LLM进化搜索重构约束模型,提升求解器效率

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

精选理由

论文提出用LLM做模型重构,跑8个基准问题都有明显提速,做约束求解的可以看看这个PDR策略。

AI 摘要

该研究用进化框架让LLM自动重构约束模型以提升求解效率。作者提出Profile-Diverse Retention策略,用最大边际相关性对实例级运行时间向量做去重。在8个CSPLib问题上验证,迭代重构带来显著留出集加速。保留多样化上下文的策略优于仅保留最近或最快尝试的策略。基于验证集的选择进一步提升了所有策略的加速效果。

原文 · arXiv cs.AI

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

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.

LLM进化搜索重构约束模型,提升求解器效率 · AI 热点