Improving Constraint Models with LLM Agents
Florentina Voboril, Stefan Szeider
Why It Matters
What makes this one worth your time
This research could significantly streamline the modeling process in Constraint Programming, making it more accessible and efficient for practitioners who may lack deep expertise.
An LLM agent enhances constraint models by autonomously reformulating and validating them.
Summary
The paper presents an agentic framework utilizing a Large Language Model (LLM) to reformulate constraint models for Constraint Programming (CP), demonstrating improved performance over traditional methods through empirical validation of alternative formulations.
Key contributions
- Introduction of an agentic framework for constraint model reformulation using LLMs.
- Demonstration of improved performance across multiple combinatorial optimization problems compared to original models.
- Empirical validation of model correctness through an innovative iterative process.
Notable insights
- The use of an LLM for iterative diagnosis and repair of constraint models is a novel approach that leverages the strengths of AI in problem-solving.
- Empirical validation of model correctness rather than relying solely on predefined rules allows for greater flexibility and adaptability in model reformulation.
Possible limitations
- Not stated in the abstract.
Abstract
arXiv:2608.08127v1 Announce Type: new Abstract: The runtime of Constraint Programming (CP) solvers is highly sensitive to modeling choices, such as symmetry breaking, implied constraints, global constraints, constraint reformulation, and variable representation. Improving these constraint models has traditionally required human expertise, and existing automated reformulation systems are restricted to a predefined library of hand-crafted transformation rules. We introduce an agentic framework that instead reformulates a constraint model from an open-ended space and establishes correctness empirically rather than by construction: a Large Language Model (LLM) agent, given a model and three training instances, proposes alternative formulations, validates each by injecting its solution back into the original model, and diagnoses and repairs failures, returning the best variant it finds in a median of about fifteen minutes. The models are expressed in the CPMpy modeling library, and each proposed model is evaluated on three larger test instances. Across nine combinatorial optimization problems, the generated models outperform the originals on 21 of 27 test instances, and on some problems solve more than two orders of magnitude faster. A comparison against non-agentic baselines that reuse the same validation and selection tools indicates that the gains stem from the agent's iterative diagnosis and repair, not merely from sampling several candidates. These results demonstrate that autonomous agentic methods can support the improvement of constraint models.