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

arXiv: https://arxiv.org/abs/2509.12643 · HTML: https://mlsanity.com/paper/2509.12643/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## Builds on (most cited first, 9 of 9)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [Large Language Model for Multi-objective Evolutionary Optimization](https://mlsanity.com/paper/2310.12541/) (2023)
- [Large Language Model-Enhanced Algorithm Selection: Towards Comprehensive Algorithm Representation](https://mlsanity.com/paper/2311.13184/) (2023)
- [Large Language Models as Surrogate Models in Evolutionary Algorithms: A Preliminary Study](https://mlsanity.com/paper/2406.10675/) (2024)
- [Cooperative Operation of the Fleet Operator and Incentive-aware Customers in an On-demand Delivery System: A Bi-level Approach](https://mlsanity.com/paper/2109.03539/) (2021)
- [An Almost Feasible Sequential Linear Programming Algorithm](https://mlsanity.com/paper/2401.13840/) (2024)

## Built on by (most cited first, 1 of 1)

- [Learning to Design Convex Relaxations for Nonconvex Optimization](https://mlsanity.com/paper/2610.16948/) (2026)

## Abstract (arXiv)

Large Language Model (LLM)-based optimization has recently shown promise for autonomous problem solving, yet most approaches still cast LLMs as passive constraint checkers rather than proactive strategy designers, limiting their effectiveness on complex Constraint Optimization Problems (COPs). To address this, we present AutoCO, an end-to-end Automated Constraint Optimization method that tightly couples operations-research principles of constraint relaxation with LLM reasoning. A core innovation is a unified triple-representation that binds relaxation strategies, algorithmic principles, and executable codes. This design enables the LLM to synthesize, justify, and instantiate relaxation strategies that are both principled and executable. To navigate fragmented solution spaces, AutoCO employs a bidirectional global-local coevolution mechanism, synergistically coupling Monte Carlo Tree Search (MCTS) for global relaxation-trajectory exploration with Evolutionary Algorithms (EAs) for local solution intensification. This continuous exchange of priors and feedback explicitly balances diversification and intensification, thus preventing premature convergence. Extensive experiments on three challenging COP benchmarks validate AutoCO's consistent effectiveness and superior performance, especially in hard regimes where current methods degrade. Results highlight AutoCO as a principled and effective path toward proactive, verifiable LLM-driven optimization.