arXiv:2607.28268cs.AI2026-07

用大模型自动优化约束求解模型,提升求解速度。

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

  • 用大模型结合进化搜索生成改进的约束模型。
  • 在8个问题上实现显著提速,最快提升10倍以上。
  • 适合需要高效求解复杂组合问题的研究者和工程师。

组合优化问题广泛存在于工业应用中。通常通过声明式约束模型进行建模,再由后端求解器求解。近期研究显示,大语言模型(LLM)能从自然语言生成正确模型,但即使模型正确,求解效率仍高度依赖建模方式。本文探究是否可用LLM自动化性能导向的模型重构。受自动启发式设计(AHD)启发,我们采用进化框架:由LLM提出候选重构方案,经验证与基准模型对比。比较了多种适配AHD的搜索策略,这些策略决定哪些历史尝试、指令和反馈进入下一轮提示。现有保留策略关注时效性或性能,但未显式保持上下文多样性。为此,我们提出「特征多样保留」(PDR),利用最大边际相关性(MMR)对实例级运行时向量进行保留,以获取行为多样化的尝试。我们在8个CSPLib问题上系统评估该策略,采用基于验证的最终模型选择。结果表明:(i) 迭代重构可带来显著的预留加速;(ii) 保留上下文多样性的策略优于仅保留最新或最快尝试的策略;(iii) 基于验证的选择提升了所有策略的预留加速效果。

原文摘要 · Abstract (English)

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.

约束求解大模型自动化进化搜索

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。