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

This paper investigates whether Large Language Models (LLMs) can automate the performance-oriented reformulation of constraint models. While LLMs are known to generate correct models from natural language, these models are often inefficient. The authors propose an evolutionary framework where an LLM iteratively proposes model reformulations, which are then evaluated against a baseline model on training instances. The core of the research involves comparing different 'retention strategies'—methods for deciding which previous model attempts and performance feedback are included in the LLM's prompt for the next iteration.

The authors compare several strategies, including simple recency-based retention, quality-based retention (keeping the fastest models), and a novel approach called Profile-Diverse Retention (PDR). PDR uses Maximal Marginal Relevance (MMR) to select a subset of previous attempts that are not only fast but also exhibit diverse runtime behaviors across different problem instances. This ensures the LLM receives a varied set of examples, preventing the search from getting stuck in local optima where only one type of model structure is explored.

The experiments, conducted across eight diverse CSPLib problems, demonstrate that iterative reformulation consistently yields substantial speedups on held-out test data. The results show that strategies prioritizing context diversity (like PDR) outperform those that focus solely on the most recent or the fastest attempts. Furthermore, the authors emphasize that validation-based final model selection—choosing the best model based on a separate validation set rather than the training set—is a critical step that improves performance across all tested strategies.

Automating the reformulation of constraint models is a long-standing challenge in Constraint Programming, often requiring significant manual effort from expert modelers. This work demonstrates that LLMs can effectively bridge this gap, turning the 'model-and-solve' workflow into a more automated, performance-aware process. By providing a framework that balances model quality with behavioral diversity, the authors offer a scalable path toward improving solver efficiency in industrial applications.