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

📄 arXiv: 2509.12643 📥 PDF

作者: Beidan Liu, Zhengqiu Zhu, Chen Gao, Tianle Pu, Yong Zhao, Wei Qi, Quanjun Yin

分类: cs.AI

发布日期: 2026-04-06

💡 一句话要点

AutoCO：利用大语言模型和双向协同进化解决约束优化问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 约束优化问题 约束松弛 蒙特卡洛树搜索 进化算法 双向协同进化 自动化优化 LLM推理

📋 核心要点

  1. 现有方法将LLM视为被动的约束检查器，限制了其在复杂约束优化问题（COP）上的有效性。
  2. AutoCO通过统一的三重表示，使LLM能够综合、论证和实例化既有原则性又可执行的松弛策略。
  3. AutoCO采用双向协同进化机制，平衡全局探索和局部强化，实验表明其在困难场景下性能优越。

📝 摘要（中文）

本文提出了一种名为AutoCO的端到端自动化约束优化方法，该方法将约束松弛的运筹学原理与大语言模型（LLM）的推理能力紧密结合。核心创新在于统一的三重表示，它将松弛策略、算法原理和可执行代码绑定在一起，使LLM能够综合、论证和实例化既有原则性又可执行的松弛策略。为了应对分散的解空间，AutoCO采用双向全局-局部协同进化机制，将蒙特卡洛树搜索（MCTS）用于全局松弛轨迹探索，并将进化算法（EAs）用于局部解的强化。这种持续的先验和反馈交换明确地平衡了多样性和强化，从而防止了过早收敛。在三个具有挑战性的约束优化问题（COP）基准上的大量实验验证了AutoCO的一致有效性和卓越性能，尤其是在当前方法退化的困难情况下。结果表明，AutoCO是实现主动、可验证的LLM驱动优化的有效途径。

🔬 方法详解

问题定义：论文旨在解决复杂约束优化问题（COPs），现有方法主要依赖于将LLM作为被动的约束检查器，缺乏主动的策略设计能力，导致在复杂问题上效果不佳。此外，解空间分散，容易陷入局部最优。

核心思路：论文的核心思路是将约束松弛的运筹学原理与LLM的推理能力相结合，使LLM能够主动设计和执行松弛策略。通过统一的三重表示，将松弛策略、算法原理和可执行代码绑定，实现LLM对优化过程的有效控制。同时，采用双向协同进化机制，平衡全局探索和局部强化，避免过早收敛。

技术框架：AutoCO的整体框架包含以下几个主要模块：1) 统一三重表示：将松弛策略、算法原理和可执行代码进行统一表示，作为LLM的输入和输出。2) LLM推理模块：利用LLM生成、验证和实例化松弛策略。3) 双向协同进化模块：使用蒙特卡洛树搜索（MCTS）进行全局松弛轨迹探索，使用进化算法（EAs）进行局部解的强化，并进行信息交换。4) 执行模块：执行LLM生成的代码，并评估结果。

关键创新：AutoCO的关键创新在于：1) 统一三重表示：将松弛策略、算法原理和可执行代码进行统一表示，使得LLM能够理解和操作优化过程。2) 双向协同进化机制：通过MCTS和EAs的协同，平衡全局探索和局部强化，避免过早收敛。与现有方法相比，AutoCO更加主动和可控，能够更好地应对复杂约束优化问题。

关键设计：论文中涉及的关键设计包括：1) 三重表示的具体形式：如何将松弛策略、算法原理和可执行代码进行有效编码，以便LLM理解和生成。2) MCTS和EAs的参数设置：如何设置MCTS的探索参数和EAs的进化参数，以实现最佳的全局探索和局部强化平衡。3) LLM的prompt设计：如何设计LLM的prompt，引导其生成有效的松弛策略和可执行代码。具体的参数设置和网络结构等细节在论文中可能有所描述，但此处无法详细展开。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，AutoCO在三个具有挑战性的约束优化问题基准上表现出色，尤其是在困难情况下，性能优于现有方法。具体的数据提升幅度在论文中有所体现，但此处无法给出精确数值。AutoCO的成功验证了LLM在主动优化策略设计方面的潜力，并为LLM驱动的优化方法提供了新的思路。

🎯 应用场景

AutoCO具有广泛的应用前景，可应用于资源调度、生产计划、物流优化、金融建模等领域。通过结合LLM的推理能力和运筹学原理，AutoCO能够更有效地解决复杂的约束优化问题，提高决策效率和优化效果，为企业和社会带来实际价值。未来，AutoCO有望成为一种通用的自动化优化工具，赋能各行各业。

📄 摘要（原文）

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.