Large language models guide better algorithms for optimization problems
Dream-COP: Guiding Algorithm Discovery for Combinatorial Optimization Problems in an Experience World
Machine LearningArtificial Intelligence
Summary
Finding better ways to solve complex optimization problems can take a lot of time and trial-and-error. The authors developed Dream-COP, which uses past search experiences like a memory to help a guide agent learn how to explore and improve algorithms efficiently. This method helps discover better solutions faster and can even apply lessons learned from one problem to similar problems. Their approach showed improvement across several types of optimization challenges compared to previous methods.
What this means in practice
- •For optimization software developers: Create faster and more effective optimization solvers by using learned exploration policies to guide algorithm discovery.
- •For resource planning teams: Improve resource allocation by deploying optimization algorithms refined through experience-guided search strategies, leading to better solutions with less computational effort.
Authors
Kuan Xu, Jianming Wang, Ni Zhang, Yaoxin Wu, Yong Wang, Zhiguang Cao
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 \emph{policy agent} learns executable policies through \emph{dreaming} in this experience world to guide a \emph{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, \textsc{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.