Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World

1 INTRODUCTION

• COPs support efficient resource use, but growing problem size and complexity make optimal solutions computationally demanding, while heuristic development requires expertise and repeated experimentation.These demands motivate automating algorithm design across problems.Source: §1 · p. 1
• The central question is how historical trajectories and outcomes can help learn better policies for allocating search among branches with differing improvement, failure, and stagnation patterns.The allocation of search budget and when to stop influence the quality of discovered algorithms.Source: §1 · pp. 1–2
• Dream-COP replays recorded search trees to evaluate executable policies that choose revision branches, branch openings, and stopping decisions before guiding real search.Replay evaluates the quality of revealed programs and the number of search steps used; new real searches expand the experience world.Source: §1 · p. 2
• Across five COPs, Dream-COP discovers better algorithms with fewer search requests than fixed exploration and achieves superior performance to existing LLM-based AHD methods.Cross-problem experiments also find that learned policies remain effective when guiding discovery on another COP.Source: §1 · p. 2

2 RELATED WORK

• Dream-COP makes search-budget allocation itself an object of program discovery: executable policies select revision branches and stopping decisions, then historical replay evaluates them before deployment.The replay compares the quality of revealed programs with the number of search steps used.Source: §2 · p. 3
• Other experience-driven methods adapt prompts, model parameters, or interactive generation behavior; Dream-COP learns a separate tree-search controller while keeping LLM weights fixed.The passage contrasts Dream-COP with EvoPH, CALM, RFTHGS, and AHD Agent (Huang et al., 2026; Zhu et al., 2026b; Lv et al., 2026).Source: §2 · p. 3
• Language-agent methods use textual feedback and reflection to guide behavior, whereas Dream-COP tests policies on the same historical trees using revealed-program quality and replay-step count.The described approaches include trajectory reflection and learned instructions (Zhang et al., 2024; Gupta et al., 2024).Source: §2 · p. 3
• Unlike learned world models, Dream-COP's internal environment uses transitions and outcomes directly from recorded program revisions, enabling replay without new generation or evaluation.The selected policy then controls subsequent real search, whose new trees supply further experience.Source: §2 · p. 3

3 DREAM-COP

• The discovery agent generates heuristic components or complete solvers and records their development as search trees that become the policy agent’s experience world.The two agents use the same LLM backbone.Source: §3 · p. 3, Figure 2 · p. 4

3.1 THE DISCOVERY AGENT AND SEARCH TREES

• Each search round starts from a feasible root; the discovery agent revises a selected parent using task information, branch hypotheses, and evaluation feedback, recording alternative revision branches.Every request consumes a search step, including requests that fail to produce a valid revision.Source: §3.1 · p. 3

3.2 EXECUTABLE POLICIES FOR BUDGET ALLOCATION

• An executable policy maps the revealed tree, remaining budget, and action history to opening a branch, extending a leaf, or stopping; learned policies can redistribute the fixed per-round budget.FIXED opens B branches and allocates L steps to each, while DREAM begins with that policy in its first round.Source: §3.2 · p. 4

3.3 HISTORICAL TREES AS AN EXPERIENCE WORLD

• Replay reveals recorded tree transitions in the policy’s chosen order, exposing stored feasibility and quality outcomes without new solver generation or evaluation.Policies see only outcomes revealed by their own actions, and replay ends at stopping, budget exhaustion, or full tree revelation.Source: §3.3 · pp. 4–5

3.4 REPLAY OBJECTIVE

• The replay objective rewards high-quality revealed programs while penalizing replay steps, averaging the top five feasible development scores to assess quality.The fixed coefficient λ sets the trade-off between normalized development quality and search cost; eligible trees receive equal weight.Source: §3.4 · p. 5

3.5 THE POLICY AGENT: LEARNING FROM REPLAY

• After each round, the policy agent proposes executable policies through four sequential LLM calls, uses replay feedback to refine proposals, and deploys the valid policy pair with the highest mean replay reward.LLM weights remain unchanged, and the selected policy stays fixed throughout the next real search round.Source: §3.5 · pp. 5–6

4 EXPERIMENTS

• The experiments cover constructive TSP and KP, online bin packing, flow-shop scheduling, and complete-solver generation for offline 2D-BPP.They also examine policy transfer among TSP, OBPP, and FSSP.Source: §4 · p. 6

4.1 EVALUATION SETTINGS

• DREAM and FIXED share a 240-search-step maximum overall, but DREAM adaptively allocates 24 steps per round and may stop early.Both use the same discovery agent and run for 10 rounds; the highest-development-score solver is frozen for testing.Source: §4.1 · p. 7

4.2 PERFORMANCE ACROSS PROBLEMS AND SIZES

• DREAM achieves the lowest mean tour length among compared LLM-based AHD methods across four synthetic TSP sizes and TSPLIB, reducing the GPT-6-Luna mean gap to LKH from FIXED’s 17.65% to 11.60%.It uses 13.75% fewer search requests; Figure 3 plots TSP development score averaged over three runs.Source: §4.2 · p. 7, Figure 3 · p. 7
• DREAM matches OR-Tools optimal values to displayed precision at all four KP sizes, using 17.5% fewer search requests than FIXED.At N = 500, MCTS-AHD and FIXED retain gaps of 0.020% and 0.010%, respectively.Source: §4.2 · p. 7
• For OBPP, the reported aggregate comparison averages all 30 test instances across both capacities against the volume lower bound.Figure 4 reports FSSP mean gap to the Taillard reference upper bound by size, with lower values better.Source: §4.2 · p. 7, Figure 4 · p. 8

N FunSearch EoH ReEvo MCTS FIXED DREAM

• Table 3 compares OBPP mean gaps to the volume lower bound by item count at C = 100; lower is better.Shading marks the best method at each size.Source: Table 3 · p. 8
• The table’s stated metric is mean gap (%) to the volume lower bound.Source: Table 3 · p. 8
• The comparison is restricted to GPT-6-Luna and capacity C = 100.Source: Table 3 · p. 8

N BRKGA GPT-6-Luna GPT-6-Sol Total FIXED DREAM FIXED DREAM

• On OBPP, DREAM reduces the gap from FIXED’s 2.112% to 1.199% while using 42.5% fewer search steps.The improvement is concentrated in longer item sequences at capacity 100.Source: N BRKGA GPT-6-Luna GPT-6-Sol Total… · p. 8

4.3 DESIGNING COMPLETE 2D-BPP SOLVERS

• DREAM saves eight bins over FIXED on the 500-instance 2D-BPP test set with GPT-6-Luna, with most improvement on larger instances.All selected solvers produce feasible layouts on every instance.Source: §4.3 · p. 8, Table 4 · p. 8

4.4 EXPERIMENTAL ANALYSIS

• Q5 yields higher delayed-improvement rates than Q1 on all five problems, with better test performance on TSP, FSSP, and 2D-BPP and identical KP results.Delayed improvements are counted per 100 discovery requests after at least three consecutive requests without a new best.Source: Figure 5 · p. 9, §4.4 · p. 9
• At λ = 10−3, DREAM uses 106 search steps on average versus FIXED’s 240, with mean test bin counts of 14.51333 versus 14.51933.Raising λ from 10−5 to 10−3 reduces mean search steps by 44.1%; including policy learning, recorded tokens fall by 23.8% relative to FIXED.Source: §4.4 · p. 9, Figure 6 · p. 9
• DREAM reaches a higher development score with fewer search steps than No replay and records 15 wins, 483 ties, and 2 losses across 500 test instances.Excluding ties, the two-sided exact sign test gives p = 0.00235.Source: §4.4 · pp. 9–10, Figure 6 · p. 9
• Within a 24-step round, DREAM varies effort across six branches, revisits the first branch at step 20, and finds the run’s highest-scoring program at depth eight.FIXED assigns four steps per branch.Source: Figure 7 · p. 10, §4.4 · p. 10

4.5 CROSS-PROBLEM POLICY TRANSFER

• Transferred policies improve test quality over FIXED in all three directions while using 25.0–64.2% fewer search steps; on OBPP, transfer reduces the mean gap from 1.1988% to 1.0637%.The tested directions are TSP → OBPP, OBPP → FSSP, and FSSP → TSP.Source: §4.5 · p. 10

5 CONCLUSION

• Dream-COP learns search policies through historical replay to guide algorithm discovery for combinatorial optimization problems.Recorded transitions and outcomes support policy evaluation and refinement through replay without additional solver generation or evaluation.Source: §5 · pp. 10–11
• Across five COPs, Dream-COP discovers better algorithms with fewer search requests than fixed exploration for both heuristic components and complete solvers.The replay ablation supports evaluating candidate policies in the experience world before deployment.Source: §5 · p. 11
• Learned search policies remain effective beyond the problems on which they were learned.Cross-problem experiments show that historical search experience can provide reusable guidance for algorithm discovery.Source: §5 · p. 11

A ALGORITHM AND AGENT DETAILS

• Across rounds, each completed search contributes a tree to the accumulated history; eligible trees support policy replay before the next search round.The procedure finally selects the solver with the highest development score and evaluates it on the test set.Source: A ALGORITHM AND AGENT DETAILS · p. 14
• At each decision, a policy returns ROOT to open a branch, a current leaf to extend one, or None to stop the round.The observation includes revealed tree structure, program scores, branch status, quality measures, and remaining budget; future outcomes are excluded.Source: A ALGORITHM AND AGENT DETAILS · p. 14
• A history tree becomes eligible after enough recorded search steps; with B = 6 and L = 4, five steps suffice, including failures and without requiring improvement.Learning uses all eligible trees accumulated so far, retaining the incumbent policy and parameter when none are available.Source: A ALGORITHM AND AGENT DETAILS · p. 15
• Replay evaluates each generated policy at five α values on eligible trees, and valid policy–parameter pairs compete by replay reward.Four sequential LLM calls each request four distinct policies; proposals receive feedback from replay results and generation or execution failures.Source: A ALGORITHM AND AGENT DETAILS · p. 15

A.1 CORE DISCOVERY-AGENT PROMPT

• The discovery prompt supplies the parent program, branch-local feedback, and evaluation settings so the agent can implement a revision.The search policy selects the parent program; required interfaces and evaluation protocols are specified separately.Source: Figure 8 · p. 15, §A.1 · p. 16

A.2 CORE POLICY-LEARNING PROMPT

• The policy-learning prompt updates context across calls with the policy source, historical records, and replay feedback; calls focus on stopping, branching, allocation, and revisiting.The best valid proposal so far is supplied for refinement, or the incumbent if no valid proposal exists.Source: §A.2 · p. 16, Figure 9 · p. 16

A.3 AN EXAMPLE OF A LEARNED POLICY

• The example learned policy continues branches showing recent gains and revisits paused branches whose gains and quality justify further exploration.It ranks eligible branches using gains, stagnation, and quality gaps; otherwise it opens a branch if below B or stops, while α adjusts its thresholds.Source: §A.3 · p. 17

• Reference gaps are computed against LKH for TSP, certified OR-Tools optima for KP, the volume lower bound for OBPP, and supplied Taillard upper bounds for FSSP.A negative FSSP gap means the makespan is below its reference upper bound.Source: B BENCHMARK TASKS, INTERFACES, AND… · p. 17
• TSP evolves a next-city selector in a fixed constructor, tested on 4,000 synthetic instances and 15 TSPLIB instances against LKH tour lengths.The selector receives the current and destination cities, unvisited cities, and distance matrix, then returns one unvisited city.Source: B BENCHMARK TASKS, INTERFACES, AND… · p. 17
• For knapsack, the evolved selector returns an index of an item fitting remaining capacity; the constructor removes it, updates capacity, and repeats until none fits, then checks the selected subset against the original instance.Test results report total selected value without normalization; the official checker uses a feasibility tolerance of 10−6. OR-Tools enforces original capacities without this tolerance and certifies optimality for every evaluated KP instance.Source: B BENCHMARK TASKS, INTERFACES, AND… · pp. 17–19
• OBPP evolves a bin-scoring rule for sequential placement, evaluated on 30 instances using percentage excess bin count over the volume lower bound.The controller places each arriving item in the feasible bin with the highest score, breaking ties by supplied order.Source: B BENCHMARK TASKS, INTERFACES, AND… · p. 18
• For FSSP, an evolved perturbation function guides swap and insertion moves in a fixed NEH-initialized GLS controller; testing covers 110 Taillard instances, ten per job–machine size, with a 1,000-iteration cap.GLS allows up to 30 seconds during development and 60 seconds during testing, with the iteration cap applying in both phases.Source: B BENCHMARK TASKS, INTERFACES, AND… · p. 19
• 2D-BPP evolves complete solvers that return rectangle placements, evaluated on 500 BWMV instances by used-bin count against a BRKGA reference.The checker verifies integer coordinates, original orientations, bin containment, and non-overlap; Table 4 reports excess bins relative to the reference.Source: B BENCHMARK TASKS, INTERFACES, AND… · p. 19

C EXPERIMENTAL DETAILS AND COST ACCOUNTING

• FIXED and DREAM share an initial solver in paired TSP and 2D-BPP comparisons; DREAM allocates search steps sequentially, while FIXED permits concurrent requests.Both methods use the same discovery agent and ten rounds; baseline coverage follows publicly released implementations.Source: C EXPERIMENTAL DETAILS AND COST… · pp. 19–20
• Token counts include solver development and policy learning, while failed steps consume budget; search steps and tokens are reported separately.Three-run results average run-level means equally, and development curves carry earlier-stopping runs forward with ±1 standard-error shading.Source: C EXPERIMENTAL DETAILS AND COST… · p. 20

D EXTENDED RESULTS

• The extended appendix covers TSP quality and running times, FSSP comparisons with CP solvers, OBPP performance, replay-quality measures, search costs, and real trajectories.The trajectory analysis illustrates branch continuation, revisiting alternatives, and stopping decisions.Source: D EXTENDED RESULTS · p. 20

D.1 TSP SOLUTION QUALITY AND RUNNING TIMES

• TSP timing averages per-instance solver calls; POMO uses batched GPU inference, while other methods run on CPUs.The appendix also evaluates 1,000 released 500-city instances and 15 TSPLIB instances without a CPU or wall-clock cutoff.Source: §D.1 · p. 20
• DREAM achieves lower mean gaps and shorter mean solve times than FIXED in all five GPT-6-Luna TSP test groups.Table 6 reports mean gaps to LKH and per-instance solver-call times.Source: §D.1 · p. 20, Table 6 · p. 21

D.2 FSSP EVALUATION AND CP SOLVER SETTINGS

• DREAM achieves the lowest mean makespan among LLM-based FSSP methods with both GPT-4o-mini and GPT-6-Luna.Table 8 includes mean makespan and per-instance solve time; the CP baselines return feasible solutions on all 110 instances.Source: §D.2 · pp. 21–22, Table 8 · p. 22
• With GPT-6-Luna, DREAM records 59 wins, 40 ties, and 11 losses against FIXED, reducing mean makespan by 7.61 on paired FSSP instances.For GPT-4o-mini, the comparison yields 38 wins, 46 ties, and 26 losses, with a mean reduction of 3.25; the exact sign-test p-value is 0.169.Source: §D.2 · p. 22

D.3 ONLINE BIN PACKING RESULTS

• At N = 10,000 and C = 100, DREAM reduces the OBPP mean gap from 3.501% to 0.459%, using 122 fewer bins per instance on average.At C = 500, the methods obtain similar bin counts close to the volume lower bound.Source: Table 9 · p. 22, §D.3 · p. 22

D.4 COMPARING REPLAY QUALITY MEASURES

• Q5 improves development and test metrics over Q1 on TSP, FSSP, and 2D-BPP, and matches Q1 on KP at displayed precision.The comparison uses one run per measure and problem, with the same root programs and budgets; replay quality is the changed component.Source: §D.4 · pp. 22–23, Table 10 · p. 23

D.5 2D-BPP ABLATIONS AND COSTS

• DREAM records more wins than losses against FIXED on 2D-BPP; against No replay, it raises mean final development score to 0.75451 from 0.75327 using 189.7 versus 233.3 steps.The paired FIXED comparison averages 8 bins saved with GPT-6-Luna and 5.7 with GPT-6-Sol across 500 instances.Source: Table 11 · p. 23, §D.5 · p. 23
• Among tested penalties, λ = 10^-5 yields the highest development score and lowest mean test bin count; λ = 10^-3 cuts mean search steps by 44.1% with a 0.010-bin increase.DREAM at λ = 10^-5 surpasses FIXED’s final mean development score by the third round while using fewer steps per round thereafter.Source: Table 12 · p. 24, §D.5 · p. 24, Figure 10 · p. 24
• At λ = 10^-3, DREAM reduces discovery tokens by 54.7% and total recorded tokens by 23.8% relative to FIXED, after including policy-learning costs.Figure 11 separates discovery and policy-learning token usage; a sensitivity check imputing a cancelled FIXED call raises its mean by 0.11%.Source: Figure 11 · p. 24, §D.5 · p. 24

D.6 LEARNED POLICIES IN REAL SEARCH

• On TSP, replay across eight historical trees yields a mean top-five score of 0.901947 versus FIXED’s 0.901457, with 17.18% fewer replay steps.In live search, the first branch recovers after a temporary score decline, reaches 0.912170 at depth eleven, and supplies the run’s highest-development-score solver.Source: Figure 12 · p. 25, §D.6 · p. 25
• After two failed evaluations, the TSP policy explores alternatives, returns to the first branch, then stops after 19 of 24 steps when no continuation exceeds its threshold.It leaves five steps unused after opening all six branches.Source: §D.6 · p. 25
• At 2D-BPP λ = 10^-5, the policy distributes all 24 steps unevenly across branches; returning to its first branch reaches 0.755089, selected for testing.Branch lengths are (8, 6, 1, 3, 5, 1), rather than FIXED’s four steps per branch.Source: §D.6 · p. 25

E PROGRAMS DISCOVERED BY DREAM

• The released listings provide complete evaluated source: TSP and KP include wrappers, OBPP and FSSP expose components to fixed controllers, and 2D-BPP supplies a full solver.Each listing shows one selected program; its performance is reported below that program.Source: E PROGRAMS DISCOVERED BY DREAM · p. 26

E.1 CONSTRUCTIVE TSP

• 11.00% was the mean gap to LKH across 4,015 TSP test instances for a program combining short lookahead, residual minimum-spanning-tree and greedy completion costs, and exact endgame subset dynamic programming.The test set comprised 4,000 synthetic instances and 15 TSPLIB instances.Source: §E.1 · p. 26

E.2 CONSTRUCTIVE KNAPSACK

• 52.1798 was the mean value across 4,000 test instances at four reported item counts for a knapsack selector using value-density beam search and an optimistic completion bound.The constructor repeatedly selects an item as capacity decreases.Source: §E.2 · p. 28

E.3 ONLINE BIN PACKING

• 1,297.0 bins on average and a 1.199% mean gap to the lower bound were achieved over 30 online bin-packing test instances by a scoring rule that penalizes small positive residual capacity and rewards exact fits.The benchmark supplies _obpp_pack, the fixed controller that applies the scores to feasible bins.Source: §E.3 · p. 29

E.4 FLOW-SHOP SCHEDULING

• 0.0412% was the mean gap to upper bounds over 110 flow-shop test instances for a perturbation rule that traces a critical path to prioritize jobs and machines.The benchmark supplies _fssp_gls, the fixed NEH-initialized guided local search controller that calls get_matrix_and_jobs.Source: §E.4 · p. 30

E.5 COMPLETE TWO-DIMENSIONAL BIN PACKING

• 7,240 bins (14.480 per instance) were used across 500 BWMV instances by a full solver combining free-rectangle placement, randomized item orders, and partial repacking.Discovered with GPT-6-Sol at λ = 0; accepted layouts are checked for feasibility, with a valid fallback maintained throughout the search.Source: §E.5 · p. 32
• Item ordering assigns priorities from the selected mode, sorts them, and returns the resulting item indices.The snippets also show that ordering receives a random-number generator and noise parameter.Source: §E.5 · p. 34
• The solver repeats search until its deadline, cycling through four styles for the first 16 iterations before choosing styles randomly.The solve routine accepts a time budget and seed, and checks the deadline during its search.Source: §E.5 · p. 34