WorksComputer Science
Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World
Abstract
Large language models (LLMs) enable algorithm discovery for combinatorial optimization problems (COPs) through iterative program generation and evaluation. A central challenge is how to organize search to discover better algorithms within a limited budget. Our key insight is that past search trajectories and their recorded outcomes form an experience world, which can be used to facilitate the COP solving through replay. We introduce Dream-COP, in which a policy agent learns executable policies through dreaming in this experience world to guide a discovery agent in generating and refining COP programs. Specifically, policy replay provides feedback on the quality of the programs revealed and the search steps used, to guide policy selection more effectively. Across five COPs, Dream discovers better algorithms than fixed exploration in both heuristic component design and complete solver generation. Particularly, it matches the optimal values on KP and reduces the gap on OBPP from 2.112% to 1.199% while using 42.5% fewer search requests. Moreover, the learned exploration policies transfer effectively across different COPs with the assitance of the experience world.
Introduction
Combinatorial optimization problems (COPs) are central to efficient resource use in transportation, production scheduling, and resource allocation, yet finding optimal solutions becomes increasingly computationally demanding as problem size and complexity grow [16]. Heuristics and metaheuristics play a central role in obtaining high-quality solutions under practical computational constraints [3]. Developing effective heuristics often requires substantial expertise and repeated experimentation [1], motivating methods that can automate algorithm design for different problems (Figure 1).
Figure 1. Three approaches to heuristic design: (a) human expertise, (b) LLM-based heuristic search, and (c) Dream-COP, which learns exploration policies through historical replay in the experience world.
Automatic heuristic design (AHD) automates the selection, composition, and configuration of heuristics and their components [2, 29]. Large language models (LLMs) expand this design space by expressing algorithmic ideas in natural language and generating executable programs [27, 19]. Evaluation and evolutionary search then support repeated selection and revision of these programs using measured performance and execution feedback [32]. Subsequent approaches use this experience to provide reflective guidance and organize development trajectories into trees for structured exploration [33, 36]. Reinforcement learning enables the LLM to improve its generation behavior from evaluated candidates (Zhuang et al., 2026) and learn decisions within multi-turn AHD interactions [22]. These advances highlight the value of experience in improving heuristic generation.
Algorithm discovery also requires deciding which candidate program to revise and evaluate next. Different revision branches exhibit different patterns of improvement, failure, and stagnation. How the search budget is allocated among these branches, and when exploration stops, therefore directly influence the quality of the algorithms discovered. Historical trajectories record these patterns together with the outcomes of earlier revisions, providing evidence for learning how to make such decisions. We therefore ask: how can historical search trajectories help us learn better exploration policies?
World-model research suggests a useful principle: experience can provide an internal environment for improving policies before they guide further real interaction ([30, 7, 8, 10]). For algorithm discovery, this motivates turning past searches into an environment where exploration policies can be evaluated before allocating new generation and evaluation requests.
Our key insight is that historical search trees record both what was discovered and how discovery unfolded, providing exactly the structure needed for such an internal environment. We introduce Dream-COP, which learns search policies by dreaming in an experience world constructed from these trees (Figure 1c). The relationships among programs, together with their recorded evaluation outcomes, allow candidate search policies to be replayed over these development trajectories. Particularly, a policy agent proposes executable search policies that decide which revision branch to extend, when to open a new branch, and when to stop. During replay, each policy sees only the outcomes revealed by its own actions and is evaluated by the quality of the programs it reveals and the number of search steps it uses. These evaluations guide subsequent policy proposals and policy selection. The selected policy then directs a discovery agent’s program generation and evaluation, producing new search trajectories that expand the experience world. This cycle turns each completed search into two assets: candidate algorithms and experience for learning more effective exploration policies.
Our contributions are threefold. (1) We formulate historical search trees as an experience world, enabling policies to be compared through recorded outcomes without additional solver generation or evaluation during replay. (2) We develop Dream-COP, which proposes executable policies for budget allocation, and selects candidate policies using a replay objective that balances algorithm quality against the number of search steps. (3) We conduct experiments across five COPs, and the results show that Dream-COP discovers better algorithms with fewer search requests than fixed exploration. Meanwhile, it also achieves superior performance against existing LLM-based AHD methods. Cross-problem experiments further show that exploration policies learned from search experience on one COP remain effective when guiding algorithm discovery on another.
Related Work
LLM-based algorithm discovery. Automated algorithm design builds on configuration methods that optimize parameter settings from measured performance ([12, 21]) and neural approaches that learn solution-construction policies for recurring optimization problems ([14, 15]). LLM-based discovery generates executable programs, using evaluated candidates as the basis for proposing new algorithms ([18, 27, 37]). Existing frameworks can jointly develop natural-language heuristic ideas and their implementations ([19]), generate complete metaheuristics and solvers ([32, 34]), and extend evaluator-guided code evolution to broader scientific and computational problems ([26]). At the same time, search organization determines which programs receive further development. Reflective methods use performance feedback to guide program revision ([33, 24]), while MCTS-AHD organizes heuristic development into a tree to explore promising continuations ([36]). AB-MCTS uses external feedback to choose adaptively between generating new candidates and refining existing ones [13]. PathWise organizes heuristic discovery around an entailment graph that records derivation relationships and evaluation history [5]. These methods demonstrate the value of feedback for directing search. Differently, Dream-COP makes the allocation rule itself an object of program discovery: an LLM proposes executable policies that choose which revision branch to develop and when to stop, and historical replay evaluates these policies before deployment.
Experience-driven search-policy adaptation. Experience can change both how candidates are generated and how discovery decisions are made. EvoPH co-evolves prompts and heuristics using feedback from past search [20]. CALM and RFTHGS use evaluated algorithms to improve the LLM generation through reinforcement learning [11, 38]. AHD Agent extends learning to multi-turn heuristic design, training an LLM to decide between generating heuristics and using tools to obtain evidence in synthesized environments [22]. These works adapt prompts, model parameters, or interactive generation behavior. Dream-COP learns a separate executable controller over the program-search tree, updating budget allocation decisions while keeping LLM weights fixed.
Language agents also adapt through textual feedback, from iterative output refinement to reflections retained across trials [23, 28]. Agent-Pro optimizes behavioral policies through reflection on trajectories and beliefs [35], while MetaReflection learns instructions from past reflections [6]. We likewise use accumulated feedback to guide policy proposals. To evaluate a proposed policy, we execute it on the same historical trees and compare the quality of the programs it reveals and the number of search steps it uses.
Policy learning in internal environments. Dyna couples real interaction with planning through a learned environment model [30]. World Models train controllers inside a learned recurrent environment and transfer them to real interaction [7]. Dreamer learns behavior from imagined trajectories in latent world models [8, 9, 10]. These approaches use internal environments to improve policies before further interaction. Dream-COP applies this principle to algorithm discovery through an experience world whose transitions and outcomes come directly from recorded program revisions. A policy’s actions reveal these records in sequence, allowing alternative allocation and stopping strategies to be compared without new algorithm generation or evaluation during replay. The selected policy then controls subsequent real search, which supplies new trees for learning. This connects experience reuse to an explicit cycle of exploration-policy proposal, replay evaluation, and deployment.
Dream-COP
Dream-COP learns search policies by replaying completed search trees (Figure 2). Particularly, a discovery agent generates and evaluates solver programs, recording their development as search experience; a policy agent uses this experience to learn executable policies that allocate subsequent search budget and decide when to stop. Both agents are instantiated with the same LLM backbone.
Figure 2. Learning search policies from recorded experience. The discovery agent generates and evaluates candidate programs, recording their development trajectories as historical search trees. These trees provide an experience world in which the policy agent compares executable policies. During replay, each policy sees only the outcomes revealed by its own actions; the world supplies recorded transitions without new solver generation or evaluation. Replay feedback guides successive policy proposals, and the selected policy controls the next real search round. The depicted trajectories illustrate alternative search allocations.
The Discovery Agent and Search Trees
Let denote a solver program and let be its quality on a fixed development set, normalized so that larger values are better. The discovery agent generates either a heuristic within a fixed controller or a complete solver. An independent evaluator verifies solutions and computes their quality, providing feedback under either interface.
A search round begins with a feasible root program. At each search step, the discovery agent receives the task specification, the selected parent program, the hypotheses associated with its revision branch, and evaluation feedback. It returns a revised program together with a brief description of the change. The evaluator then records the result. Each request consumes one search step, including requests that fail to produce a valid revision.
We record each round as a rooted tree , where only the root may have multiple children, and every other node has at most one child. The tree thus represents alternative branches of program revisions. At the same time, a search policy (i.e., generated by the policy agent) chooses whether to open a new branch, extend an existing branch, or stop.
Executable Policies for Budget Allocation
At step , the observation summarizes the revealed tree together with the remaining budget and action history. Then, an executable policy maps this observation to a single action:
Here, is the set of current leaf identifiers; the policy selects ROOT to open a new branch, to extend the corresponding branch; or None to stop the round. The policy agent proposes policies between rounds; during real search, DREAM executes the selected policy after observing each completed outcome. Its input expresses the preference between further exploration and earlier stopping. Appendix A details the observation fields and presents an example of a learned policy. For comparison, FIXED follows a predetermined policy that opens revision branches and allocates search steps to each branch. DREAM uses this policy in its first round. Both methods run for rounds with a budget of search steps per round. Learned policies can redistribute this budget across branch counts and lengths, or stop early.
Historical Trees as an Experience World
The experience world allows a policy to explore the recorded transitions of in its own order. Let be the nodes revealed after replay steps and the remaining replay budget. Initially, contains only the root. For a non-stopping action with , replay updates
Here, contains the next unrevealed child of the root in recorded order, or the recorded child of the selected leaf. It is empty when no continuation remains. Newly revealed nodes expose their stored feasibility and quality outcomes without calling the discovery agent or the evaluator.
During replay, the policy uses the same observation interface as in real search and sees only the outcomes revealed by its actions, including feasibility, solution quality, and execution failures. The same recorded tree can therefore support different search trajectories: a policy may stop after exploring one branch or alternate among branches. These decisions determine which programs are revealed and how many replay steps are used.
Each request to the root or a leaf counts as one replay step, including empty requests with . Replay ends when the policy returns None, the replay budget is exhausted (), or all recorded nodes have been revealed (). Appendix A specifies replay budgets and eligibility rules for the accumulated history after round .
Replay Objective
A useful search policy should reveal high-quality programs while avoiding unproductive requests. For policy and exploration setting , let denote the multiset of development scores of feasible nodes revealed during replay on tree , including the score of the root node. With , sort these scores as and define
When development scores are closely clustered, the best score alone provides a narrow view of a policy’s search performance. We therefore average the top five feasible scores to capture progress across several promising candidates. Five serves as a practical cutoff that keeps this quality measure focused on high-performing programs while limiting the influence of lower-ranked candidates.
Let count replay steps, then the replay objective at boundary is
where is the nonempty set of eligible trees available at this boundary, weighted equally. The fixed coefficient penalizes each replay step in units of normalized development quality. Thus, controls exploration preference, while determines the trade-off between program quality and search cost in the replay objective .
The Policy Agent: Learning from Replay
Let be the pair deployed in round . Starting with , the first round uses \pi_1 = \textsc{Fixed}, which ignores its input. Each round generates a search tree and expands the history:
where Search executes the discovery agent under the deployed policy with at most search steps.
Before the next round (), policy learning runs whenever the expanded history contains eligible trees, i.e., . The policy agent proposes executable policies through four sequential LLM calls, using the current policy and historical evidence. After each call, replay evaluates the proposals; rewards, quality, step counts, and failures inform the next call. This feedback guides refinement of stopping, branching, allocation, and revisiting decisions. Appendix A.2 provides the prompt template.
For a policy–parameter pair , write . Let contain the valid pairs generated at this boundary, then the pair with the best mean replay reward is deployed as
Policy learning leaves LLM weights unchanged. The selected policy remains fixed throughout the next real search round, which supplies new experience. Appendix A provides execution and selection details and the complete procedure (Algorithm 1).
Experiments
Our experiments address three questions: (1) Can Dream-COP discover better algorithms with fewer search requests? (2) Does historical replay improve the effectiveness of learned search policies? (3) How well do these policies transfer across different COPs?
We first evaluate Dream-COP on four tasks in which the discovery agent evolves heuristic components within fixed controllers: constructive variants of the traveling salesman problem (TSP) and knapsack problem (KP), online bin packing (OBPP), and flow-shop scheduling (FSSP). We further use offline two-dimensional bin packing (2D-BPP) to evaluate complete solver generation and to analyze policy replay and the trade-off between solution quality and search cost. Moreover, we evaluate cross-problem policy transfer among TSP, OBPP, and FSSP. Complete Dream-discovered programs are provided in Appendix E.
Evaluation Settings
Tasks and instances. For constructive TSP and KP, we aim to evolve next-city and next-item selectors within fixed construction procedures to minimize tour length and maximize total item value, respectively. Each task is evaluated on 1,000 test instances at each size . TSP additionally includes 15 TSPLIB instances, totaling 4,015 test instances. For OBPP, we aim to evolve a bin-scoring rule to minimize bin count and evaluate it on 30 test instances spanning 1,000–10,000 items and capacities 100 and 500. For FSSP, we aim to evolve a perturbation function within a fixed local-search controller to minimize makespan and evaluate it on 110 Taillard test instances covering 11 sizes [31]. For 2D-BPP, we aim to evolve complete solvers to minimize bin count and evaluate them on 500 BWMV test instances with 20–100 rectangles per instance [25].
Following MCTS-AHD [36], we use its released development sets of 64 TSP instances with 50 cities, 64 KP instances with 100 items, and four OBPP instances. For FSSP, we use the 64 development instances with 50 jobs released in EoH [19]. For 2D-BPP, we generate 60 instances following the BWMV class distributions [25]. These development sets are disjoint from the corresponding test sets. Task specifications are detailed in Appendix § 7.
Methods and setting. We compare with applicable implementations of FunSearch, EoH, ReEvo, and MCTS-AHD [27, 19, 33, 36]. Both FIXED and DREAM use the same discovery agent and run for rounds. FIXED opens branches per round with a maximum depth of , whereas DREAM adaptively allocates the same budget of search steps per round and may stop early. Both therefore allow at most 240 search steps overall; the other baselines receive a budget of 240 candidates, including initialization. Invalid generations and failed evaluations count toward these budgets. Search steps measure algorithm-discovery effort, whereas token costs also account for policy learning. The main backbone is GPT-6-Luna; TSP and FSSP also use GPT-4o-mini, and 2D-BPP also uses GPT-6-Sol. In the GPT-6-Luna experiments on TSP and 2D-BPP, FIXED and DREAM share the initial solver within each comparison. For each run, we freeze the solver with the highest development score before testing it directly on all test instances. All reported evaluations are complete, with zero failed instances. Appendix § 8 provides detailed experimental configurations.
Performance across Problems and Sizes
Constructive TSP and KP. Table 1 shows that DREAM achieves the lowest mean tour length among the compared LLM-based AHD methods across all four synthetic sizes and TSPLIB, using either LLM backbone, i.e., GPT-6-Luna or GPT-4o-mini. Here, with GPT-6-Luna, it reduces the overall mean gap to LKH from FIXED’s 17.65% to 11.60% while using 13.75% fewer search requests.
| LLM Model | Method | Obj.↓ | Gap (%) | Obj.↓ | Gap (%) | Obj.↓ | Gap (%) | Obj.↓ | Gap (%) | TSPLIB Obj.↓ | TSPLIB Gap (%) |
| LKH ref. | 5.675 | – | 7.768 | – | 10.708 | – | 16.531 | – | 46392.7 | – | |
| Greedy | 6.959 | 22.622 | 9.706 | 24.936 | 13.461 | 25.711 | 20.813 | 25.903 | 57055.2 | 24.332 | |
| POMO | 5.697 | 0.383 | 8.001 | 2.999 | 12.897 | 20.447 | 24.156 | 46.135 | 60654.7 | 23.923 | |
| GPT-4o-mini | EoH | 6.629 | 16.822 | 9.252 | 19.114 | 12.939 | 20.842 | 20.202 | 22.209 | 55974.5 | 21.060 |
| ReEvo | 6.959 | 22.622 | 9.706 | 24.936 | 13.461 | 25.711 | 20.813 | 25.903 | 57055.2 | 24.332 | |
| MCTS-AHD | 6.578 | 15.906 | 9.231 | 18.832 | 12.974 | 21.166 | 20.258 | 22.549 | 55759.7 | 19.306 | |
| FIXED | 6.959 | 22.622 | 9.706 | 24.936 | 13.461 | 25.711 | 20.813 | 25.903 | 57055.2 | 24.332 | |
| Dream-COP | 6.490 | 14.379 | 9.006 | 15.952 | 12.587 | 17.557 | 19.696 | 19.149 | 54416.3 | 17.390 | |
| GPT-6-Luna | EoH | 6.630 | 16.819 | 9.241 | 18.955 | 12.882 | 20.305 | 20.019 | 21.099 | 56590.2 | 20.658 |
| ReEvo | 6.566 | 15.682 | 9.204 | 18.493 | 12.881 | 20.292 | 20.075 | 21.440 | 55454.1 | 20.782 | |
| MCTS-AHD | 6.582 | 15.959 | 9.161 | 17.929 | 12.758 | 19.143 | 19.792 | 19.728 | 55893.7 | 20.226 | |
| FIXED | 6.543 | 15.275 | 9.123 | 17.432 | 12.688 | 18.495 | 19.734 | 19.378 | 54476.4 | 18.355 | |
| Dream-COP | 6.214 | 9.489 | 8.647 | 11.316 | 12.031 | 12.361 | 18.714 | 13.209 | 51666.6 | 11.984 |
Table 1. Constructive TSP: mean tour length and gap (%) to LKH, which matches the official optima on all 15 TSPLIB instances. We also include Greedy and POMO [17] as baselines. LLM-based results are averaged over 3 runs. Bold: best non-reference result; shading: best LLM result within each model, including ties.
These gains show that learned search policies discover constructive programs that generalize beyond the development instances. At , DREAM also reduces the mean solve time per instance from 137 seconds with FIXED to 80 seconds, improving both tour quality and execution efficiency (Appendix § 9.§ 1). Figure 3 shows the mean best-so-far development score across three runs, with shading indicating standard error. DREAM reaches a higher final score than FIXED while using fewer search requests. It also surpasses the compared LLM-based baselines, showing that more selective use of the search budget can improve the quality of the discovered programs.
Figure 3. TSP development score using GPT-6-Luna, averaged over three independent runs per method.
Table 2 reports the constructive KP results across four item counts. DREAM matches the OR-Tools optimal values to the displayed precision at all four sizes, whereas none of the compared baselines consistently achieves a zero gap. At the largest size, , MCTS-AHD and FIXED retain gaps of 0.020% and 0.010%, respectively. DREAM attains its higher solution quality while using 17.5% fewer search requests than FIXED, demonstrating more effective use of the discovery budget.
| LLM Model | Method | , Obj.↑ | , Gap (%) | , Obj.↑ | , Gap (%) | , Obj.↑ | , Gap (%) | , Obj.↑ | , Gap (%) |
| OR-Tools opt. | 20.037 | – | 40.272 | – | 57.447 | – | 90.963 | – | |
| Greedy | 19.985 | 0.261 | 40.225 | 0.118 | 57.395 | 0.090 | 90.919 | 0.048 | |
| POMO | 19.510 | 2.548 | 39.431 | 2.034 | 57.209 | 0.417 | 85.414 | 6.096 | |
| GPT-6-Luna | MCTS-AHD | 20.037 | 0.000 | 40.272 | 0.000 | 57.447 | 0.000 | 90.945 | 0.020 |
| FIXED | 20.033 | 0.019 | 40.264 | 0.020 | 57.436 | 0.020 | 90.954 | 0.010 | |
| Dream-COP | 20.037 | 0.000 | 40.272 | 0.000 | 57.447 | 0.000 | 90.963 | 0.000 |
Table 2. Constructive KP: mean objective value and gap (%) to the OR-Tools optimum by item count and capacity , averaging 1,000 test instances per size. LLM-based methods use GPT-6-Luna. Bold: best non-reference result; shading: best LLM result, including ties.
Online packing and flow-shop scheduling. Table 3 reports OBPP gaps at capacity , with each cell averaging five instances. Table 9 in the Appendix includes both and . Averaged over all 30 test instances across both capacities, DREAM reduces the gap to the volume lower bound from FIXED’s 2.112% to 1.199%, using 42.5% fewer search steps. The improvement is concentrated in longer item sequences at capacity 100, where DREAM outperforms all included baselines. Since every method uses the same packing controller, this gain reflects a more effective bin-scoring rule discovered through adaptive search.
| FunSearch | EoH | ReEvo | MCTS | FIXED | DREAM | |
| 1k | 4.771 | 4.771 | 4.522 | 3.926 | 4.371 | 4.477 |
| 5k | 4.307 | 4.307 | 3.743 | 3.357 | 3.585 | 1.089 |
| 10k | 4.049 | 4.049 | 3.730 | 3.291 | 3.501 | 0.459 |
Table 3. OBPP with GPT-6-Luna: mean gap (%) to the volume lower bound at capacity , by item count (lower is better). Shading marks the best method at each size.
| Ref. LB Bins | Ref. LB Gap (%) | FunSearch Bins | FunSearch Gap (%) | EoH Bins | EoH Gap (%) | ReEvo Bins | ReEvo Gap (%) | MCTS-AHD Bins | MCTS-AHD Gap (%) | FIXED Bins | FIXED Gap (%) | Dream-COP Bins | Dream-COP Gap (%) | ||
| 1k | 100 | 402.4 | - | 421.6 | 4.771 | 421.6 | 4.771 | 420.6 | 4.522 | 418.2 | 3.926 | 420.0 | 4.371 | 420.4 | 4.477 |
| 1k | 500 | 80.6 | - | 80.8 | 0.247 | 80.8 | 0.247 | 80.8 | 0.247 | 80.8 | 0.247 | 80.8 | 0.247 | 80.8 | 0.247 |
| 5k | 100 | 2019.4 | - | 2106.4 | 4.307 | 2106.4 | 4.307 | 2095.0 | 3.743 | 2087.2 | 3.357 | 2091.8 | 3.585 | 2041.4 | 1.089 |
| 5k | 500 | 402.4 | - | 404.6 | 0.547 | 404.6 | 0.547 | 404.6 | 0.547 | 404.6 | 0.547 | 404.4 | 0.497 | 404.2 | 0.448 |
| 10k | 100 | 4010.6 | - | 4173.0 | 4.049 | 4173.0 | 4.049 | 4160.2 | 3.730 | 4142.6 | 3.291 | 4151.0 | 3.501 | 4029.0 | 0.459 |
| 10k | 500 | 802.4 | - | 806.2 | 0.474 | 806.2 | 0.474 | 806.2 | 0.474 | 806.2 | 0.474 | 806.2 | 0.474 | 806.2 | 0.474 |
Table 9. OBPP mean bin counts and gaps (%) to the volume lower bound by item count and bin capacity . All LLM-based methods use GPT-6-Luna. Each row averages five instances. Ref. LB reports the mean volume lower bound. Shading marks the lowest non-reference values in each row and metric, including ties at displayed precision.
On FSSP, DREAM achieves the lowest aggregate makespan among the LLM-based methods with both LLM backbones, with improvements over FIXED and EoH extending to the largest job counts. With GPT-6-Luna, its mean gap to the upper bound is 0.0412%. Across the 110 instances, DREAM records 59 wins, 40 ties, and 11 losses against FIXED. Excluding ties, a two-sided exact sign test gives . This extends the benefit of learned search from constructive decisions to perturbations within iterative local search. Figure 4 further shows that DREAM’s 60-second GLS protocol achieves a lower mean gap than CP-SAT and OptalCP under their 300-second limits. The LLM-based results in the heatmap use GPT-6-Luna, where each entry for a given problem size averages ten instances, while the overall mean averages all 110 instances. Appendix D.2 provides the complete makespan/time results (Table 8) and settings.
Figure 4. FSSP mean gap (%) to the Taillard reference upper bound by size (lower is better). LLM-based methods use GPT-6-Luna. Bold marks the best method per row.
Designing Complete 2D-BPP Solvers
The preceding tasks evolve components within fixed controllers. For 2D-BPP, we instead ask the discovery agent to generate complete solvers that assign rectangles to bins and determine their positions without rotation. Each solver implements its own construction and improvement logic within a given time budget. An independent geometric checker verifies the resulting packing layouts.
We evaluate candidate solvers on 60 development instances using mean squared bin utilization as the score. The selected solvers are then tested on 500 BWMV instances with a 60-second budget per instance. Table 4 reports their excess bin counts relative to the published BRKGA reference [4]. All selected solvers produce feasible layouts on every instance, and DREAM uses fewer bins than FIXED with both settings. With GPT-6-Luna, it saves eight bins over the 500-instance test set, with most of the improvement occurring on larger instances. These results show that learned search policies remain effective when the discovery agent must coordinate construction, placement, and improvement within a complete solver.
Experimental Analysis
We examine the two terms of the replay objective by comparing quality measures across all five COPs and varying the cost penalty on 2D-BPP. We then use 2D-BPP to assess the contribution of policy replay and illustrate how learned policies allocate the search budget.
Replay quality measure. The replay quality term in Eq. (3) averages the top five feasible development scores. We denote it by and compare it with , keeping the request penalty unchanged. Whereas increases only when a new best score is revealed, also captures improvements in the overall quality of the top-five candidates. We examine whether this richer signal helps exploration through periods without a new best. Both objectives use GPT-6-Luna with the same root programs and budgets for discovery and policy learning, with one completed run per objective and problem.
We count a delayed improvement when a new best development score is reached within a round after at least three consecutive requests without a new best. To account for varying search effort, we report these events per 100 discovery requests across the learned-policy rounds, excluding the initial round. Failed requests count toward both the stagnation interval and the request total. Figure 5 shows higher delayed-improvement rates with on all five problems, suggesting that the quality of several promising candidates provides useful guidance during stagnation.
Figure 5. Delayed improvements per 100 discovery requests under and with GPT-6-Luna.
The selected solvers also achieve higher development scores and better test performance with on TSP, FSSP, and 2D-BPP, with identical KP results (see Appendix § 9.§ 4). Together, these results support using multiple promising candidates to assess replay quality and guide continued exploration.
Cost penalty. We next examine the cost term of the replay objective by varying on 2D-BPP. Figure 6 compares search progress under different penalties and with or without policy replay, averaging three runs per setting. Dream with and reaches higher mean development scores than Fixed with fewer search steps, whereas favors shorter searches. Increasing from to reduces mean search steps by 44.1%, while the final mean development score changes from 0.75451 to 0.75209. At , Dream uses 106 search steps on average, compared with 240 for Fixed, and still achieves a lower mean test bin count (14.51333 versus 14.51933). We use as the default to balance quality and cost. Appendix D.5 provides the full sensitivity results in Table 12 and round-level statistics in Figure 10.
Figure 6. 2D-BPP search progress under different cost penalties and with or without policy replay, using GPT-6-Luna. Curves show the best-so-far development score, averaged over three runs per setting.
Figure 10. Round-level 2D-BPP development quality and search effort with GPT-6-Luna. (a) Cumulative best development score at the end of each round. (b) Search steps per round, including failures. Each point averages three runs.
The reduction in search effort also yields net token savings. Including policy learning, Dream at reduces mean total recorded tokens by 23.8% relative to Fixed, as the savings in solver discovery exceed the cost of policy learning. Appendix D.5 reports the token breakdown.
Policy-replay ablation. Using the default cost penalty, we next examine the contribution of replay-based policy evaluation and selection. We compare Dream with No replay, which uses the same historical-evidence interface and algorithm-discovery budget. At each learning boundary, No replay makes one LLM call to generate a single policy and deploys it after syntax and interface checks, without replay-based evaluation or selection. In Figure 6, No replay remains close to Fixed, whereas
DREAM reaches a higher development score with fewer search steps. Comparing three-run mean bin counts on each of the 500 test instances gives DREAM 15 wins, 483 ties, and 2 losses against No replay. Excluding ties, a two-sided exact sign test gives . These results support the replay-based policy-learning loop, which evaluates policies in the experience world before deployment.
Learned budget allocation in real search. To illustrate how these policies guide individual search decisions, Figure 7 follows DREAM within a round’s 24-step budget. It allocates different numbers of steps to the six branches, extending promising ones beyond FIXED’s four-step limit. After two lower-scoring revisions on the first branch, it explores other branches before returning at step 20. This revisit produces the program with the highest development score in the run, at depth eight. The trajectory shows how learned policies combine deeper refinement with exploration of alternatives under the same total budget.
Figure 7. 2D-BPP search round 9 with GPT-6-Luna. (a) Allocation of the 24-step budget across branches, compared with four steps per branch under FIXED. (b) Development scores along the first branch. (c) Complete search tree, with nodes labeled by search step. The highlighted program has the highest development score in the run and is selected for testing.
Cross-Problem Policy Transfer
We further examine whether learned search policies transfer effectively across COPs. We consider three directions: TSP OBPP, OBPP FSSP, and FSSP TSP. For TSP, we report mean tour length with . For each transfer, we deploy the final search policy learned in a DREAM run on the source problem, keeping its code fixed throughout target search.
All target runs use GPT-6-Luna, , , and . For each transfer run, we freeze the program with the highest development score before testing. Table 5 compares transferred policies with the FIXED and DREAM results. Transferred policies improve test quality over FIXED in all three directions while using 25.0–64.2% fewer search steps. On OBPP, transfer also surpasses DREAM, reducing the mean gap from 1.198% to 1.0637%. A plausible explanation is that transfer benefits from an exploration strategy already learned on the source problem, which guides OBPP discovery from the first round, whereas DREAM initially collects target-problem experience before learning its policy online. These results demonstrate that learned exploration policies provide reusable guidance for algorithm discovery across different COPs.
| Transfer | Method | Dev. score | Test metric | Search steps |
| TSP OBPP | Fixed | 0.98142 | 2.1124 | 240 |
| Dream | 0.98409 | 1.1988 | 138 | |
| Transferred Dream | 0.98710 | 1.0637 | 86 | |
| OBPP FSSP | Fixed | 0.54973 | 0.1940 | 240 |
| Dream | 0.54990 | 0.0412 | 176 | |
| Transferred Dream | 0.54981 | 0.0872 | 174 | |
| FSSP TSP | Fixed | 0.90642 | 9.4513 | 240 |
| Dream | 0.91173 | 8.9643 | 207 | |
| Transferred Dream | 0.91114 | 8.9863 | 180 |
Table 5. Cross-problem policy transfer with GPT-6-Luna, using one paired run per direction. Test metric reports mean tour length for TSP and mean gap (%) for OBPP and FSSP. Dev. score reports the highest development score in each run. Search steps count algorithm-discovery requests, including failures, with a maximum of 240 per run. Bold marks the better result within each comparison.
Conclusion
We introduced Dream-COP, which learns search policies through historical replay to guide algorithm discovery for combinatorial optimization problems. Recorded transitions and outcomes enable executable search policies to be evaluated and refined through replay, without additional solver generation or evaluation. The learned policies then guide budget allocation in subsequent search rounds. Experiments across five COPs demonstrate that this approach discovers better algorithms with fewer search requests than fixed exploration. These gains hold for the generation of both heuristic components and complete solvers. The replay ablation further supports evaluating candidate policies in the experience world before deployment. Cross-problem experiments further show that learned search policies remain effective beyond the problems on which they were learned. Together, these results demonstrate that historical search experience can be used to learn policies that guide more effective algorithm discovery.
Algorithm and Agent Details
Algorithm 1 summarizes how solver discovery and policy learning alternate across rounds. Each completed search round contributes a tree to the accumulated history, providing experience for evaluating policy proposals through replay and selecting a policy for subsequent search. The following sections detail the policy interface and observations, history eligibility and replay rules, and the policy-selection procedure. We also provide the core prompts for the discovery and policy agents, followed by an executable policy example that illustrates how the learned decision rules operate.
Algorithm 1 Dream-COP: real search and policy learning
Require: Task, reference program, , , , penalty
; ;
for do
Initialize root under the task contract
if and then
for do
Propose policies using accumulated feedback
Replay each at five values on
Add valid pairs to ; summarize outcomes
end for
Update by Eq. (5)
end if
end for
Select and freeze the solver with the highest development score
Evaluate the frozen solver directly on the test set
Policy interface. A policy is implemented as policy(observation, alpha). At each step, it returns ROOT to start a new branch, a current leaf to extend an existing branch, or None to stop the current round. DREAM executes one search request at a time.
The observation contains the search settings , , and , together with the total, used, and remaining budget. For each node in the revealed search tree, it records the parent, program and development score. It also reports the branch count and identifies the root and current leaves as the points at which the policy can start a new branch or extend an existing one, respectively. Unselected branches remain available for subsequent exploration, even after a failed search step.
To compare branches, the observation provides the global best score and top-five mean, per-branch best and current scores, and quality gaps. Branch depth, recent gains, stagnation, and the number of steps since a branch’s last request help the policy decide whether to continue or revisit it. Feasibility, execution status, failures, and empty-request counts distinguish evaluated outcomes from missing continuations. The action history records previous choices and revealed outcomes, along with the budget and quality after each step, allowing the policy to reconstruct its past decisions within the current tree.
A program that produces an infeasible solution receives no numerical quality score. An interrupted request still consumes budget, but is not classified as a solver failure. During replay, an empty request indicates that no recorded continuation is available, whereas a request reaching an invalid program reveals the recorded failure. Both consume one replay step, and the request status is included in the next observation. All observation fields use only information revealed so far, excluding future scores and counts of unrevealed descendants. Completed trees are provided separately to the policy agent for policy learning.
Each policy decision runs in a fresh restricted scope, so the policy must reconstruct its earlier decisions from the supplied action history. Execution permits only approved operations, with no access to files or networks, and is limited to one second and 256 MiB of memory per decision.
History and replay budgets. The history contains completed, replayable search trees. A tree is eligible for policy learning once it contains sufficiently many recorded search steps:
Here, is the node set of . The count excludes the root and includes failed search steps; eligibility does not require an improvement in solution quality. With and , a tree becomes eligible after five recorded search steps. Before each subsequent round (), policy learning uses all eligible trees accumulated so far. Learning proceeds whenever this set is nonempty, even if the latest round contributes no newly eligible tree. Otherwise, the current policy and parameter are retained.
Replay evaluation. Real search allows at most search steps per round, whereas replay allows at most steps per historical tree. Requests that reveal a failure or have no recorded continuation both consume one replay step.
Replay quality is computed from the scores of revealed feasible nodes, including the root, using Eq. (3). Each node contributes once, and equal scores from different nodes are counted separately. If fewer than five feasible nodes have been revealed, all available scores are averaged. Failed nodes do not contribute to the quality statistic.
Policy proposals and selection. Policy learning consists of four sequential LLM calls, each requesting four distinct executable policies. Each proposed policy is replayed at in ascending order. Replay results and generation or execution failures are formatted as feedback for the next call. Valid proposals are retained even if other proposals in the same call fail; no additional repair or retry calls are made.
After all four calls, we select the valid generated policy–parameter pair with the highest replay reward. Ties favor the earlier policy proposal and, within a policy, the smaller . The incumbent policy and FIXED are also replayed to provide reference results for feedback, but are excluded from candidate selection. The incumbent is retained only if no valid generated pair is available.
Discovery repairs. The discovery agent may make up to two repair attempts for generation or compilation errors before full development evaluation. No further repairs are allowed once that evaluation begins. Every search step consumes budget, including steps that end in generation or evaluation failure. Appendix C provides the cost-accounting details.
Core Discovery-Agent Prompt
Figure 8 summarizes the shared instructions and request context used to develop a solver. The required interfaces, objectives, and evaluation protocols are specified in Appendix B. Bracketed placeholders contain the parent program, branch-local feedback, and evaluation settings. The search policy selects the parent program, and the discovery agent proposes and implements a revision.

Figure 8. Core discovery-agent prompt modules. Brackets denote dynamic inputs.
Core Policy-Learning Prompt
Figure 9 presents a condensed policy-learning prompt from a TSP run, separating shared instructions from context updated for each proposal call. Bracketed placeholders denote the policy source, historical search records, and replay feedback. The four calls focus in turn on stopping, branching, allocation, and revisiting.

Figure 9. Core policy-learning prompt modules. Brackets denote dynamic inputs.
Each subsequent call receives replay results and generation or execution failures from earlier calls. The policy supplied for refinement is the valid proposal with the highest replay reward so far in the current update. If no valid proposal is available, the incumbent is supplied instead. The policy agent uses completed historical trees to guide proposal generation. During execution, each proposed policy receives observations containing only outcomes revealed by its own actions.
An Example of a Learned Policy
Listing 1 shows a learned policy from the GPT-6-Luna TSP experiment. It was selected after the eighth search round and deployed in the ninth with . The ninth round produced the program with the highest development score in the run. The code is reproduced with only line wrapping changed. Appendix § 9.6 follows its decisions and the resulting real search trajectory.
The policy balances continuing recent progress with revisiting previously promising branches. It continues branches that show recent gains, little stagnation, and a small gap to the best observed quality. It also revisits paused branches whose earlier gains and current quality justify further exploration. Eligible branches are ranked by a score that rewards gains and penalizes stagnation and quality gaps. If the highest-ranked branch exceeds the continuation threshold, the policy extends it. Otherwise, it opens a new branch if fewer than branches exist, or stops the round. This learned policy therefore retains as its branching cap while adapting branch lengths and revisits to observed progress.
Increasing lowers the recent-gain and continuation thresholds and relaxes quality-gap limits. For revisiting a branch, it also permits more stagnation while requiring a longer interval since the branch’s last request.
Here, recent_gains contains up to three most recent increases in a branch’s best score, and gap_to_best measures how far that score trails the global best. stagnation counts requests to the branch since its last improvement. idle_batches counts completed serial search steps since the branch’s last request. All quantities are computed from revealed outcomes.
Benchmark Tasks, Interfaces, and Metrics
Reference gaps. For objective and reference on instance , the mean relative gap over instances is
We compute gaps relative to LKH tour lengths for TSP, certified OR-Tools optima for KP, the volume lower bound for OBPP, and the supplied Taillard upper bounds for FSSP. A negative gap of FSSP indicates a makespan below the reference upper bound ().
Traveling salesman problem (TSP). The evolved selector implements select_next_node(current_node, destination_node, unvisited_nodes, distance_matrix). It receives the current city, the return destination (city zero), the unvisited cities, and the matrix of unrounded Euclidean distances, and returns one unvisited city ID. The fixed constructor starts at city zero and repeatedly invokes the selector until all cities have been visited, then closes the tour.
The development set consists of 64 50-city instances in train50_dataset.npy from the public MCTS-AHD dataset.2 For each 50-city instance, a tour of length gives quality . All reported methods and reference solvers are evaluated on the same 4,000 synthetic instances at and 15 TSPLIB instances, totaling 4,015 test instances. Gaps are computed relative to LKH tour lengths, which match the official optima on all 15 TSPLIB instances (Appendix § 9.§ 1).
Knapsack problem (KP). The evolved selector implements select_next_item(remaining_capacity, weights, values). It receives the remaining knapsack capacity and the weight and value arrays of the remaining items, and returns the index of an item that fits within the remaining capacity. The index refers to the supplied arrays. The fixed constructor removes the selected item, updates the remaining capacity, and repeats until no remaining item fits. The selected subset is checked against the original instance.
Listing 1: A learned TSP search policy, deployed with .
def policy(observation, alpha):
if (observation["remaining"] <= 0
or observation["used"] >= observation["budget"]):
return None
leaves = observation.get("leaves", [])
options = []
for r in observation.get("branch_stats", []):
leaf = next((n for n in leaves
if n["id"] == r["leaf_id"]), None)
if leaf is None or leaf.get("status") == "interrupted":
continue
gains = r.get("recent_gains", [])
peak = max(gains) if gains else 0.0
recent = sum(gains) / max(1, len(gains))
stale = r.get("stagnation", 0)
gap = r.get("gap_to_best", 0.0)
idle = r.get("idle_batches", 0)
delayed = (peak >= 0.001 and idle >= 1 + int(3 * alpha)
and stale <= 2 + int(2 * alpha)
and gap <= 0.004 + 0.008 * alpha)
active = (recent >= 0.0003 * (1.0 - alpha) + 0.00004
and stale <= 1 and gap <= 0.003 + 0.007 * alpha)
if delayed or active:
value = max(peak / (2.0 + stale) if delayed else 0.0,
recent / (1.0 + stale)) - 0.04 * gap
options.append((value, idle if delayed else -idle, leaf["id"]))
if options:
value, _, leaf_id = max(options)
if value > 0.00012 * (1.0 - alpha):
return leaf_id
if observation["branches"] < observation["B"]:
return "ROOT"
return None
The development set consists of 64 instances at in train100_dataset.npy from the public MCTS-AHD dataset.3 Item weights and values are uniformly distributed in . The knapsack capacity is for items and for . The development score is the total value of the selected items divided by 100. Test results report the total selected value without normalization. The official test checker uses a feasibility tolerance of . The OR-Tools reference enforces the original capacities without this tolerance.
Online bin packing problem (OBPP). The evolved function implements score(item, bins), where item is the arriving item’s size and bins contains the remaining capacities of all feasible bins, including unused bins. It returns one score for each supplied bin. The fixed controller places the item in the bin with the highest score, breaking ties by choosing the first bin in the supplied order.
We use the released MCTS-AHD dataset for OBPP.4 The four development instances cover the combinations of items and bin capacities . The 30 test instances additionally include at both capacities. For an instance with item weights , and used bins, the volume lower bound is . The development score is , averaged equally across the four development instances. Test performance is the percentage excess in bin count over this bound, , averaged equally across the 30 test instances.
Flow-shop scheduling problem (FSSP). The evolved perturbation function implements get_matrix_and_jobs(current_sequence, time_matrix, m, n). Here, current_sequence lists the current job order, time_matrix is the processing-time matrix, and and are the numbers of jobs and machines, respectively. The function returns a modified processing-time matrix of the same shape and a list of job IDs to perturb. The fixed controller initializes the sequence with NEH and uses these outputs to guide swap and insertion perturbations within GLS. Makespan is computed from the original processing times.
The development set consists of all 64 instances in the public EoH training set, with 50 jobs and 2–20 machines.5 The development score is . Testing uses the 110 Taillard instances, with ten instances per job–machine size. The supplied upper bounds serve as reference makespans.
GLS is allowed up to 30 seconds during development and 60 seconds during testing, with a maximum of 1,000 iterations in both phases. Reaching the iteration cap can therefore end a run before its time budget is exhausted.
Two-dimensional bin packing problem (2D-BPP). The evolved program implements solve(instance, time_budget, seed). The instance provides the bin dimensions and rectangle sizes, time_budget specifies the solve time allowance in seconds, and seed controls randomness. The program returns one placement per rectangle in input order, specifying its bin ID and lower-left coordinates. The checker verifies integer coordinates, preservation of the original orientations, bin containment, and pairwise non-overlap.
The development set consists of 60 instances generated following the BWMV class distributions, with a 20-second solve budget per instance. The development score is , where is the number of used bins and is the area utilization of bin . Testing uses 500 BWMV instances with a 60-second budget per instance and reports the number of used bins.6 These instances cover ten problem classes and five sizes from 20 to 100 items in increments of 20, with ten instances per class–size combination.
The reference results use the aNB variant of BRKGA without rotation (Gonçalves & Resende [4]), with equal weight assigned to each class–size combination. Table 4 reports the BRKGA bin counts and the excess bin counts of FIXED and DREAM relative to this reference. Each size row sums over 100 instances, and the All row sums over all 500 instances.
| BRKGA Total | GPT-6-Luna FIXED | GPT-6-Luna DREAM | GPT-6-Sol FIXED | GPT-6-Sol DREAM | |
| 20 | 515 | +0.3 | 0.0 | 0.0 | 0.0 |
| 40 | 977 | +2.0 | +1.0 | +1.0 | +1.0 |
| 60 | 1446 | +6.3 | +4.7 | +2.7 | +1.3 |
| 80 | 1964 | +5.0 | +3.3 | +2.3 | +0.3 |
| 100 | 2332 | +12.0 | +8.7 | +5.3 | +3.0 |
| All | 7234 | +25.7 | +17.7 | +11.3 | +5.7 |
Table 4. 2D-BPP: BRKGA total bins and excess bins () for FIXED/DREAM, averaged over three runs. Each size has 100 instances (500 total). Shading marks the smaller excess within each model, including ties.
Local reference solvers. Greedy uses nearest-neighbor construction from city zero for TSP and selects feasible items by value-to-weight ratio for KP. POMO is evaluated locally using the official TSP50 (Python version) and KP200 (legacy version) checkpoints fixed before testing. We use greedy decoding from a single start at index zero without augmentation, following the MCTS-AHD setting (Zheng et al. [36]). POMO runs on NVIDIA RTX PRO 6000 Blackwell GPUs. CPU reference evaluations run on a dual-socket AMD EPYC 9555 machine.
LKH-3.0.13 uses ten runs, with at most 1,000 trials and a 60-second limit per run.7 Distances are scaled by and rounded for search, while reported tour lengths are recomputed from the original coordinates.
OR-Tools 9.14 uses its multidimensional branch-and-bound knapsack solver with one capacity constraint and a 60-second limit.8 The stored binary inputs are scaled by to obtain exact integer representations. Assertions verify exact representability and compliance with the signed 64-bit range. OR-Tools certifies optimality for every evaluated KP instance.
Experimental Details and Cost Accounting
For each task and search method, we select the solver with the highest development score in each run and evaluate it directly on the test set.
Baseline coverage. Baseline coverage is determined by the problem-specific implementations publicly released by the original authors. Accordingly, we include EoH, ReEvo, and MCTS-AHD for constructive TSP; MCTS-AHD for KP; EoH for FSSP; and FunSearch, EoH, ReEvo, and MCTS-AHD for OBPP. Model names indicate the LLM backbones used for algorithm discovery.
Rounds and execution. For root generation in each round, the discovery agent receives only the same task specification and reference program. Evaluation caches are maintained separately for each round. Search experience therefore transfers across rounds through the learned policy. In the paired GPT-6-Luna TSP and 2D-BPP comparisons, FIXED and DREAM share the initial solver. FIXED permits up to concurrent development requests, whereas DREAM issues one request at a time.
Cost accounting. Token counts cover recorded LLM usage for solver development and policy learning, including root generation and repair calls. Invalid and failed search steps still consume the search budget. A single search step may involve multiple LLM calls when repairs are needed, so we report search steps and token usage separately.
Result aggregation. All reported metrics are computed from complete per-instance evaluation results. Reference gaps are calculated for each instance before averaging. For results reported over three runs, we average the run-level means with equal weight. In particular, the overall GPT-6-Luna TSP gap averages all 4,015 test instances equally within each run, then averages across the three runs. Table highlighting is based on values rounded to the displayed precision.
Development-curve aggregation. Figures 3 and 6 show the mean best-so-far development score across three runs at each search step. Invalid candidates and failed evaluations leave each run’s best score unchanged. Within each method, the final best scores of runs that end earlier are carried forward until the longest run ends. Shading indicates standard error across the three runs.
Extended Results
This appendix supplements § 4 with detailed comparisons and analyses of search behavior. We first report TSP solution quality and running times, FSSP results alongside CP baselines, and OBPP performance across item counts and bin capacities. We then examine the effects of policy replay and the cost penalty on 2D-BPP, including paired comparisons and token expenditure. Finally, we use real search trajectories to illustrate how learned policies extend promising branches, revisit alternatives, and decide when to stop.
TSP Solution Quality and Running Times
Table 6 reports mean reference gaps and per-instance solve times for the same solvers and test instances as Table 1. GPT-6-Luna results average three runs per method. With this backbone, DREAM achieves lower mean gaps and shorter mean solve times than FIXED on all five test groups. Reported times measure solver evaluation. For LLM-generated solvers, timing covers only the solver call and excludes process startup and CPU queueing.
| LLM Model | Method | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | Gap (%) | Time (s) | TSPLIB Gap (%) | TSPLIB Time (s) |
| LKH ref. | – | 0.479 | – | 1.83 | – | 6.06 | – | 31.3 | – | 29.1 | |
| Greedy | 22.622 | 0.0002 | 24.936 | 0.0005 | 25.711 | 0.0013 | 25.903 | 0.0239 | 24.332 | 0.0065 | |
| POMO{sup}†` | 0.383 | 0.0005 | 2.999 | 0.0004 | 20.447 | 0.0008 | 46.135 | 0.0024 | 23.923 | 0.0502 | |
| GPT-4o-mini | EoH | 16.822 | 0.001 | 19.114 | 0.0025 | 20.842 | 0.0085 | 22.209 | 0.0502 | 21.060 | 0.0096 |
| ReEvo | 22.622 | 0.0006 | 24.936 | 0.0014 | 25.711 | 0.005 | 25.903 | 0.0467 | 24.332 | 0.0084 | |
| MCTS-AHD | 15.906 | 0.0049 | 18.832 | 0.0203 | 21.166 | 0.0858 | 22.549 | 0.527 | 19.306 | 0.0936 | |
| FIXED | 22.622 | 0.0006 | 24.936 | 0.0013 | 25.711 | 0.0044 | 25.903 | 0.0528 | 24.332 | 0.0095 | |
| Dream-COP | 14.379 | 0.0006 | 15.952 | 0.0013 | 17.557 | 0.0044 | 19.149 | 0.0526 | 17.390 | 0.0105 | |
| GPT-6-Luna | EoH | 16.819 | 0.0716 | 18.955 | 0.599 | 20.305 | 5.32 | 21.099 | 98.3 | 20.658 | 12.2 |
| ReEvo | 15.682 | 0.602 | 18.493 | 0.62 | 20.292 | 0.834 | 21.440 | 5.04 | 20.782 | 1.01 | |
| MCTS-AHD | 15.959 | 0.21 | 17.929 | 1.92 | 19.143 | 18.5 | 19.728 | 488 | 20.226 | 64 | |
| FIXED | 15.275 | 0.0807 | 17.432 | 0.668 | 18.495 | 6.21 | 19.378 | 137 | 18.355 | 14.5 | |
| Dream-COP | 9.489 | 0.0622 | 11.316 | 0.398 | 12.361 | 3.56 | 13.209 | 80.3 | 11.984 | 10.3 |
Table 6. TSP mean gaps (%) to LKH and per-instance solve times (seconds). Bold indicates the lowest gap among non-reference methods. Shading indicates the lowest gap within each LLM backbone, including ties at displayed precision. †POMO’s synthetic-instance times are GPU batch inference times divided by batch size.
POMO runs on the GPU, while the other methods run on CPUs. For synthetic instances, POMO’s per-instance time is the synchronized batch inference time divided by the actual batch size, with up to 60 instances per batch. TSPLIB instances are evaluated individually because their sizes vary. Reported times correspond to the tours used for gap calculation and are averaged equally over instances within each test group. GPT-6-Luna results then average the three run-level means. Times are reported with up to three significant figures and at most four decimal places.
Larger and structured instances. The selected solvers are evaluated on all 1,000 released 500-city MCTS-AHD instances and the 15 TSPLIB instances listed in Table 7. Each constructor runs to completion without a CPU or wall-clock cutoff. Evaluation permits at most 50 concurrent instances per solver.
| Instance | LKH (ref.) Length | LKH (ref.) Gap (%) | Greedy Length | Greedy Gap (%) | POMO Length | POMO Gap (%) | EoH Length | EoH Gap (%) | ReEvo Length | ReEvo Gap (%) | MCTS-AHD Length | MCTS-AHD Gap (%) | FIXED Length | FIXED Gap (%) | Dream-COP Length | Dream-COP Gap (%) | |
| ts225 | 225 | 126643 | 162697.0 | 28.469 | 182934.0 | 44.449 | 145719.7 | 15.063 | 146561.7 | 15.728 | 152030.7 | 20.047 | 148299.7 | 17.101 | 141445.0 | 11.688 | |
| rat99 | 99 | 1211 | 1558.0 | 28.654 | 1332.0 | 9.992 | 1424.7 | 17.644 | 1437.7 | 18.717 | 1544.0 | 27.498 | 1456.0 | 20.231 | 1355.7 | 11.946 | |
| bier127 | 127 | 118282 | 135848.0 | 14.851 | 134250.0 | 13.500 | 150183.0 | 26.970 | 133371.3 | 12.757 | 137271.7 | 16.055 | 132660.3 | 12.156 | 127479.7 | 7.776 | |
| lin318 | 318 | 42029 | 54019.0 | 28.528 | 59945.0 | 42.628 | 50308.0 | 19.698 | 53587.7 | 27.502 | 51346.7 | 22.170 | 51914.0 | 23.519 | 48487.0 | 15.366 | |
| eil51 | 51 | 426 | 511.0 | 19.953 | 429.0 | 0.704 | 487.0 | 14.319 | 475.3 | 11.581 | 487.0 | 14.319 | 513.3 | 20.501 | 479.7 | 12.598 | |
| d493 | 493 | 35002 | 43395.0 | 23.979 | 55695.0 | 59.119 | 41895.3 | 19.694 | 40781.0 | 16.510 | 41178.0 | 17.645 | 41451.7 | 18.427 | 38873.0 | 11.059 | |
| kroB100 | 100 | 22141 | 29158.0 | 31.692 | 22904.0 | 3.446 | 26536.3 | 19.852 | 27662.7 | 24.939 | 26526.0 | 19.805 | 26782.3 | 20.963 | 24791.0 | 11.969 | |
| kroC100 | 100 | 20749 | 26327.0 | 26.883 | 22999.0 | 10.844 | 24969.3 | 20.340 | 24882.7 | 19.922 | 25009.3 | 20.5 | 25009.3 | 20.5 | 22639.3 | 9.110 | |
| ch130 | 130 | 6110 | 7578.0 | 24.026 | 6530.0 | 6.874 | 7073.7 | 15.772 | 7319.0 | 19.787 | 7052.0 | 15.417 | 6966.0 | 14.010 | 6914.0 | 13.159 | |
| pr299 | 299 | 48191 | 62738.0 | 30.186 | 70010.0 | 45.275 | 59506.3 | 23.480 | 58868.0 | 21.156 | 58805.3 | 22.026 | 57259.3 | 18.817 | 53958.3 | 11.968 | |
| fl417 | 417 | 11861 | 14598.0 | 23.076 | 15072.0 | 27.072 | 15062.3 | 26.990 | 16228.7 | 36.824 | 14634.3 | 23.382 | 15013.0 | 26.574 | 13552.3 | 14.260 | |
| kroA150 | 150 | 26524 | 33612.0 | 26.723 | 29279.0 | 10.387 | 31333.3 | 17.378 | 32189.7 | 21.361 | 31163.7 | 17.492 | 30266.7 | 14.110 | 29894.0 | 12.705 | |
| pr264 | 264 | 49135 | 57963.0 | 17.967 | 63174.0 | 28.572 | 65800.0 | 23.293 | 58899.7 | 19.873 | 58717.0 | 19.501 | 58391.7 | 18.839 | 55638.7 | 13.236 | |
| pr226 | 226 | 80369 | 94277.0 | 17.305 | 87381.0 | 8.725 | 99820.0 | 24.404 | 96235.7 | 19.742 | 97972.3 | 21.903 | 89031.7 | 10.779 | 88338.3 | 9.916 | |
| pr439 | 439 | 107217 | 131549.0 | 22.694 | 157886.0 | 47.258 | 133991.7 | 24.972 | 133310.7 | 24.337 | 134668.0 | 25.603 | 133283.0 | 24.311 | 121153.0 | 12.998 | |
| Mean | – | 46392.7 | 57055.2 | 24.332 | 60654.7 | 23.923 | 56590.2 | 20.658 | 55454.1 | 20.782 | 55893.7 | 20.226 | 54476.4 | 18.355 | 51666.6 | 11.984 |
Table 7. TSPLIB tour lengths and gaps (%) to LKH, which matches the optima on all 15 instances. LLM-based results use GPT-6-Luna and average three runs per method. Bold indicates the best non-reference result. Shading indicates the best LLM-based result, including ties at displayed precision.
Before inference, TSPLIB coordinates are translated by subtracting the minimum on each axis and uniformly scaled by the larger of the two coordinate ranges. Inference uses a single start at city zero without augmentation. Returned tours are evaluated on the original coordinates using TSPLIB EUC_2D nearest-integer edge costs. LKH uses the same edge costs. Gaps are computed relative to LKH tour lengths, which match the official optima on all 15 instances.9
FSSP Evaluation and CP Solver Settings
tbl:8 reports mean makespan and per-instance solve time for the FSSP methods, including the two CP baselines. Dream achieves the lowest mean makespan among the LLM-based methods with both GPT-4o-mini and GPT-6-Luna.
We choose OR-Tools CP-SAT 9.14.6206 and OptalCP 2026.4.0 as CP baselines. Both enforce the permutation flow-shop constraints: every job visits the machines in order, operations on each machine cannot overlap, and all machines follow the same job permutation. CP-SAT represents the shared job order using pairwise ordering variables across machines. OptalCP enforces it through a same-sequence constraint on the machine sequence variables. Both minimize makespan and use the same deterministic NEH solution as a warm start. The supplied Taillard reference upper bounds are used only for reporting.
Each CP solver uses one thread per instance and has a 300-second time limit. Timing starts after model construction and NEH initialization. Every returned permutation is independently checked,
| Taillard | UB | CP-SAT | CP-SAT Time | OptalCP | OptalCP Time | GPT-4o-mini EoH | GPT-4o-mini EoH Time | GPT-4o-mini FIXED | GPT-4o-mini FIXED Time | GPT-4o-mini Dream-COP | GPT-4o-mini Dream-COP Time | GPT-6-Luna EoH | GPT-6-Luna EoH Time | GPT-6-Luna FIXED | GPT-6-Luna FIXED Time | GPT-6-Luna Dream-COP | GPT-6-Luna Dream-COP Time | ||
| 20 | 5 | 1222.5 | 1221.9 | 1221.9 | 5.87 | 1221.9 | 270 | 1223.6 | 0.280 | 1223.6 | 0.282 | 1222.4 | 0.270 | 1222.4 | 0.356 | 1222.4 | 2.09 | 1222.4 | 0.536 |
| 20 | 10 | 1513.7 | 1516.5 | 1521.1 | 245 | 1521.1 | 300 | 1516.2 | 0.330 | 1516.2 | 0.327 | 1515.5 | 0.313 | 1515.2 | 0.444 | 1521.1 | 2.68 | 1514.2 | 0.639 |
| 20 | 20 | 2235.1 | 2246.8 | 2253.3 | 300 | 2253.3 | 300 | 2237.9 | 0.494 | 2237.9 | 0.501 | 2239.6 | 0.438 | 2237.1 | 0.691 | 2239.3 | 4.34 | 2236.1 | 0.920 |
| 50 | 5 | 2736.4 | 2736.4 | 2736.4 | 13.7 | 2736.4 | 182 | 2736.5 | 2.19 | 2736.5 | 2.23 | 2736.4 | 1.94 | 2736.4 | 2.21 | 2736.6 | 5.12 | 2736.7 | 2.51 |
| 50 | 10 | 2997.6 | 3037.8 | 3011.7 | 300 | 3011.7 | 300 | 3000.1 | 2.77 | 3000.1 | 2.95 | 3001.5 | 2.55 | 2998.6 | 2.99 | 3000.7 | 3.87 | 2997.5 | 3.16 |
| 50 | 20 | 3731.0 | 3943.0 | 3854.4 | 300 | 3854.4 | 300 | 3756.3 | 4.78 | 3756.3 | 5.19 | 3761.6 | 4.67 | 3751.8 | 5.64 | 3761.1 | 6.90 | 3750.4 | 5.47 |
| 100 | 5 | 5246.9 | 5246.4 | 5245.5 | 153 | 5245.5 | 300 | 5245.0 | 12.5 | 5245.0 | 13.7 | 5244.5 | 13.5 | 5244.8 | 14.8 | 5244.8 | 26.1 | 5244.5 | 13.9 |
| 100 | 10 | 5630.0 | 5752.0 | 5652.6 | 300 | 5652.6 | 300 | 5637.9 | 18.5 | 5637.9 | 18.8 | 5635.2 | 19.3 | 5641.0 | 20.4 | 5631.2 | 33.7 | 5631.3 | 19.9 |
| 100 | 20 | 6362.6 | 6634.4 | 6538.7 | 300 | 6538.7 | 300 | 6380.3 | 37.3 | 6380.3 | 35.1 | 6384.4 | 36.2 | 6369.0 | 34.0 | 6375.3 | 40.8 | 6350.8 | 39.0 |
| 200 | 10 | 10673.0 | 10803.8 | 10755.5 | 300 | 10755.5 | 300 | 10700.4 | 60 | 10700.4 | 60 | 10676.6 | 60 | 10687.5 | 60 | 10682.4 | 60 | 10677.3 | 60 |
| 200 | 20 | 11373.6 | 11752.4 | 11726.5 | 300 | 11726.5 | 300 | 11440.3 | 60 | 11430.9 | 60 | 11411.7 | 60 | 11441.2 | 60 | 11406.2 | 60 | 11376.2 | 60 |
| Mean | 4883.9 | 4990.1 | 229 | 4956.1 | 287 | 4897.7 | 18.1 | 4896.8 | 18.1 | 4893.6 | 18.1 | 4895.0 | 18.3 | 4892.8 | 22.4 | 4885.2 | 18.8 |
caption: FSSP mean makespan and per-instance solve time (seconds) for jobs and machines. Bold indicates the lowest makespan among non-reference methods. Shading indicates the lowest makespan within each LLM backbone, including ties at displayed precision.
:::
and its makespan is recomputed using the original processing times. Both solvers return feasible solutions on all 110 instances. CP-SAT proves optimality on 30 instances, and OptalCP on five.
Paired FIXED/DREAM comparison. For each LLM backbone, we pair FIXED and DREAM makespans by instance ID on all 110 instances under the same 60-second GLS limit. A win for DREAM means a lower makespan than FIXED on the same instance; ties require exact equality of integer makespans. With GPT-6-Luna, DREAM records 59 wins, 40 ties, and 11 losses, with a mean makespan reduction of 7.61. With GPT-4o-mini, DREAM yields 38 wins, 46 ties, and 26 losses, with a mean reduction of 3.25. Excluding ties, separate two-sided exact sign tests of equal win and loss probabilities give on 70 non-tied instances for GPT-6-Luna and on 64 for GPT-4o-mini.
Online Bin Packing Results
Table 9 breaks down OBPP performance by item count and bin capacity. DREAM achieves its largest gains over FIXED on longer sequences at . At , it reduces the mean gap from 3.501% to 0.459%, using 122 fewer bins per instance on average. At , the methods obtain similar bin counts close to the volume lower bound.
Comparing Replay Quality Measures
To complement the analysis of delayed improvements in § 4.4, we compare the final programs discovered under the two replay quality measures. As in the main-text analysis, we use GPT-6-Luna and one completed run per measure and problem, with the same root programs and budgets for solver discovery and policy learning. Only the quality term changes from the top-five mean in Eq. (3) to the best revealed score , while the request penalty remains unchanged. For each run, we select the solver with the highest development score and evaluate it directly on the test set.
For TSP and KP, this comparison uses 3,000 test instances per problem with . For OBPP, FSSP, and 2D-BPP, we use 30, 110, and 500 test instances, respectively. Table 10 reports the best development score and test performance for each quality measure. improves both metrics on TSP, FSSP, and 2D-BPP and matches on KP at the displayed precision. These final results complement the higher delayed-improvement rates with in Figure 5, supporting its use for guiding exploration toward better programs.
| Problem | Best dev. score | Test metric | Test result | ||
| TSP | 0.903628 | 0.911622 | Tour length | 9.7762 | 9.2079 |
| KP | 0.401890 | 0.401890 | Value | 39.25212 | 39.25212 |
| OBPP | 0.986612 | 0.984093 | Gap (%) | 1.1238 | 1.1988 |
| FSSP | 0.549795 | 0.549904 | Gap (%) | 0.1864 | 0.0412 |
| 2D-BPP | 0.752726 | 0.755089 | Bins | 14.520 | 14.504 |
Table 10. Comparison of replay quality terms and with GPT-6-Luna, using one run per quality term and problem. Test results use the solver with the highest development score in each run. Bold marks the better value within each problem and metric, including ties at displayed precision.
2D-BPP Ablations and Costs
Shared paired-comparison protocol. All paired 2D-BPP comparisons use the same 500 BWMV instances with a 60-second budget per instance. For each method, is the mean bin count across three runs on instance . Each instance contributes one comparison, and a lower mean bin count is better. Ties are identified by exact equality of the integer bin-count sums across the three runs. We use two-sided exact sign tests of equal win and loss probabilities, excluding ties.
Paired FIXED/DREAM comparison. For GPT-6-Luna, DREAM uses . We define as the bin-count reduction achieved by DREAM on instance . Positive, zero, and negative values give a DREAM win, tie, and loss, respectively. Table 11 shows more wins than losses for DREAM with both backbones. Across the 500 instances, the total savings average 8 bins with GPT-6-Luna and 5.7 bins with GPT-6-Sol over three runs.
| Model | W/T/L | Mean | |
| GPT-6-Luna | 20/479/1 | 0.016 | |
| GPT-6-Sol | 13/486/1 | 0.011 | 0.002 |
Table 11. Paired 2D-BPP comparison using three-run mean bin counts. W/T/L counts wins, ties, and losses for DREAM. Mean reports bins saved per instance by DREAM. The -values are from two-sided exact sign tests excluding ties.
No replay protocol. No replay uses the same historical-evidence interface, history eligibility rule, and search budget (, ) as DREAM. At each policy update, it makes a single LLM call to generate one policy and deploys it at after syntax and interface checks. It performs no replay or reward-based ranking. DREAM instead uses four proposal calls and replay-based selection of the policy–parameter pair, as described in Appendix § 6.
Paired replay comparison. Across three runs, DREAM at achieves a higher mean final development score than No replay (0.75451 versus 0.75327) with fewer search steps (189.7 versus 233.3). On the 500 test instances, the paired comparison records 15 wins, 483 ties, and 2 losses for DREAM. A two-sided exact sign test on the 17 non-tied instances gives .
Cost-penalty sensitivity. Table 12 shows the effect of the cost penalty on development quality, search steps, and test bin counts. Among the evaluated settings, achieves the highest development score and the lowest mean test bin count. Increasing to reduces mean search steps from 189.7 to 106.0 (44.1%), with an increase of 0.010 bins per test instance.
| Method | Dev. score | Steps | Test bins | |
| FIXED | – | 0.75290 | 240.0 | 14.51933 |
| DREAM | 0.75417 | 204.7 | 14.51333 | |
| DREAM | 0.75451 | 189.7 | 14.50333 | |
| DREAM | 0.75209 | 106.0 | 14.51333 |
Table 12. Effect of the cost penalty on 2D-BPP with GPT-6-Luna. Entries average three runs. Dev. score reports the final best development score. Steps counts discovery requests. Test bins reports the mean bin count over 500 test instances. Bold marks the best value in each metric.
Search trajectories. In Figure 6, development requests are indexed in submission order, excluding root initialization. The horizontal axis begins at step 24 to highlight progress beyond the initial search phase. Figure 10 shows that DREAM at surpasses FIXED’s final mean development score by the third round, while using fewer search steps per round thereafter.
Token costs. Figure 11 decomposes recorded token usage into solver discovery and policy learning. Across the three penalty settings, mean policy-learning usage ranges from 2.68 to 3.06 M tokens. Algorithm-discovery usage falls from 8.26 M at to 3.92 M at . Most of the reduction therefore comes from solver discovery.
Figure 11. Recorded token usage for 2D-BPP with GPT-6-Luna. Stacked bars show three-run means, split into algorithm discovery (unhatched) and policy learning (hatched). Whiskers indicate sample standard deviation of total tokens. Dots show total tokens for individual runs.
At , DREAM reduces discovery tokens by 54.7% relative to FIXED. Adding 2.68 M policy-learning tokens brings its mean total to 6.61 M, compared with 8.67 M for FIXED. The reduction in discovery expenditure exceeds the policy-learning cost by 2.06 M tokens, yielding a net reduction of 23.8%.
One cancelled call in a FIXED run has no recorded usage. As a sensitivity check, assigning it the 0.029 M tokens recorded for its successful retry increases the three-run FIXED mean by 0.11%.
Learned Policies in Real Search
We examine TSP and 2D-BPP search trajectories to illustrate how learned policies adapt branch continuation, revisiting, and stopping to observed progress. Both cases use GPT-6-Luna and show the ninth search round. Node labels indicate the order of search steps, and branch depth counts successive revisions from the root.
TSP: extending a productive branch and stopping early. Figure 12 follows the policy in Listing 1, deployed in round nine with . Before deployment, replay on eight historical trees yields a mean top-five score of 0.901947, compared with 0.901457 for FIXED. Mean replay expenditure falls from 20.375 to 16.875 steps per tree, a reduction of 17.18%.
Figure 12. TSP search round 9 with GPT-6-Luna. (a) Mean top-five score and replay steps on eight historical trees before deployment. (b) Development scores along the first branch up to the program selected for testing. (c) Complete search tree, with nodes labeled by search step. The policy stops after 19 of the 24 available steps.
In real search, the policy extends the first branch beyond FIXED’s four-step depth limit. The development score falls from 0.899847 at depth four to 0.899567 at depth five, then recovers to 0.901768 at depth six. The policy’s recent-gain and stagnation conditions permit continuation through this temporary decline. At depth eleven, the branch reaches 0.912170. This node contains the solver with the highest development score in the run, which is selected for testing.
After two failed evaluations on this branch, the policy explores three other branches before returning to the first at step 17. It then opens two further branches. With all six branches opened and no continuation exceeding its threshold, the policy stops after 19 search steps, leaving five steps unused.
2D-BPP: reallocating a full search budget. At , the policy uses all 24 search steps but distributes them unevenly across branches (Figure 7). It ranks branch extensions using recent gains, stagnation, and quality gaps, and compares them with starting a new branch. The resulting branch lengths are (8, 6, 1, 3, 5, 1), whereas FIXED assigns four steps to each of six branches.
The first branch reaches 0.751209 at depth four (step 12) and improves to 0.753565 at depth five. After two lower-scoring revisions, the policy pauses this branch and allocates steps 16–19 elsewhere. Returning at step 20 produces a score of 0.755089 at depth eight, the highest development score in the run. The corresponding solver is selected for testing.
Programs Discovered by Dream
We provide the DREAM programs for each task. Each listing reproduces the complete evaluated source, with line wrapping for presentation only. TSP and KP include their construction wrappers. OBPP and FSSP expose learned components to the fixed controllers described in Appendix B. The 2D-BPP program implements the full solver. Each listing shows a single selected program; its performance below refers to that program. Table 1 averages three runs for GPT-6-Luna TSP, and Table 4 averages three runs for each 2D-BPP method and backbone.
Constructive TSP
The GPT-6-Luna program in Listing 2 combines short lookahead with residual minimum-spanning-tree and greedy completion costs. It solves the final ten or fewer unvisited cities by subset dynamic programming. Its mean gap to LKH is 11.00% over all 4,015 test instances, comprising 4,000 synthetic instances and 15 TSPLIB instances.
Listing 2: DREAM’s constructive TSP program.
import numpy as np
import math
def select_next_node(current_node, destination_node, unvisited_nodes, distance_matrix):
nodes = sorted(unvisited_nodes)
if len(nodes) == 1:
return int(nodes[0])
# Solve the small endgame exactly, including the final return to the start.
if len(nodes) <= 10:
count = len(nodes)
full_mask = (1 << count) - 1
memo = {}
def tail_cost(last_index, remaining_mask):
key = (last_index, remaining_mask)
if key in memo:
return memo[key]
if remaining_mask == 0:
return float(distance_matrix[nodes[last_index], destination_node])
best = float("inf")
for next_index in range(count):
bit = 1 << next_index
if remaining_mask & bit:
cost = float(distance_matrix[nodes[last_index], nodes[next_index]])
cost += tail_cost(next_index, remaining_mask ^ bit)
if cost < best:
best = cost
memo[key] = best
return best
best_cost = float("inf")
best_city = nodes[0]
for index, city in enumerate(nodes):
cost = float(distance_matrix[current_node, city])
cost += tail_cost(index, full_mask ^ (1 << index))
if cost < best_cost:
best_cost = cost
best_city = city
return int(best_city)
current_distances = np.asarray(distance_matrix[current_node, nodes], dtype=float)
order = np.argsort(current_distances, kind="stable")
shortlist_size = min(len(nodes), max(3, int(math.ceil(math.sqrt(len(nodes))))))
candidates = [nodes[int(i)] for i in order[:shortlist_size]]
def residual_mst_cost(vertices):
count = len(vertices)
if count <= 1:
return 0.0
used = [False] * count
best_edge = [float("inf")] * count
best_edge[0] = 0.0
total = 0.0
for _ in range(count):
chosen = -1
chosen_cost = float("inf")
for i in range(count):
if not used[i] and best_edge[i] < chosen_cost:
chosen = i
chosen_cost = best_edge[i]
if chosen < 0:
break
used[chosen] = True
total += chosen_cost
source = vertices[chosen]
for i in range(count):
if not used[i]:
edge = float(distance_matrix[source, vertices[i]])
if edge < best_edge[i]:
best_edge[i] = edge
return total
def greedy_tail_cost(start, vertices):
remaining = set(vertices)
last = start
total = 0.0
while remaining:
nxt = min(remaining, key=lambda node: (float(distance_matrix[last, node]),
node))
total += float(distance_matrix[last, nxt])
remaining.remove(nxt)
last = nxt
total += float(distance_matrix[last, destination_node])
return total
best_key = None
best_city = candidates[0]
for city in candidates:
first = float(distance_matrix[current_node, city])
remaining = [node for node in nodes if node != city]
if remaining:
second = min(float(distance_matrix[city, node]) for node in remaining)
next_city = min(remaining, key=lambda node: (float(distance_matrix[city,
node]), node))
after_next = [node for node in remaining if node != next_city]
if after_next:
third = min(float(distance_matrix[next_city, node]) for node in
after_next)
else:
third = float(distance_matrix[next_city, destination_node])
else:
second = third = 0.0
residual_vertices = list(remaining)
if destination_node not in residual_vertices:
residual_vertices.append(destination_node)
global_tail = residual_mst_cost(residual_vertices)
completion_tail = greedy_tail_cost(city, remaining)
score = first + 0.12 * second + 0.04 * third + 0.12 * global_tail + 0.18 * completion_tail
key = (score, first, city)
if best_key is None or key < best_key:
best_key = key
best_city = city
return int(best_city)
def solve(instance, time_budget, seed):
points = np.asarray(instance["points"], dtype=float)
n = len(points)
distance_matrix = np.sqrt(np.sum((points[:, None, :] - points[None, :, :]) ** 2, axis=-1))
tour = [0]
unvisited = set(range(1, n))
while unvisited:
node = select_next_node(tour[-1], 0, unvisited.copy(), distance_matrix.copy())
if isinstance(node, (bool, np.bool_)) or not isinstance(node, (int, np.integer)) or node not in unvisited:
raise ValueError("select_next_node must return an unvisited integer city")
node = int(node)
tour.append(node)
unvisited.remove(node)
return tour
Constructive Knapsack
The GPT-6-Luna selector in Listing 3 uses a beam search ordered by value density and guided by an optimistic completion bound. It returns the first item of the best retained partial solution, and the constructor repeats this decision as capacity decreases. Its mean value is 52.1798 over all 4,000 test instances at the four reported item counts.
Listing 3: DREAM’s constructive knapsack program.
import numpy as np
def select_next_item(remaining_capacity, weights, values):
n = len(weights)
if n == 0:
raise ValueError("No items are available")
capacity = float(remaining_capacity)
feasible = np.flatnonzero(weights <= capacity)
if not len(feasible):
# Tolerance-feasible fallback required when no strictly feasible item exists.
return int(np.argmin(weights))
# Process promising items first so the beam explores useful combinations early.
density = values / np.maximum(weights, 1e-15)
order = np.argsort(-density, kind="mergesort")
sorted_weights = weights[order]
sorted_values = values[order]
sorted_density = density[order]
# Each state is (used weight, collected value, first selected current index).
# A beam bound adds the fractional-knapsack value available from later items.
beam = [(0.0, 0.0, -1)]
beam_width = 128
for position in range(n):
item_weight = float(sorted_weights[position])
item_value = float(sorted_values[position])
current_index = int(order[position])
candidates = []
for used_weight, total_value, first_item in beam:
candidates.append((used_weight, total_value, first_item))
new_weight = used_weight + item_weight
if new_weight <= capacity:
new_first = current_index if first_item < 0 else first_item
candidates.append((new_weight, total_value + item_value, new_first))
next_density = float(sorted_density[position + 1]) if position + 1 < n else 0.0
remaining_total_weight = float(np.sum(sorted_weights[position + 1:]))
ranked = []
for used_weight, total_value, first_item in candidates:
residual = max(0.0, capacity - used_weight)
# The fractional bound is inexpensive and admissible for the remaining
items.
optimistic_extra = min(residual, remaining_total_weight) * next_density
ranked.append((-(total_value + optimistic_extra), -total_value,
used_weight, first_item, used_weight, total_value, first_item))
ranked.sort()
beam = [(row[4], row[5], row[6]) for row in ranked[:beam_width]]
best = min(beam, key=lambda state: (-state[1], state[0], state[2] if state[2] >= 0
else n))
if best[2] < 0:
return int(feasible[0])
return int(best[2])
def solve(instance, time_budget, seed):
weights = np.asarray(instance["weights"], dtype=float)
values = np.asarray(instance["values"], dtype=float)
remaining_capacity = float(instance["capacity"])
epsilon = float(instance["feasibility_epsilon"])
indices = np.arange(len(weights))
selected = []
while len(weights) and remaining_capacity + epsilon > float(weights.min()):
item = select_next_item(remaining_capacity=remaining_capacity,
weights=weights.copy(), values=values.copy())
if isinstance(item, (bool, np.bool_)) or not isinstance(item, (int,
np.integer)) or not 0 <= item < len(weights):
raise ValueError("select_next_item must return an integer index in the
current arrays")
item = int(item)
if not remaining_capacity + epsilon > weights[item]:
raise ValueError("Selected item exceeds remaining capacity")
selected.append(int(indices[item]))
remaining_capacity -= weights[item]
weights = np.delete(weights, item)
values = np.delete(values, item)
indices = np.delete(indices, item)
return selected
Online Bin Packing
The GPT-6-Luna scoring rule in Listing 4 penalizes small positive residual capacity and rewards exact fits. It uses 1,297.0 bins on average over the 30 test instances, with a mean gap of 1.199% to the lower bound. The benchmark supplies _obpp_pack, the fixed controller that applies these scores to feasible bins.
Listing 4: Dream’s online bin-packing scoring rule and controller entry point.
import numpy as np
def score(item, bins):
remaining = np.asarray(bins, dtype=float) - float(item)
scores = -remaining.copy()
# Future items have a typical size near the Weibull scale (45).
# Smoothly discourage positive scraps smaller than that size.
scrap_limit = 45.0
tiny_scrap = (remaining > 1e-9) & (remaining < scrap_limit)
deficit = (scrap_limit - remaining[tiny_scrap]) / scrap_limit
scores[tiny_scrap] -= 3.0 * scrap_limit * deficit * deficit
# Exact fits avoid consuming capacity that could serve later items.
scores[remaining <= 1e-9] += 100.0
return scores
def solve(instance, time_budget, seed):
return _obpp_pack(instance, seed, score)
Flow-Shop Scheduling
The GPT-6-Luna program in Listing 5 traces a critical path to prioritize jobs and machines for perturbation. Its mean gap to the upper bounds is 0.0412% over 110 test instances. The benchmark supplies _fssp_gls, the fixed NEH-initialized guided local search controller that calls get_matrix_and_jobs.
import numpy as np
def get_matrix_and_jobs(current_sequence, time_matrix, m, n):
times = np.asarray(time_matrix, dtype=float)
jobs_count, machines = times.shape
if jobs_count == 0 or machines == 0:
return times.copy(), []
# Keep one valid occurrence of each job in sequence order.
seq = []
seen = set()
for value in current_sequence:
job = int(value)
if 0 <= job < jobs_count and job not in seen:
seq.append(job)
seen.add(job)
if not seq:
seq = list(range(jobs_count))
# Completion times support a backward trace of one critical path.
completion = np.zeros((len(seq), machines), dtype=float)
for i, job in enumerate(seq):
for k in range(machines):
above = completion[i - 1, k] if i > 0 else 0.0
left = completion[i, k - 1] if k > 0 else 0.0
completion[i, k] = max(above, left) + times[job, k]
path_counts = np.zeros(jobs_count, dtype=float)
critical_machines = np.zeros(machines, dtype=float)
path_positions = np.zeros(len(seq), dtype=bool)
i, k = len(seq) - 1, machines - 1
while i >= 0 and k >= 0:
job = seq[i]
path_positions[i] = True
path_counts[job] += 1.0
critical_machines[k] += 1.0
if i == 0 and k == 0:
Listing 5: Dream’s flow-shop perturbation rule and controller entry point.
break
above = completion[i - 1, k] if i > 0 else -1.0
left = completion[i, k - 1] if k > 0 else -1.0
if above >= left:
i -= 1
else:
k -= 1
# Add a modest boundary signal for jobs directly adjacent to critical
# operations; these jobs often determine whether a critical block can move.
boundary = np.zeros(jobs_count, dtype=float)
for pos, on_path in enumerate(path_positions):
if on_path:
if pos > 0 and not path_positions[pos - 1]:
boundary[seq[pos - 1]] += 0.5
if pos + 1 < len(seq) and not path_positions[pos + 1]:
boundary[seq[pos + 1]] += 0.5
total_load = np.sum(times, axis=1)
critical_load = times @ critical_machines
mean_load = float(np.mean(critical_load)) + 1e-12
priority = (2.5 * path_counts + boundary + critical_load / mean_load
+ 0.15 * total_load / (float(np.mean(total_load)) + 1e-12))
count = min(5, jobs_count)
pool_size = min(jobs_count, max(count, min(16, 3 * count)))
order = sorted(range(jobs_count), key=lambda j: (priority[j], path_counts[j],
total_load[j]), reverse=True)
pool = np.asarray(order[:pool_size], dtype=int)
weights = np.asarray([1.0 + max(0.0, priority[j]) for j in pool], dtype=float)
weights = np.maximum(weights, 1e-9)
probabilities = weights / np.sum(weights)
chosen = np.random.choice(pool, size=count, replace=False, p=probabilities).tolist()
# Concentrate perturbation on machines appearing on the path, with a small
# shoulder on neighboring machines to expose adjacent bottleneck effects.
focus = critical_machines.copy()
for machine in range(machines):
amount = critical_machines[machine]
if amount > 0.0:
if machine > 0:
focus[machine - 1] += 0.25 * amount
if machine + 1 < machines:
focus[machine + 1] += 0.25 * amount
if not np.any(focus > 0.0):
focus[-1] = 1.0
focus /= max(float(np.max(focus)), 1e-12)
modified = times.copy()
for job in chosen:
# Jobs with greater path participation receive a stronger perturbation.
job_strength = 0.85 + 0.15 * min(1.0, path_counts[int(job)] / max(1.0,
float(np.max(path_counts))))
factor = float(np.random.uniform(1.15, 1.45)) * job_strength
scale = np.maximum(focus, 0.10 * (focus > 0.0))
modified[int(job), :] *= 1.0 + (factor - 1.0) * scale
modified = np.nan_to_num(modified, nan=0.0, posinf=1.0e12, neginf=0.0)
modified = np.maximum(modified, 0.0)
return modified, [int(job) for job in chosen]
def solve(instance, time_budget, seed):
return _fssp_gls(instance, time_budget, seed, get_matrix_and_jobs)
Complete Two-Dimensional Bin Packing
The full solver in Listing 6 was discovered with GPT-6-Sol at . It combines free-rectangle placement with randomized item orders and partial repacking. Accepted layouts are checked for feasibility, and a valid fallback is maintained throughout the search. It uses 7,240 bins over the 500 BWMV instances, or 14.480 bins per instance.
Listing 6: DREAM’s complete two-dimensional bin-packing solver.
import random
import time
def _valid(placements, items, width, height):
if not isinstance(placements, list) or len(placements) != len(items):
return False
bins = {}
for i, placement in enumerate(placements):
if not isinstance(placement, (list, tuple)) or len(placement) != 3:
return False
if any(type(value) is not int or value < 0 for value in placement):
return False
bid, x, y = placement
w, h = items[i]
if x + w > width or y + h > height:
return False
for ox, oy, ow, oh in bins.get(bid, ()):
if x < ox + ow and ox < x + w and y < oy + oh and oy < y + h:
return False
bins.setdefault(bid, []).append((x, y, w, h))
return True
def _split_free(free, x, y, w, h):
pieces = []
right = x + w
top = y + h
for fx, fy, fw, fh in free:
fr = fx + fw
ft = fy + fh
if right <= fx or fr <= x or top <= fy or ft <= y:
pieces.append((fx, fy, fw, fh))
continue
if x > fx:
pieces.append((fx, fy, x - fx, fh))
if right < fr:
pieces.append((right, fy, fr - right, fh))
if y > fy:
pieces.append((fx, fy, fw, y - fy))
if top < ft:
pieces.append((fx, top, fw, ft - top))
result = []
for i, rect in enumerate(pieces):
ax, ay, aw, ah = rect
contained = False
for j, other in enumerate(pieces):
if i == j:
continue
bx, by, bw, bh = other
if bx <= ax and by <= ay and ax + aw <= bx + bw and ay + ah <= by + bh:
if rect != other or j < i:
contained = True
break
if not contained:
result.append(rect)
return result
def _contact(x, y, w, h, rectangles, width, height):
value = (h if x == 0 else 0) + (h if x + w == width else 0)
value += (w if y == 0 else 0) + (w if y + h == height else 0)
for ox, oy, ow, oh in rectangles:
if x + w == ox or ox + ow == x:
value += max(0, min(y + h, oy + oh) - max(y, oy))
if y + h == oy or oy + oh == y:
value += max(0, min(x + w, ox + ow) - max(x, ox))
return value
def _build(order, kept, base, items, width, height, style, deadline):
placements = [None] * len(items)
bins = []
remap = {}
for i in kept:
if time.monotonic() >= deadline:
return None
old_bid, x, y = base[i]
if old_bid not in remap:
remap[old_bid] = len(bins)
bins.append([[(0, 0, width, height)], 0, []])
bid = remap[old_bid]
w, h = items[i]
bins[bid][0] = _split_free(bins[bid][0], x, y, w, h)
bins[bid][1] += w * h
bins[bid][2].append((x, y, w, h))
placements[i] = [bid, x, y]
for i in order:
if time.monotonic() >= deadline:
return None
w, h = items[i]
area = w * h
best_key = None
options = []
for bid, (free, used, rectangles) in enumerate(bins):
if time.monotonic() >= deadline:
return None
for fx, fy, fw, fh in free:
if w > fw or h > fh:
continue
waste = fw * fh - area
short = min(fw - w, fh - h)
if style == 0:
key = (-used, waste, short)
elif style == 1:
key = (waste, -used, short)
elif style == 2:
key = (short, -used, waste)
else:
key = (-used, short, waste)
if best_key is None or key < best_key:
best_key = key
options = []
if key == best_key:
for x in (fx, fx + fw - w):
for y in (fy, fy + fh - h):
options.append((bid, x, y))
if not options:
bid = len(bins)
bins.append([[(0, 0, width, height)], 0, []])
x = y = 0
else:
bid, x, y = min(
options,
key=lambda p: (-_contact(p[1], p[2], w, h, bins[p[0]][2], width,
height), p[2], p[1], p[0]),
)
bins[bid][0] = _split_free(bins[bid][0], x, y, w, h)
bins[bid][1] += area
bins[bid][2].append((x, y, w, h))
placements[i] = [bid, x, y]
return placements, [entry[1] for entry in bins]
def _order(indices, items, mode, rng, noise):
priorities = []
for i in indices:
w, h = items[i]
if mode == 0:
priority = w * h
elif mode == 1:
priority = max(w, h)
elif mode == 2:
priority = w + h
elif mode == 3:
priority = w
elif mode == 4:
priority = h
else:
priority = min(w, h)
if noise:
priority *= 0.65 + 0.70 * rng.random()
priorities.append((-priority, i))
priorities.sort()
return [i for _, i in priorities]
def solve(instance, time_budget, seed, lower_bound=0):
start = time.monotonic()
width, height = instance['bin_size']
items = instance['items']
count = len(items)
if count == 0:
return []
fallback = [[i, 0, 0] for i in range(count)]
if not _valid(fallback, items, width, height):
raise ValueError('No feasible single-item-bin fallback')
best = fallback
areas = [w * h for w, h in items]
best_numerator = sum(area * area for area in areas)
best_bins = count
rng = random.Random(seed)
deadline = start + max(0.0, float(time_budget)) * 0.85
iteration = 0
while time.monotonic() < deadline:
mode = iteration % 6
style = iteration % 4 if iteration < 16 else rng.randrange(4)
if iteration >= 16 and iteration % 5 != 0:
occupied = {}
for i, placement in enumerate(best):
bid = placement[0]
occupied[bid] = occupied.get(bid, 0) + areas[i]
ranked = sorted(occupied, key=lambda bid: (occupied[bid], bid))
pivot = rng.choice(ranked[:min(4, len(ranked))])
selected = {pivot}
target = min(len(ranked), 1 + rng.randrange(4))
``
others = [bid for bid in ranked if bid != pivot]
rng.shuffle(others)
selected.update(others[:target - 1])
kept = [i for i in range(count) if best[i][0] not in selected]
removed = [i for i in range(count) if best[i][0] in selected]
order = _order(removed, items, mode, rng, True)
result = _build(order, kept, best, items, width, height, style, deadline)
else:
order = _order(range(count), items, mode, rng, iteration >= 6)
result = _build(order, (), best, items, width, height, style, deadline)
if result is None:
break
candidate, used_areas = result
numerator = sum(area * area for area in used_areas)
bin_count = len(used_areas)
if numerator * best_bins > best_numerator * bin_count:
if _valid(candidate, items, width, height):
best = candidate
best_numerator = numerator
best_bins = bin_count
iteration += 1
return best if _valid(best, items, width, height) else fallbackReferences
- [1]Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.arxiv.org/abs/1811.06128
- [2]Edmund K. Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12):1695–1724, 2013. doi: 10.1057/jors.2013.71.DOI
- [3]Michel Gendreau and Jean-Yves Potvin (eds.). Handbook of Metaheuristics, volume 272 of International Series in Operations Research & Management Science. Springer, Cham, third edition, 2019. doi: 10.1007/978-3-319-91086-4.
- [4]José Fernando Gonçalves and Mauricio G.C. Resende. A biased random key genetic algorithm for 2d and 3d bin packing problems. International Journal of Production Economics, 145(2):500–510, October 2013. ISSN 0925-5273. doi: 10.1016/j.ijpe.2013.04.019.DOI
- [5]Oğuzhan Gungordu, Siheng Xiong, and Faramarz Fekri. PathWise: Planning through world model for automated heuristic design via self-evolving LLMs. In Proceedings of the 43rd International Conference on Machine Learning, volume 306, pp. 37779–37816. PMLR, 2026.arxiv.org/abs/2601.20539
- [6]Priyanshu Gupta, Shashank Kirtania, Ananya Singha, Sumit Gulwani, Arjun Radhakrishna, Gustavo Soares, and Sherry Shi. MetaReflection: Learning instructions for language agents using past reflections. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 8369–8385. Association for Computational Linguistics, 2024. doi: 10.18653/v1/2024.emnlp-main.477.DOI
- [7]David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In Advances in Neural Information Processing Systems, volume 31, 2018.arxiv.org/abs/1809.01999
- [8]Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In International Conference on Learning Representations, 2020.arxiv.org/abs/1912.01603
- [9]Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In International Conference on Learning Representations, 2021.arxiv.org/abs/2010.02193
- [10]Danijar Hafner, Jurgis Pasukonis, Jimmy Ba, and Timothy Lillicrap. Mastering diverse control tasks through world models. Nature, 640:647–653, 2025. doi: 10.1038/s41586-025-08744-2.DOI
- [11]Ziyao Huang, Weiwei Wu, Kui Wu, Wei-Bin Lee, and Jianping Wang. CALM: Co-evolution of algorithms and language model for automatic heuristic design. In International Conference on Learning Representations, 2026.arxiv.org/abs/2505.12285
- [12]Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. Sequential Model-Based Optimization for General Algorithm Configuration. In Learning and Intelligent Optimization, volume 6683 of Lecture Notes in Computer Science, pp. 507–523. Springer Berlin Heidelberg, 2011. doi: 10.1007/978-3-642-25566-3_40.DOI
- [13]Yuichi Inoue, Kou Misaki, Yuki Imaizuku, Su Kuroki, Taishi Nakamura, and Takuya Akiba. Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search. In Advances in Neural Information Processing Systems, volume 38, pp. 35448–35484. Curran Associates, Inc., 2025. doi: 10.52202/085713-1191.
- [14]Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.arxiv.org/abs/1704.01665
- [15]Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, 2019.arxiv.org/abs/1803.08475
- [16]Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms, volume 21 of Algorithms and Combinatorics. Springer, Berlin, Heidelberg, sixth edition, 2018. doi: 10.1007/978-3-662-56039-6.DOI
- [17]Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21188–21198. Curran Associates, Inc., 2020.
- [18]Fei Liu, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Algorithm Evolution Using Large Language Model. arXiv preprint arXiv:2311.15249, 2023.arxiv.org/abs/2311.15249
- [19]Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 32201–32223. PMLR, 2024.arxiv.org/abs/2401.02051
- [20]Yihong Liu, Junyi Li, Hongyu Lu, Wayne Xin Zhao, and Ji-Rong Wen. Experience-driven reflective co-evolution of prompts and heuristics for autonomous algorithm design. In Findings of the Association for Computational Linguistics: ACL 2026, pp. 4981–4995. Association for Computational Linguistics, 2026. doi: 10.18653/v1/2026.findings-acl.245.DOI
- [21]Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Thomas Stützle, and Mauro Birattari. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58, 2016. doi: 10.1016/j.orp.2016.09.002.
- [22]Haoze Lv, Ning Lu, Ziang Zhou, Yew-Soon Ong, and Shengcai Liu. AHD Agent: Agentic reinforcement learning for automatic heuristic design. arXiv preprint arXiv:2605.08756, 2026.arxiv.org/abs/2605.08756
- [23]Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-Refine: Iterative Refinement with Self-Feedback. In Advances in Neural Information Processing Systems, volume 36, pp. 46534–46594. Curran Associates, Inc., 2023. doi: 10.52202/075280-2019.DOI
- [24]Manuj Malik, Jiaman Zhou, Shashank Reddy Chirra, and Zhiguang Cao. PyVRP⁺: LLM-driven metacognitive heuristic evolution for hybrid genetic search in vehicle routing problems. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, pp. 2800–2808, 2026. doi: 10.65109/isfv2587.DOI
- [25]Silvano Martello and Daniele Vigo. Exact solution of the two-dimensional finite bin packing problem. Management Science, 44(3):388–399, 1998. doi: 10.1287/mnsc.44.3.388.DOI
- [26]Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
- [27]Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625:468–475, 2024. doi: 10.1038/s41586-023-06924-6.
- [28]Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, pp. 8634–8652. Curran Associates, Inc., 2023. doi: 10.52202/0725280-0377.arxiv.org/abs/2303.11366
- [29]Thomas Stützle and Manuel López-Ibáñez. Automated design of metaheuristic algorithms. In Michel Gendreau and Jean-Yves Potvin (eds.), Handbook of Metaheuristics, volume 272 of International Series in Operations Research & Management Science, pp. 541–579. Springer, Cham, third edition, 2019. doi: 10.1007/978-3-319-91086-4_17.DOI
- [30]Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Proceedings of the Seventh International Conference on Machine Learning, pp. 216–224, 1990. doi: 10.1016/B978-1-55860-141-3.50030-4.DOI
- [31]Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993.DOI
- [32]Niki van Stein and Thomas Bäck. LLaMEA: A large language model evolutionary algorithm for automatically generating metaheuristics. IEEE Transactions on Evolutionary Computation, 29(2):331–345, 2025. doi: 10.1109/TEVC.2024.3497793.DOI
- [33]Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jink yoo Park, and Guojie Song. ReEvo: Large language models as hyper-heuristics with reflective evolution. In Advances in Neural Information Processing Systems, volume 37, pp. 43571–43608. Curran Associates, Inc., 2024. doi: 10.52202/079017-1381.DOI
- [34]Ni Zhang, Zhiguang Cao, Jianan Zhou, Cong Zhang, and Yew-Soon Ong. An agentic framework with LLMs for solving complex vehicle routing problems. In International Conference on Learning Representations, 2026.arxiv.org/abs/2510.16701
- [35]Wenqi Zhang, Ke Tang, Hai Wu, Mengna Wang, Yongliang Shen, Guiyang Hou, Zegi Tan, Peng Li, Yueting Zhuang, and Weiming Lu. Agent-Pro: Learning to evolve via policy-level reflection and optimization. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5348–5375. Association for Computational Linguistics, 2024. doi: 10.18653/v1/2024.acl-long.292.DOI
- [36]Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte Carlo tree search for comprehensive exploration in LLM-based automatic heuristic design. In Proceedings of the 42nd International Conference on Machine Learning, volume 267, pp. 78338–78373. PMLR, 2025.arxiv.org/abs/2501.08603
- [37]Jianghan Zhu, Cong Zhang, Rongjie Zhu, Chi Zhang, and Zhiguang Cao. SimpleEvol: Efficient intelligence conversion via less human prior in automated heuristic design. In Advances in Neural Information Processing Systems, 2026a.
- [38]Rongjie Zhu, Cong Zhang, and Zhiguang Cao. Refining hybrid genetic search for CVRP via reinforcement learning-finetuned LLM. In International Conference on Learning Representations, 2026b.arxiv.org/abs/2510.11121









