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

Kuan Xu; Jianming Wang; Ni Zhang; Yaoxin Wu; Yong Wang; Zhiguang Cao

cs.LGOct 27, 2026

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

Authors: Kuan Xu, Jianming Wang, Ni Zhang, Yaoxin Wu, Yong Wang, Zhiguang Cao

Organizations: Singapore Management University · University of Science and Technology of China · Eindhoven University of Technology · Central South University

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.

Figures & tables

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.

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.

LLM Model	Method	$N=50$		$N=100$		$N=200$		$N=500$		TSPLIB
LLM Model	Method	Obj. $\downarrow$	Gap (%)	Obj. $\downarrow$	Gap (%)	Obj. $\downarrow$	Gap (%)	Obj. $\downarrow$	Gap (%)	Obj. $\downarrow$	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

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 ( Kwon et al., 2020 ) as baselines. LLM-based results are averaged over 3 runs. Bold: best non-reference result; shading: best LLM result within each model, including ties.

LLM Model	Method	$N=50$ , $W=12.5$		$N=100$ , $W=25$		$N=200$ , $W=25$		$N=500$ , $W=25$
LLM Model	Method	Obj. $\uparrow$	Gap (%)	Obj. $\uparrow$	Gap (%)	Obj. $\uparrow$	Gap (%)	Obj. $\uparrow$	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

Table 2: Constructive KP: mean objective value and gap (%) to the OR-Tools optimum by item count

N

and capacity

W

, 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.

Figure 3: TSP development score using GPT-6-Luna, averaged over three independent runs per method.

Figure 5: Delayed improvements per 100 discovery requests under

Q_{1}

and

Q_{5}

with GPT-6-Luna.

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 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.

Transfer	Method	Dev. score $\uparrow$	Test metric $\downarrow$	Search steps $\downarrow$
TSP $\rightarrow$ OBPP	Fixed	0.98142	2.1124	240
	Dream	0.98409	1.1988	138
	Transferred Dream	0.98710	1.0637	86
OBPP $\rightarrow$ FSSP	Fixed	0.54973	0.1940	240
	Dream	0.54990	0.0412	176
	Transferred Dream	0.54981	0.0872	174

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.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure 8: Core discovery-agent prompt modules. Brackets denote dynamic inputs.

Panel of Figure 9 — Figure 9: Core policy-learning prompt modules. Brackets denote dynamic inputs.

LLM Model	Method	$N=50$		$N=100$		$N=200$		$N=500$		TSPLIB
LLM Model	Method	Gap (%)	Time (s)	Gap (%)	Time (s)	Gap (%)	Time (s)	Gap (%)	Time (s)	Gap (%)	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 †	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

Appendix

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.

Instance	$N$	LKH (ref.)	Greedy		POMO		EoH		ReEvo		MCTS-AHD		Fixed		Dream-COP
Instance	$N$	LKH (ref.)	Length	Gap (%)	Length	Gap (%)	Length	Gap (%)	Length	Gap (%)	Length	Gap (%)	Length	Gap (%)	Length	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

Appendix

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.

							GPT-4o-mini						GPT-6-Luna
$N$	$M$	Taillard UB	CP-SAT		OptalCP		EoH		Fixed		Dream-COP		EoH		Fixed		Dream-COP
		$C_{\max}$	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time	$C_{\max}$	Time
20	5	1222.5	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	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	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	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

Appendix

Table 8: FSSP mean makespan and per-instance solve time (seconds) for

N

jobs and

M

machines. Bold indicates the lowest makespan among non-reference methods. Shading indicates the lowest makespan within each LLM backbone, including ties at displayed precision.

$N$	$C$	Ref. LB		FunSearch		EoH		ReEvo		MCTS-AHD		Fixed		Dream-COP
$N$	$C$	Bins	Gap (%)	Bins	Gap (%)	Bins	Gap (%)	Bins	Gap (%)	Bins	Gap (%)	Bins	Gap (%)	Bins	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

Appendix

Table 9: OBPP mean bin counts and gaps (%) to the volume lower bound by item count

N

and bin capacity

C

. 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.

Problem	Best dev. score $\uparrow$		Test metric	Test result
Problem	$Q_{1}$	$Q_{5}$	Test metric	$Q_{1}$	$Q_{5}$
TSP	0.903628	0.911622	Tour length $\downarrow$	9.7762	9.2079
KP	0.401890	0.401890	Value $\uparrow$	39.25212	39.25212
OBPP	0.986612	0.984093	Gap (%) $\downarrow$	1.1238	1.1988
FSSP	0.549795	0.549904	Gap (%) $\downarrow$	0.1864	0.0412
2D-BPP	0.752726	0.755089	Bins $\downarrow$	14.520	14.504

Appendix

Table 10: Comparison of replay quality terms

Q_{1}

and

Q_{5}

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.

Model	W/T/L	Mean $\delta_{i}$	$p$
GPT-6-Luna	20/479/1	0.016	$2.10\times 10^{-5}$
GPT-6-Sol	13/486/1	0.011	$0.002$

Appendix

Table 11: Paired 2D-BPP comparison using three-run mean bin counts. W/T/L counts wins, ties, and losses for Dream . Mean

\delta_{i}

reports bins saved per instance by Dream . The p-values are from two-sided exact sign tests excluding ties.

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.

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

\pm 1

sample standard deviation of total tokens. Dots show total tokens for individual runs.

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.

Automated Algorithm Discovery

Automated algorithm discovery develops methods that generate and test executable algorithms for optimization, science, software, and machine learning.

See all 170 papers

Code World Models for Parameter Control in Evolutionary Algorithms
Feb 25, 2026Camilo Chacón Sartori, Guillem Rodríguez CorominasCode World Models Large Language Model-Guided Optimization
ICN2 – Catalan Institute of Nanoscience and Nanotechnology, Barcelona, Spain · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Universitat Politècnica de Catalunya (UPC), Barcelona, Spain
Initialization Improves LLM-Driven Discovery
Sep 30, 2026Mansi Sakarvadia, Marco Ciccone, Colin RaffelLarge Language Model-Guided Optimization Large Language Model-Guided Scientific Discovery
University of Chicago · Vector Institute · University of Toronto
Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers
May 18, 2026Soheyl Massoudi, Gabriel Apaza, Milad Habibi +1RL for Code Generation LLM-Based Program Synthesis
ETH Zürich Zürich, Switzerland · University of Maryland College Park, MD, USA

Feb 25, 2026J/K move · Enter open · S save

Code World Models for Parameter Control in Evolutionary Algorithms

Camilo Chacón Sartori, Guillem Rodríguez Corominas

ICN2 – Catalan Institute of Nanoscience and Nanotechnology, Barcelona, Spain · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Universitat Politècnica de Catalunya (UPC), Barcelona, Spain

Code World Models Large Language Model-Guided Optimization LLMs for Evolutionary Optimization World Models Evolutionary Optimization Combinatorial Optimization

Open paper AskPDF arXiv

Can an LLM learn how an optimizer behaves -- and use that knowledge to control it? We extend Code World Models (CWMs), LLM-synthesized Python programs that predict environment dynamics, from deterministic games to stochastic combinatorial optimization. Given suboptimal trajectories of

(1{+}1)

\text{RLS}_k

, the LLM synthesizes a simulator of the optimizer's dynamics; greedy planning over this simulator then selects the mutation strength

k

at each step. On \lo{} and \onemax{}, CWM-greedy performs within 6% of the theoretically optimal policy -- without ever seeing optimal-policy trajectories. On \jump{

_k

}, where a deceptive valley causes all adaptive baselines to fail (0% success rate), CWM-greedy achieves 100% success rate -- without any collection policy using oracle knowledge of the gap parameter. On the NK-Landscape, where no closed-form model exists, CWM-greedy outperforms all baselines across fifteen independently generated instances (

36.94

vs.\

36.32

;

p<0.001

) when the prompt includes empirical transition statistics. The CWM also outperforms DQN in sample efficiency (200 offline trajectories vs.\ 500 online episodes), success rate (100% vs.\ 58%), and generalization (

k{=}3

: 78% vs.\ 0%). Robustness experiments confirm stable synthesis across 5 independent runs.

Abstract

Automated Algorithm Discovery

Explore similar work

Code World Models for Parameter Control in Evolutionary Algorithms

Initialization Improves LLM-Driven Discovery

Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers