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

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.

Many important decisions in science and industry require choosing the best option under a set of rules. Examples include allocating resources, planning schedules, and arranging objects efficiently. This paper studies two common challenges in this area. The first is to turn a real-world problem description into a clear mathematical model. The second is to find practical solution strategies for hard problems. Exact methods may be too slow for these problems. We present OptMaster, a framework that uses large language models to address both challenges. OptMaster does not generate only one solution. Instead, it explores many possible solution paths. Each attempt is converted into executable code. The code is then tested and checked by a separate verification step. Useful lessons from both successful and failed attempts are passed to later attempts. In this way, the system can improve over time. Across several benchmarks, OptMaster produces more reliable mathematical models. It also finds strong practical strategies for hard problems such as graph partitioning and circle packing. The results show that language models can be more useful for optimization. This happens when they are combined with execution, verification, and structured search, rather than relying only on text-based reasoning.