OptMaster: A DAG-Based Framework for Formulation and Heuristic Discovery in Optimization

Hang Lin, Yuanpeng Gao, Yuzhi Zhang, Kun Yuan, Gang Yan, Siheng Chen, Linfeng Zhang, Weinan E
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:74310-74327, 2026.

Abstract

Optimization problems are fundamental across science and industry, including planning, scheduling, and resource allocation. While LLMs show promise in automating optimization, they struggle to bridge the gap between real-world requirements and both mathematical formulations and effective heuristic designs. Furthermore, the field lacks a unified framework that spans problem formulation and heuristic discovery for NP-hard settings. To address these challenges, we propose OptMaster, a unified framework that spans optimization from formulation to heuristic discovery, structuring the process as a Directed Acyclic Graph (DAG) where each node represents a candidate solution. The DAG architecture enables cross-branch knowledge transfer when search progress stagnates. Within each node, we further replace textual self-reflection with independently generated verification code, grounding the evaluation in deterministic computation to suppress hallucinations. OptMaster achieves competitive performance across two optimization paradigms. In Formulation Intelligence, OptMaster achieves state-of-the-art accuracy across the three most challenging benchmarks in the field. In Heuristic Discovery, OptMaster surpasses the best known solutions on Circle Packing ($n=26, 32$) and achieves a cut of 9,590 on Gset70 with significantly reduced time and search budgets.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-lin26i, title = {{O}pt{M}aster: A {DAG}-Based Framework for Formulation and Heuristic Discovery in Optimization}, author = {Lin, Hang and Gao, Yuanpeng and Zhang, Yuzhi and Yuan, Kun and Yan, Gang and Chen, Siheng and Zhang, Linfeng and E, Weinan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {74310--74327}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/lin26i/lin26i.pdf}, url = {https://proceedings.mlr.press/v306/lin26i.html}, abstract = {Optimization problems are fundamental across science and industry, including planning, scheduling, and resource allocation. While LLMs show promise in automating optimization, they struggle to bridge the gap between real-world requirements and both mathematical formulations and effective heuristic designs. Furthermore, the field lacks a unified framework that spans problem formulation and heuristic discovery for NP-hard settings. To address these challenges, we propose OptMaster, a unified framework that spans optimization from formulation to heuristic discovery, structuring the process as a Directed Acyclic Graph (DAG) where each node represents a candidate solution. The DAG architecture enables cross-branch knowledge transfer when search progress stagnates. Within each node, we further replace textual self-reflection with independently generated verification code, grounding the evaluation in deterministic computation to suppress hallucinations. OptMaster achieves competitive performance across two optimization paradigms. In Formulation Intelligence, OptMaster achieves state-of-the-art accuracy across the three most challenging benchmarks in the field. In Heuristic Discovery, OptMaster surpasses the best known solutions on Circle Packing ($n=26, 32$) and achieves a cut of 9,590 on Gset70 with significantly reduced time and search budgets.} }
Endnote
%0 Conference Paper %T OptMaster: A DAG-Based Framework for Formulation and Heuristic Discovery in Optimization %A Hang Lin %A Yuanpeng Gao %A Yuzhi Zhang %A Kun Yuan %A Gang Yan %A Siheng Chen %A Linfeng Zhang %A Weinan E %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-lin26i %I PMLR %P 74310--74327 %U https://proceedings.mlr.press/v306/lin26i.html %V 306 %X Optimization problems are fundamental across science and industry, including planning, scheduling, and resource allocation. While LLMs show promise in automating optimization, they struggle to bridge the gap between real-world requirements and both mathematical formulations and effective heuristic designs. Furthermore, the field lacks a unified framework that spans problem formulation and heuristic discovery for NP-hard settings. To address these challenges, we propose OptMaster, a unified framework that spans optimization from formulation to heuristic discovery, structuring the process as a Directed Acyclic Graph (DAG) where each node represents a candidate solution. The DAG architecture enables cross-branch knowledge transfer when search progress stagnates. Within each node, we further replace textual self-reflection with independently generated verification code, grounding the evaluation in deterministic computation to suppress hallucinations. OptMaster achieves competitive performance across two optimization paradigms. In Formulation Intelligence, OptMaster achieves state-of-the-art accuracy across the three most challenging benchmarks in the field. In Heuristic Discovery, OptMaster surpasses the best known solutions on Circle Packing ($n=26, 32$) and achieves a cut of 9,590 on Gset70 with significantly reduced time and search budgets.
APA
Lin, H., Gao, Y., Zhang, Y., Yuan, K., Yan, G., Chen, S., Zhang, L. & E, W.. (2026). OptMaster: A DAG-Based Framework for Formulation and Heuristic Discovery in Optimization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:74310-74327 Available from https://proceedings.mlr.press/v306/lin26i.html.

Related Material