Elamur Research⌕
☰
home / papers / 2026 / Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution

Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution

Paper · 2026 · Beidan Liu, Zhengqiu Zhu, Chen Gao et al.

Summary

Real-world constraint optimization problems (COPs) are often NP-hard. Hard constraints split the feasible region into fragments, so LLM-driven algorithm-design systems such as EoH, ReEvo and FunSearch get little useful feedback once feasible solutions become rare. The authors propose AutoCO, which makes the LLM an active designer of constraint relaxation strategies, a standard operations-research technique, rather than a simple feasibility checker.

Each candidate solver is encoded as a linked triple: a relaxation strategy (one relaxation factor per constraint), the algorithmic idea behind it, and runnable code. Two search layers exchange information in both directions. Monte Carlo Tree Search explores relaxation trajectories at the global level, and an evolutionary algorithm refines the triples locally. This balances exploration against exploitation and helps the search avoid getting stuck early.

On three benchmarks (VRPTW, SFL and VRPTW-fuel), AutoCO outperforms prior LLM-based methods. Its advantage is largest on the hardest instances, where Gurobi also has difficulty. The work points toward LLM-driven optimization that is more proactive and easier to verify.

Key points

  • The pipeline has three phases: problem analysis, strategy search and code execution. Relaxed constraints take the form g_k(x) ≤ δ_k, with each δ_k kept within set bounds.
  • Compared with the strongest LLM-based baselines, AutoCO lowers the optimality gap by 24.7% on average across VRPTW, SFL and VRPTW-fuel.
  • The baselines (FunSearch, EoH, ReEvo) stall early. On SFL-4, for example, FunSearch converges by generation 5. AutoCO keeps probing new regions even when fitness plateaus.
  • The method has several stated limitations:
    • End-to-end runtime is longer than for some baselines.
    • It covers only static, deterministic problems.
    • The strategy space grows exponentially with problem dimensionality.
    • Results depend on the LLM's reasoning and coding ability.
    • There is no theoretical convergence guarantee.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Tsinghua UniversityBeijing · China333 works · 87,019 citations🎓National University of Defense TechnologyChangsha · China10 works · 931 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksComputer Networks and Communications · 64 works

Cite

Cite as Beidan Liu, Zhengqiu Zhu, Chen Gao, Tianle Pu, Yong Zhao, Wei Qi and Quanjun Yin. 2026. Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.48

@inproceedings{liu2026learn,
  title = {{Learn to Relax with Large Language Models: Solving Constraint Optimization Problems via Bidirectional Coevolution}},
  author = {Beidan Liu, Zhengqiu Zhu, Chen Gao, Tianle Pu, Yong Zhao, Wei Qi and Quanjun Yin},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.48},
  url = {https://doi.org/10.18653/v1/2026.acl-long.48}
}

References

37 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Fangyun Bai, Xinglong Ju, Shouyi Wang, Wenyong Zhou, and Feng Liu. 2022. Wind farm layout optimization using adaptive evolutionary algorithm with Monte Carlo Tree Search reinforcement learning. Energy Conversion and Management, 252:115047. find
  2. Hendrik Baier and Peter I. Cowling. 2018. Evolutionary mcts for multi-action adversarial games. In 2018 find
  3. IEEE Conference on Computational Intelligence and Games (CIG), pages 1–8. Federico Berto, Chuanbo Hua, Junyoung Park, Lau-rin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiw… find
  4. Pierre Bonami, Lorenz T. Biegler, Andrew R. Conn, Gérard Cornuéjols, Ignacio E. Grossmann, Carl D. Laird, Jon Lee, Andrea Lodi, François Margot, Nicolas Sawaya, and Andreas Wächter. 2008. An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optimization, 5(2):186–204. find
  5. Cameron B. Browne, Edward Powley, Daniel Whitehouse, Simon M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. 2012. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1… find
  6. Pan Cao, John Thompson, and H. Vincent Poor. 2017. A sequential constraint relaxation algorithm for rank-one constrained problems. In 2017 25th European Signal Processing Conference (EUSIPCO), pages 1060–1064. find
  7. François Clautiaux and Ivana Ljubić. 2025. Last fifty years of integer linear programming: A focus on recent practical advances. European Journal of Operational Research, 324(3):707–731. find
  8. Naoki Egami, Musashi Hinck, Brandon Stewart, and Hanying Wei. 2023. Using imperfect surrogates for downstream inference: Design-based supervised learning for social science applications of large language models. In Advances in Neural Information Processing Systems, volume 36, pages 68589–68601. Curr… find
  9. A. E. Eiben and J. E. Smith. 2015. Introduction to Evolutionary Computing, 2 edition. Natural Computing Series. Springer Berlin, Heidelberg. 55 b/w illustrations, 12 illustrations in colour. find
  10. Marshall L. Fisher. 1981. The lagrangian relaxation method for solving integer programming problems. Management Science, 27(1):1–18. find
  11. Christodoulos A Floudas. 1995. Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press. find
  12. Ignacio E Grossmann. 2002. Review of nonlinear mixed-integer and disjunctive programming techniques. Optimization and Engineering, 3:227–252. find
  13. Hao Hao, Xiaoqun Zhang, and Aimin Zhou. 2024. Large language models as surrogate models in evolutionary algorithms: A preliminary study. Swarm and Evolutionary Computation, 91:101741. find
  14. Haokai Hong, Min Jiang, and Gary G. Yen. 2024. Improving performance insensitivity of large-scale multiobjective optimization via monte carlo tree search. IEEE Transactions on Cybernetics, 54(3):1816– 1827. find
  15. J. Kennedy and R. Eberhart. 1995. Particle swarm optimization. In Proceedings of ICNN’95 - International Conference on Neural Networks, volume 4, pages 1942–1948 vol.4. find
  16. David Kiessling, Charlie Vanaret, Alejandro Astudillo, Wilm Decré, and Jan Swevers. 2024. An almost feasible sequential linear programming algorithm. In 2024 European Control Conference (ECC), pages 2328–2335. IEEE. find
  17. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science, 220(4598):671–680. find
  18. Fei Liu, Xi Lin, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. 2025. Large language model for multiobjective evolutionary optimization. In International Conference on Evolutionary Multi-Criterion Optimization, pages 178–191. Springer. find
  19. Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. 2024. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. Preprint, arXiv:2401.02051. — [arXiv:2401.02051](https://arxiv.org/abs/2401.02051) find
  20. Fei Liu, Yiming Yao, Ping Guo, Zhiyuan Yang, Xi Lin, Zhe Zhao, Xialiang Tong, Kun Mao, Zhichao Lu, Zhenkun Wang, Mingxuan Yuan, and Qingfu Zhang. 2026. A systematic survey on large language models for algorithm design. ACM Computing Surveys, 58(8):1–32. find
  21. Ali W. Mohamed, Anas A. Hadi, and Kamal M. Jambi. 2019. Novel mutation strategy for enhancing shade and lshade algorithms for global numerical optimization. Swarm and Evolutionary Computation, 50:100455. find
  22. Mahdi Mokhtarzadeh, Reza Tavakkoli-Moghaddam, Chefi Triki, and Yaser Rahimi. 2021. A hybrid of clustering and meta-heuristic algorithms to solve a p-mobile hub location–allocation problem with the depreciation cost of hub facilities. Engineering Applications of Artificial Intelligence, 98:104121. find
  23. Pablo Moscato. 1989. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical Report C3P 826, Caltech Concurrent Computation Program 158-79, California Institute of Technology, Pasadena, CA. find
  24. Christos H. Papadimitriou and Kenneth Steiglitz. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. hyper-heuristics with reflective evolution. In Advances in Neural Information Processing Systems, volume 37, pages 43571–43608. Curran Assoc… find
  25. David Pisinger and Stefan Ropke. 2019. Large neighborhood search. In Michel Gendreau and Jean-Yves Potvin, editors, Handbook of Metaheuristics, pages 99–127. Springer International Publishing, Cham. find
  26. Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. 2023. Deepaco: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pages 43706–43728. Curran Associates, Inc. find
  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. 2024. Mathematical discoveries from program search with large language models…
  28. Marius M. Solomon. 1987. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2):254–265. find
  29. Rainer Storn. 1999. System design by constraint adaptation and differential evolution. IEEE Transactions on Evolutionary Computation, 3(1):22–34. find
  30. Paul Tseng and Dimitri P. Bertsekas. 1987. Relaxation methods for linear programs. Mathematics of Operations Research, 12(4):569–596. find
  31. Nguyen Van Thieu and Seyedali Mirjalili. 2023. Mealpy: An open-source library for latest meta-heuristic algorithms in python. Journal of Systems Architecture, 139:102871. find
  32. Darrell Whitley. 1994. A genetic algorithm tutorial. Statistics and Computing, 4(2):65–85. find
  33. Xingyu Wu, Yan Zhong, Jibin Wu, Bingbing Jiang, and Kay Chen Tan. 2024. Large language model-enhanced algorithm selection: Towards comprehensive algorithm representation. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024, pages 5235–5244. find
  34. Hai Xia, Changhe Li, Sanyou Zeng, Qingshan Tan, Junchen Wang, and Shengxiang Yang. 2022. Learning to search promising regions by a monte-carlo tree model. In 2022 IEEE Congress on Evolutionary Computation (CEC), pages 01–08. find
  35. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2024. Large language models as optimizers. In The Twelfth International Conference on Learning Representations.
  36. Canqi Yao, Shibo Chen, and Zaiyue Yang. 2024. Cooperative operation of the fleet operator and incentive-aware customers in an on-demand delivery system: A bilevel approach. IEEE Internet of Things Journal, 11(6):9668–9680. find
  37. Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. 2024. Reevo: Large language models as find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2026-learn-relax-large-language-models/