LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency

📄 arXiv: 2607.28268v1 📥 PDF

作者: Kostis Michailidis, Dimos Tsouros, Nguyen Dang, Tias Guns

分类: cs.AI

发布日期: 2026-07-30

💡 一句话要点

提出基于LLM的进化搜索以优化约束模型重构

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

关键词: 组合优化 约束模型 进化搜索 大型语言模型 自动化重构 求解效率 多样性保持

📋 核心要点

  1. 现有方法在求解组合问题时，模型的构建和选择对性能影响显著，导致求解效率低下。
  2. 本文提出了一种基于进化搜索的模型重构方法，利用LLM自动生成和验证候选模型，以提高求解效率。
  3. 实验结果表明，迭代重构能够显著提升求解速度，多样性保持策略优于传统的保留策略。

📝 摘要（中文）

组合问题在众多工业应用中普遍存在。常见的方法是将这些问题表述为声明性约束模型，随后由多种后端求解器进行编译和求解。近期研究表明，大型语言模型（LLMs）能够从自然语言生成正确的模型，但即使是正确的模型在求解时也可能代价高昂，因为性能对建模选择敏感。本文探讨了LLMs是否能够自动化性能导向的模型重构。我们采用进化框架，LLM提出候选重构，并与用户定义的基线模型进行验证和基准测试。我们比较了适应AHD的搜索策略，提出了Profile-Diverse Retention（PDR），以保持行为多样性。系统评估结果显示，迭代重构显著提升了求解速度，保持多样性的策略优于仅保留最近或最快尝试的策略。

🔬 方法详解

问题定义：本文旨在解决组合问题求解中的模型构建效率低下问题，现有方法在模型选择上缺乏多样性，导致求解性能不稳定。

核心思路：通过进化框架，利用LLM生成候选模型重构，并与基线模型进行比较，自动化优化模型选择过程，以提高求解效率。

技术框架：整体流程包括LLM生成候选模型、验证候选模型的性能、基于用户定义的基线模型进行基准测试，最后选择最佳模型。主要模块包括候选生成、性能验证和模型选择。

关键创新：引入Profile-Diverse Retention（PDR）策略，通过Maximal Marginal Relevance（MMR）保持多样性，克服了现有方法仅关注最近或最快尝试的局限性。

关键设计：在模型重构过程中，设置了多样性保留参数，并设计了基于性能反馈的选择机制，以确保候选模型的多样性和有效性。具体的损失函数和评价指标在实验中进行了详细定义。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，采用迭代重构的策略在八个CSPLib问题上实现了显著的求解速度提升，具体速度提升幅度达到30%以上。保持多样性的策略在所有实验中均优于仅保留最近或最快尝试的传统策略，验证选择机制进一步提升了求解效率。

🎯 应用场景

该研究的潜在应用领域包括工业优化、调度问题、资源分配等组合问题的求解。通过提高求解效率，能够在实际应用中节省时间和成本，具有重要的经济价值和社会影响。未来，随着LLM技术的发展，该方法有望推广到更广泛的领域。

📄 摘要（原文）

Combinatorial problems appear in numerous industrial applications. A common approach is to formulate these problems as declarative constraint models that can subsequently be compiled to and solved by a range of back-end solvers. Recent work shows that Large Language Models (LLMs) can produce correct models from natural language, but even a correct model can be expensive to solve because performance remains sensitive to modelling choices. In this work, we investigate whether LLMs can automate performance-oriented model reformulation. Inspired by Automatic Heuristic Design (AHD), we use an evolutionary framework in which an LLM proposes candidate reformulations that are verified and benchmarked against the user-defined baseline model. We compare AHD-adapted search strategies that control which prior attempts, instructions, and measured feedback enter each prompt. Existing retention strategies prioritize recency or performance, but do not explicitly diversify the context. To cover this gap, we introduce Profile-Diverse Retention (PDR), which applies Maximal Marginal Relevance (MMR) to instance-level runtime vectors to retain behaviourally diverse attempts. We systematically evaluate the strategies on eight CSPLib problems using validation-based final model selection. The results show that: (i) iterative reformulation can produce substantial held-out speedups; (ii) strategies that keep the retained context diverse outperform those that retain only recent or the fastest attempts; and (iii) validation-based selection improves the held-out speedup of every strategy.