Improving Constraint Models with LLM Agents

Improving Constraint Models with LLM Agents Florentina Voboril

Stefan Szeider

Algorithms and Complexity Group TU Wien, Vienna, Austria {fvoboril,sz}@ac.tuwien.ac.at

arXiv:2608.08127v1 [cs.AI] 8 Aug 2026

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 (78%), 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. Keywords— Large Language Models, ReAct Agent, Constraint Model Optimization, CPMpy

1

Introduction

Constraint Programming (CP) is a powerful paradigm for solving combinatorial optimization problems. The solving performance strongly depends on how the problem is modeled. Applying optimization techniques such as adding symmetry-breaking constraints, which eliminate redundant equivalent solutions [1], implied constraints, which strengthen reasoning without changing the solution set [2], using high-level global constraints with specialized propagation algorithms [3], reformulating the model, or using alternative variable representations often reduces the search space and speeds up solving time [4]. However, identifying such techniques typically requires substantial expertise and experience in constraint modeling. There have been previous approaches for automatic reformulation and model improvement in CP. For example, Conjure automatically produces constraint models from an abstract problem specification written in Essence [5] and Savile Row automatically improves constraint models through predefined reformulation rules and simplifications [6]. There have also been approaches for automatically detecting symmetries [7] and generating streamliner portfolios [8]. Beyond model reformulations, there are also approaches for automated algorithm selection and automated solver tuning. SATzilla [9] automatically selects promising solvers for SAT on a per-instance basis, whereas approaches like AutoFolio [10] generalize algorithm selection to a broader range of optimization domains. SMAC [11] automatically configures solver parameters to improve performance on benchmark distributions.

Unlike these approaches, which select algorithms, tune solver parameters for a fixed constraint model, or apply predefined transformations, our framework directly modifies the model itself: the agent autonomously decides which modeling optimizations to attempt and validates them empirically. Recent progress in Large Language Models (LLMs) has enabled new approaches at the intersection between CP and generative AI. LLMs have recently been used for active constraint acquisition [12] and dealing with hard constraints in LLM-generated sentences [13]. Another promising direction is to generate CP models from natural language descriptions [14–17], and it was studied how small changes in the natural language problem description affect generated CP models [18]. However, little work has examined LLMs’ ability to improve existing models. A first step in this direction has been the use of LLMs to generate streamlining constraints for constraint satisfaction problems [19, 20] and optimization problems [21]. In this work, we introduce a novel agentic approach that autonomously improves existing constraint models. It goes beyond adding symmetry-breaking or streamlining constraints, as it reformulates the entire model, and beyond classical reformulation systems such as Savile Row [6], as it draws on an open-ended space of reformulations rather than a fixed library of hand-coded rules. We express the models in CPMpy [22], an open-source Python library for solving CP problems: one can describe problems at a high level and solve them using one of the supported solvers. Recent research has shown that CPMpy is particularly well-suited for LLMs, as they have seen extensive Python code during training [15]. We implement our approach using an agent that follows a Reason and Act (ReAct) paradigm [23]. In ReAct-style agents, an LLM alternates between reasoning about the task and executing the provided tools. Each tool behaves like a function with defined input parameters and return values following a JSON schema. Compared to a hard-coded workflow, the agent decides which tool to call in which order. Problem Statement. We consider the following setting: the user provides a CPMpy model and three small training instances. We want to automatically obtain a modified model whose solutions are feasible under the original model, while improving performance. We focus exclusively on optimization problems, where performance is measured by objective quality within a fixed time limit. The training instances may be used to guide the improvement process, while separate test instances are used only for evaluation. Our approach to this problem is to utilize an agent that analyzes the original model and iteratively generates alternative model variants by applying potential optimization strategies. It validates them using an automated procedure that checks both correctness and solver performance. In the end, it selects the model it considers best-performing and returns it. We refer to this model as the proposed model. The main difficulty is reliability: unlike a curated rule set, an LLM proposes reformulations from an unbounded space and does so unreliably – many candidates are buggy or silently change the problem – so ensuring that a proposed model is both correct and faster is the central challenge, which the validation-and-repair loop is designed to meet. To evaluate our approach, we apply it to nine combinatorial optimization problems, including several well-known benchmark problems and one novel problem designed specifically for this study. Across these problems, the agent proposes the final model in a median of approximately fifteen minutes. These models outperform the original models on 21 of 27 test instances (78%), demonstrating that LLM agents can successfully identify useful modeling improvements even with only a small number of training instances. Main Contributions. First, we frame and demonstrate a new point in the design space of automatic constraint-model improvement: reformulation from an open-ended space, with correctness established empirically rather than through a fixed library of hand-crafted rules. Classical systems such as Savile Row [6] can only apply transformations that have been pre-encoded and proved sound; our agent instead proposes arbitrary reformulations, validates each one empirically, and diagnoses and repairs failures in a Reason-and-Act loop. To our knowledge, this is the first such framework for improving existing constraint models. Second, on nine combinatorial optimization problems the agent’s proposed models outperform the originals on 21 of 27 test instances (Table 1), applying techniques such as

2

Input: original CPMpy model + 3 training instances Generate an alternative model (analyze the model; pick a technique: symmetry breaking, global / implied constraints, reformulation, . . . )

Validate on the training instances: run alt. model → inject its solution into the original → solve the original freely ⇒ better / equal / worse / invalid / no_solution / solver_error

five correct models generated? yes

no: diagnose & repair

Select and return the proposed model

Figure 1: Overview of the agent’s Reason-and-Act loop. Through the PYTHON_EXEC_TOOL, SAVE_CODE_TOOL, TODO_WRITE_TOOL, and VALIDATE_CPMPY_MODEL_TOOL tools, the LLM agent repeatedly proposes an alternative model and validates it against the original; on failure it diagnoses and repairs, iterating until five correct models have been produced, then returns the one it considers best. symmetry breaking, global constraints, and alternative variable representations. Third, we provide an empirical validation procedure that checks candidate solutions against the original model by injecting them back into it. Finally, to verify that these gains arise from the agentic loop rather than from sampling alone, we compare the agent against non-agentic baselines that reuse the same validation and selection tools.

2

Agentic Approach

In our approach, we run an open-source agentic Python coder [17] to automatically generate an improved CPMpy model. We decided to use this lightweight agent instead of full-featured coding agents, since the framework provides a high level of transparency, full control over the prompts, better reproducibility, supports various underlying LLMs, and is specifically designed for generating single-script Python code. Since our tasks focus on model generation rather than large-scale software engineering, more complex coding agents would be unnecessary. Figure 1 gives an overview of the resulting loop.

2.1

The Agent’s Tools

The agent has access to the following tools: • PYTHON_EXEC_TOOL. Executes Python code in a persistent IPython kernel. • SAVE_CODE_TOOL. Saves final verified Python code to a file. • TODO_WRITE_TOOL. Creates a set of todo items. This forces the agent to plan before coding, track progress step-by-step, and ensure it does not skip important steps. • VALIDATE_CPMPY_MODEL_TOOL. Compares a new CPMpy model against the original by testing both on training instances. See description below. 3

The validation tool checks alternative models for two aspects: a model must be semantically correct (i.e., every solution it produces must also be feasible under the original model), and it must improve performance. To ensure this, our validation tool consists of three steps, each with a 20 s time limit for each training instance. • Step 1 – Run the alternative model. This step acts as an early filter. If the alternative model does not follow formatting requirements or has a syntax error, the outcome is solver_error. Likewise, if the model cannot find any solution within the timeout, the outcome is labeled no_solution. Otherwise, a candidate solution x′ is obtained and passed to Step 2. • Step 2 – Run the original model with the injected solution x′ . This step verifies the correctness of the new solution by injecting x′ back into the original model. All output decision variables of the original model are fixed to the corresponding values in x′ via equality constraints, and the augmented model is solved. If the original model is feasible under these constraints, x′ satisfies all original problem constraints and is considered correct. Otherwise, the alternative model has produced an invalid solution and is not semantically equivalent to the original model. In this case, the outcome is labeled invalid and Step 3 is skipped. • Step 3 – Run the original model freely. The original model is solved without any injected constraints to obtain a reference objective value. Then the tool reports whether the objective value obtained by the alternative model in Step 1 is better than, equal to, or worse than the objective value from the original model.

2.2

Procedure

We provide the agent with the original CPMpy model, three small training instances, access to the cpmpy and numpy packages, and a project prompt. The agent is able to call the provided tools in any order. However, the prompt gives the agent a guideline on how to proceed: 1. Model analysis. The agent reads the original model and tries to identify improvement opportunities, such as symmetry gaps (symmetric solutions can be eliminated by additional constraints), propagation weaknesses (nested loops can be replaced by global constraints), or representation opportunities (e.g., rewriting a 3D Boolean array as a 2D integer array). 2. Model generation. The agent generates a new, alternative model and saves it to a designated folder. Since the validation tool treats all input models as interchangeable black boxes, the agent is instructed to ensure the alternative model satisfies the following formatting requirements: • The whole model is built within a build_model() function, which takes problem data as input and returns the model along with the decision variables. • It accepts the same input parameters as the original model. • It returns the same decision variables in the same order as the original model. 3. Validation. The agent invokes the validation tool that evaluates the alternative model on the three training instances and compares it with the original model. 4. Diagnosis and repair. If the new model is incorrect or less efficient, the agent creates a new model and re-validates it. 5. Iteration. Steps 2–4 repeat until five correct models have been generated. The agent is encouraged to create diverse model variants in each iteration. 6. Selection and logging. The agent selects and saves the proposed model. Additionally, it stores a log file and a summary of the results. The log file reports explicitly which techniques the agent applies and why, and states the validation results. The agent is not given a fixed time limit, but the process is restricted to a maximum of 200 agent steps. 4

3

Experimental Setup

The agentic Python coder we run is available as open-source software at https://github.com /szeider/agentic-python-coder.

3.1

Setup and Hardware

The agent was run under Windows Subsystem for Linux (WSL 2) on a Windows 11 machine equipped with an Intel Core Ultra 7 155U processor (12 cores, 14 threads) and 15 GiB RAM. We used the agentic Python coder [17] with Gemini 3 Flash (google/gemini-3-flash-preview, 20251217), a relatively inexpensive yet capable LLM, as the underlying model. It was accessed via OpenRouter and run with a temperature of 0.3. Python 3.13.2 invoked the agent and implemented the CPMpy (version 0.9.28) models. Across the nine problems, total agent wall-clock time was approximately 2.5 hours; no GPUs were used. To make objective values and solve times directly comparable, all reported comparison results (Tables 1, 3, and 4, and Figure 2) were obtained on a single shared machine: an AMD Ryzen 9 5900X with CPMpy 0.10.1 and the Chuffed 0.13.2 solver via MiniZinc 2.8.5, using a 20-second timeout on training instances and 60 seconds on test instances. The proposed models were therefore generated under CPMpy 0.9.28 and re-evaluated from scratch under 0.10.1; no outcome reported here is taken from the agent’s own run (Section 3.4). Per-run token statistics are reported in Section 4.

3.2

Benchmark Problems and Instances

We evaluate our approach on nine optimization problems encoded in CPMpy, namely Balanced Latin Rectangle, Golomb Ruler, Job Shop Scheduling, Mentor Matching, Progressive Party, Quadratic Assignment, Set Cover, Traveling Salesman, and Warehouse Location. We excluded symmetrybreaking constraints from all models, as these would limit the agent’s room for improvement. Most of these are well-known combinatorial problems. The exception is Mentor Matching, a problem we designed ourselves. Its description is as follows: Mentor Matching: We are given a set of mentors with a minimum and maximum capacity, and a set of students. Mentors and students provide a list of topics of interest. The task is to assign students to mentors such that each mentor supervises a number of students within their capacity bounds. A mentor can only supervise a student if they share at least one topic of interest. The objective is to maximize the total number of shared interests across all assigned student–mentor pairs. Even though there exist many variants of matching problems, we are not aware of this specific formulation. Related problems, such as the Student–Project Allocation (SPA) problem [24], use preference lists rather than shared topics of interest. We include a novel problem for two reasons. First, it ensures that the agent cannot just reproduce alternative models for the same problem from its training data. Second, it better represents our use case: the agent receives a manually created model for which no optimization has yet been considered. For each problem, we generated three training and three test instances. Training instances must find at least one solution within 20 seconds; test instances within 60 seconds. In both cases, we additionally required the solution found within the time limit not to be optimal, so that there remains room for improvement. For instances where optimality was uncertain, we ran the original model for 300 seconds (training) or 600 seconds (test) and verified that a strictly better solution was found within that extended time budget. Instances that did not satisfy these criteria were discarded and replaced.

5

3.3

Solver-Side Variance

To distinguish solver-side noise from real model-induced improvement, we ran each of the 27 test instances three times on the original model with different solver random seeds. For 23 instances, all three runs produced identical objective values. For the remaining 4 instances, the relative deviation (vmax − vmin )/vmax was 1.0%, 4.5%, 2.7%, and 1.1% (mean 2.3%, max 4.5%). We therefore treat outcome classification as robust to solver-side timing variation.

3.4

Evaluation Protocol

For each of the nine benchmark problems, we run our approach and obtain a proposed model. Only this model is considered for further evaluation. To evaluate it, we execute the same method that is used in the agent’s validation tool as described in Section 2.1. We run the three training instances with a timeout of 20 seconds and the three test instances with a timeout of 60 seconds. Although the agent already reports a summary of results, we repeat the evaluation on the training instances, as we cannot guarantee the correctness of the result file produced by the agent. We report whether the achieved objective value was better, equal, or worse than with the original model, or whether the proposed model is invalid or no solution is found within the given timeout. The solver’s performance may vary slightly across runs due to CPU load or other external artifacts; the seed study in Section 3.3 confirms that this variation does not change the better/equal/worse classification. The evaluation follows a paired design: each (problem, instance) pair is solved by both the original and the proposed model under identical hardware, solver, and timeout, so the 27 test comparisons control for instance-level difficulty.

4

Results

Across all problems, the agent executed a median of 12 Python code executions and 6 model validation calls per run, consuming a median of 312K tokens and completing within a median wall-clock time of 879 seconds (approximately 15 minutes). This is well below the 200-step ceiling, indicating that the budget rarely binds. Table 2 reports these statistics per problem. The counts are modest, with the exception of Mentor Matching, where the agent entered a long debugging loop (100 Python executions, 16.7M tokens) while still validating only five candidate models.

4.1

Main Results

Table 1 shows the results on the three training and the three test instances for all problems. Overall, the proposed models performed better on 24/27 training instances and 21/27 test instances (an improvement rate of 78% on test instances). Treating the 27 paired instance comparisons as independent Bernoulli trials, an exact binomial test on the 21/27 better-versus-not-better outcomes against H0 : p = 0.5 (ties counted against the proposed model) yields p ≈ 0.006 (95% Wilson confidence interval [0.59, 0.89]), supporting an instance-level improvement claim. The six remaining test instances were 1 equal, 4 worse, and 1 with no_solution; as the seed study in Section 3.3 shows, these outcome classifications are robust to solver-side timing variation. The higher performance on the training instances is expected, since the agent selected the model that performed best on them. At the problem level, the proposed model improves on all instances for five of the nine problems (Job Shop Scheduling, Mentor Matching, Progressive Party, Quadratic Assignment, and Warehouse Location), and is mixed for Golomb Ruler, Set Cover, Balanced Latin Rectangle, and Traveling Salesman; of these, Traveling Salesman is the only problem on which the proposed model is worse on average (Table 3). Notably, for every problem where the proposed model failed to outperform the original on all training instances, it also failed to do so on all test instances. Because outcomes within a problem are correlated (the same proposed model is applied to all of a 6

Table 1: Results of the proposed models compared to the original models on the three training and three test instances for each benchmark problem. NS = no solution. Balanced Latin Rectangle Golomb Ruler Job Shop Scheduling Mentor Matching Progressive Party Quadratic Assignment Set Cover Traveling Salesman Warehouse Location

Train 1

Train 2

Train 3

Test 1

Test 2

Test 3

worse better better better better better better better better

better better better better better better equal worse better

better better better better better better better better better

better better better better better better better worse better

worse worse better better better better better worse better

NS better better better better better equal better better

Table 2: Per-problem agent run statistics: number of candidate models validated, Python executions, total tokens, and wall-clock time. Neither count is the agent’s step count, but both contribute to it; every run finished within the 200-step budget. Problem

Models valid.

Python execs.

Tokens (K)

Time (s)

Balanced Latin Rectangle Golomb Ruler Job Shop Scheduling Mentor Matching Progressive Party Quadratic Assignment Set Cover Traveling Salesman Warehouse Location

7 6 6 5 7 9 5 14 6

10 9 10 100 15 13 9 17 12

287 230 223 16,713 397 312 256 556 397

1028 897 611 1371 879 798 710 1795 614

Median

6

12

312

879

problem’s instances), the instance-level test above should be read together with this problem-level view rather than as nine independent observations. Below, we list the concise optimization strategies that were used for the problems. • Balanced Latin Rectangle: global constraint (Inverse), symmetry breaking (LexLess for consecutive rows), loop restructuring, variable elimination (max_total_imb removed, bound computed inline). • Golomb Ruler: symmetry breaking (first difference must be smaller than the last), implied lower bounds (on mark positions and on pairwise differences). • Job Shop Scheduling: global constraint (Cumulative), constraint reformulation (one constraint with == max instead of multiple constraints with ≥), implied constraint (on lower bound). • Mentor Matching: preprocessing (precomputing scores instead of computing them repeatedly), global constraint (Element), model reformulation (looking up scores for the assigned mentor with Element instead of iterating over all student–mentor combinations), symmetry breaking (identical mentors / identical students).

7

Table 3: Per-problem effect sizes on the test instances: number of instances on which the proposed model is better, mean relative objective improvement, and median / maximum solve-time speedup over the original. The mean is taken over the instances with a defined improvement, so the Balanced Latin Rectangle entry averages two instances rather than three. Problem Balanced Latin Rectangle Golomb Ruler Job Shop Scheduling Mentor Matching Progressive Party Quadratic Assignment Set Cover Traveling Salesman Warehouse Location

Better (of 3)

Mean obj. impr. (%)

Median speedup

Max speedup

1 2 3 3 3 3 2 1 3

+0.3 +2.1 +4.7 +45.4 +50.0 +1.1 +5.6 −4.1 +37.0

1.0× 1.0× 2.2× 159× 1.0× 1.0× 1.0× 1.0× 150×

1.0× 1.0× 2.6× 169× 1.0× 1.0× 1.0× 1.0× 177×

• Progressive Party: reformulations (replacing a nonlinear max with a simple linear combination, np.triu_indices(n_guests, k=1) to enable a single vectorized sum() rather than iterating over pairs), symmetry breaking (guest ordering and period ordering), minor code cleanup. • Quadratic Assignment: loop restructuring (skipping zero-valued matrix entries), preprocessing (using numpy arrays instead of normal arrays), model reformulation (logical AND instead of multiplication). • Set Cover: preprocessing (element_to_sets lookup instead of scanning all sets for every element), infeasibility detection (if an element has no covering sets, immediately post model += False), implied constraint (on lower bound), model reformulation, symmetry breaking (cases where two sets have identical coverage and equal cost). • Traveling Salesman: global constraints (Element, Inverse), channeled auxiliary variable (previous city as inverse of next city), domain reduction (explicitly forbidding a city from being its own successor), symmetry breaking (a tour and its reverse are equivalent), implied constraint (each city must be the destination of exactly one edge). • Warehouse Location: preprocessing (using numpy arrays instead of normal arrays), alternative representations with output channeling (1D integer instead of 2D Boolean), global constraints (Element, LexLess), symmetry breaking (for identical warehouses), implied constraint (total capacity of open warehouses ≥ total demand).

4.2

Magnitude of Improvement

The better/equal/worse classification in Table 1 treats every improvement alike, but the gains differ by orders of magnitude. Figure 2 shows the relative objective improvement of the proposed model over the original on each test instance, and Table 3 summarizes it per problem together with the solve-time speedup. Two regimes are visible. For problems such as Progressive Party and Set Cover, both models exhaust the 60 s budget, but the proposed model reaches a substantially better objective within it – Progressive Party improves by 35–58%. For Mentor Matching and Warehouse Location, the proposed model instead solves the instances far faster, often in under a second – a speedup of more than two

8

60 40 20 0

Ba l. L at Go in Re lom ct bR . ule J o Me b S r nto ho rM p Pr atch o . Qu g. Pa ad rty .A ss Se ign. tC ov er Wa reh T o u SP se Lo c.

Objective improvement (%)

80

Figure 2: Relative objective improvement of the proposed model over the original on each test instance, grouped by problem. ■ the proposed model is better, ■ worse. The improvement is undefined for the one Balanced Latin Rectangle test instance on which the proposed model finds no solution; that instance is excluded here and from the per-problem mean in Table 3. The gains range from marginal (Quadratic Assignment, ≈1%) to large (Mentor Matching, up to 87%); a few instances degrade. orders of magnitude – because the agent replaced an expensive formulation (for example, scores recomputed in nested loops or a Boolean assignment matrix) with a global constraint or a precomputed lookup. The two largest cases, Mentor Matching and Warehouse Location, combine both effects: a much better objective and a dramatic speedup. At the same time, the magnitudes confirm that the method is not uniformly beneficial: on Traveling Salesman and a few individual instances the objective degrades (red bars in Figure 2), consistent with the per-problem pattern in Table 1. Overall, the binary better/worse counts understate the practical impact: where the agent helps, it often helps by a wide margin.

4.3

Non-Agentic Baselines

To assess the contribution of the full agent protocol beyond simply sampling and selecting among several candidate models, we compare the agent against two non-agentic baselines that reuse the same validation and selection tools but omit the agent’s reasoning, iteration, and repair. The single-shot baseline issues a single prompt to the same underlying LLM (Gemini 3 Flash, temperature 0.3) with the same high-level modeling-technique guidance, asking for one improved CPMpy model, but without validation feedback, iteration, or error recovery. The best-of-k baseline generalizes this: k independent single-shot candidates are generated, each is checked with the same validation procedure, and the best valid candidate (by training-instance performance) is selected. This matches the agent’s generation budget – the agent itself validates a comparable number of candidate models per problem – while withholding the agent’s iterative feedback and repair. To keep the comparison on equal footing, the baselines and the agent-proposed models were evaluated on the same shared machine and software as all other reported results. Table 4 reports the comparison. Increasing the number of sampled candidates does help – moving

9

Table 4: Non-agentic baselines vs. the agent: number of test instances (out of 27) on which the selected model beats the original, under a shared evaluation setup. The agent’s generation budget corresponds to roughly best-of-7. “Oracle” selects, per problem, the candidate that is best on the test instances (an upper bound that uses test data, not a fair baseline). Method

Better / 27

Single-shot (k = 1) Best-of-5 Best-of-10 Best-of-20 Oracle best-of-20 (by test, upper bound)

6 13 13 16 18

Agent (ReAct)

21

Listing 1: Part of the original model of the quadratic assignment problem. total_cost = sum( flow[f][g] * distance[i][j] * x[f, i] * x[g, j] for f in range(n) for g in range(n) for i in range(n) for j in range(n) if f != g )

from a single shot to best-of-20 raises the number of improved test instances – but it plateaus well below the agent, and even an oracle that selects candidates using the test instances does not close the gap. This indicates that the agent’s advantage stems not only from a larger search budget but from its ability to diagnose and repair failed formulations. The clearest example is the quadratic assignment problem: none of the 20 independently sampled single-shot candidates was valid (semantically equivalent and solvable on all training instances), whereas the agent produced a valid improved model by abandoning a failing formulation and reformulating it (Section 4.4). Many of the failed single-shot candidates stem from LLM coding mistakes such as calls to non-existent CPMpy methods and indexing numpy arrays by CPMpy expressions – the same class of error the agent diagnoses and works around at run time. We note that, at 27 instances, the confidence intervals of the agent and best-of-20 overlap; the comparison should therefore be read as indicative of where the gains come from rather than as a tight separation, and we treat a larger-sample version as future work.

4.4

Anatomy of a Selected Run

To illustrate the agent’s autonomous decision-making, we trace one full run on the quadratic assignment problem; the trace is informative because the agent’s first plan fails and it recovers mid-run by reformulating its strategy. The quadratic assignment problem is about assigning n facilities to n locations such that the sum over the flow between a pair of facilities times the distance between their assigned locations is minimized. The original model uses an O(n4 ) nested-loop objective over the Boolean assignment matrix x[f,i], as shown in Listing 1. Overall, the agent took 798 seconds and generated 9 model variants. The agent began by reading the given model and creating a to-do list for its next steps. In this to-do list, it already wrote down some ideas for optimization strategies. Text passages written in italics are taken from the agent’s log file and are included to illustrate the agent’s reasoning process. • Iteration 1. The agent created an integer array p of size n to assign facilities to locations and channeled it to the n × n Boolean matrix x, which is required as output. By doing that, it 10

could use the AllDifferent(p) global constraint to ensure that every facility is assigned to a different location. It also had the idea of using p for calculating the sum, but did not implement this idea in this iteration. “Actually, the original objective is quite heavy. Let’s try to optimize the objective calculation.” Creating an additional array and corresponding channeling constraints without really making use of it might be the reason why two of the training instances were solved worse than with the original model. • Iteration 2. Since using p could reduce the nested loop from O(n4 ) to O(n2 ), the agent tried to do that. It tried three times; however, it ended up with an IndexError every time because of calling distance[p[f]][p[g]] and dist_flat[idx]. In the fourth try it had a realization: “Wait, I just realized that dist_flat[idx] where idx is a CPMpy expression should work if dist_flat is a CPMpy-compatible array. Actually, CPMpy overloads __getitem__ for its own variables but not for numpy arrays. I should use cpmpy.expressions.core.Expression or just use the boolean variables, but in a more efficient way if possible. Let’s try to use the boolean variables, but simplify the sum.” So it discarded its plan and tried simplifying the sum. The result can be found in Listing 2. The new loop is still O(n4 ), but it filters out some pairs in advance. This model solved all three training instances better than the original model and was the proposed model in the end. One of the training instances was even solved optimally within 3.7 seconds. • Iteration 3. “Symmetry breaking. If the distance matrix or flow matrix has symmetries, we can break them. QAP is generally hard and doesn’t have obvious symmetries unless the matrices are special. But we can add Lexicographical constraints if there are identical facilities or locations.” In addition to the improved sum from the previous iteration, the agent added symmetry-breaking constraints for identical facilities and locations. However, since there are no identical facilities or locations in the training instances, this was just unnecessary overhead. The results on the training instances matched the objective values of Iteration 2, but the optimal instance took slightly longer to solve (6.19 s vs. 3.73 s). • Iteration 4. “Another approach: use the permutation variable p and use the Element constraint.” In this iteration, the agent finally implemented the idea it had in the first iteration but failed to implement in the second: using only an O(n2 ) loop to represent the 2-dimensional binary assignment matrix as an integer array. However, the results were mixed: 2 better, 1 worse. • Iteration 5. First, the agent tried to expand the code from Iteration 3 (symmetry breaking) with some implied constraints. However, it produced an error due to incorrect math. Its final try is also based on the model from Iteration 3, but with the difference that the objective is restructured: instead of summing over all pairs of facilities and locations independently, the terms are first grouped by facility–location pair (f, i) and collected into a subtotal, which is then added to the objective only if facility f is actually assigned to location i. This model had better results than the original model on the training instances. However, it was still worse than the models from Iterations 2 and 3.

5

Discussion and Conclusion

We introduced a novel agentic framework that automatically improves constraint models. It takes a baseline CPMpy model and only three small training instances as input, and iteratively creates and tests alternative model versions, applying various optimization strategies. In the end, the model considered best-performing is selected and returned. Across nine benchmark problems with three test instances each, our approach performed better on 21 of 27 instances, an improvement rate of 78%. 11

Listing 2: Part of the proposed model of the quadratic assignment problem. obj_terms = [] for f in range(n): for g in range(n): if f != g and flow[f, g] != 0: for i in range(n): for j in range(n): if i != j and distance[i, j] != 0: obj_terms.append( flow[f, g] * distance[i, j] * (x[f, i] & x[g, j])) total_cost = sum(obj_terms)

The results suggest that open-ended, empirically validated reformulation is a practical alternative to fixed-rule reformulation systems, and that LLM agents can design improved constraint models even with only a very small number of training instances. A comparison against single-shot and best-of-k baselines that reuse the same validation and selection tools indicates that these gains come from the agent’s iterative diagnosis and repair rather than from candidate sampling alone. In our experiments, the agent applied a diverse set of model optimization strategies, including symmetry-breaking and implied constraints, constraint reformulation, alternative variable representation, preprocessing, loop restructuring, and global constraints. It even combined several of these strategies, suggesting that LLM-based agents can reason about modeling decisions beyond simple template-based modifications. A few aspects suggest natural follow-up work. Semantic correctness is checked empirically, by injecting candidate solutions into the original model, rather than proved; this was reliable in our experiments – no proposed model was invalid on a test instance – but a formal equivalence or optimality-preservation guarantee would be a useful addition. The approach also benefits from solvers that make gradual progress on the training instances, so that performance differences are observable, and is less informative when improvements are rare. Finally, we removed existing symmetry-breaking constraints to leave room for improvement; quantifying the gains on already well-engineered models, and over larger instance sets, is a natural next step. We see several potential directions for future work. A first natural next step could be to extend our approach to constraint satisfaction problems, where, instead of improvements to the objective value, speedups in running time could be used as an indicator of good models. Additionally, the agent could generate the training instances itself, so the user does not need to provide them. Another interesting direction would be to apply our approach in a real-time scenario with only a single optimization instance. In this setting, the original model could run continuously, while the agent simultaneously searches for improved models by evaluating them on the same instance with shorter time limits. Once a model has been proposed, it can be used for the remaining solving time. Furthermore, comparing different underlying LLMs was not within the scope of this paper. Future work could therefore include further ablation studies on individual components of the framework, as well as evaluations using stronger underlying LLMs.

Acknowledgements Research was supported by the Austrian Science Fund (FWF) within the projects 10.55776/COE12 and 10.55776/P36420. This work was presented at LLM-Solve 2026, a FLoC & CP 2026 workshop, on July 19, 2026.

12

References [1] I. P. Gent, K. E. Petrie, and J. Puget, “Symmetry in constraint programming,” in Handbook of Constraint Programming, ser. Foundations of Artificial Intelligence, F. Rossi, P. van Beek, and T. Walsh, Eds. Elsevier, 2006, pp. 329–376. [Online]. Available: https://doi.org/10.1016/S1574-6526(06)80014-3 [2] B. M. Smith, “Modelling,” in Handbook of Constraint Programming, ser. Foundations of Artificial Intelligence, F. Rossi, P. van Beek, and T. Walsh, Eds. Elsevier, 2006, pp. 377–406. [Online]. Available: https://doi.org/10.1016/S1574-6526(06)80015-5 [3] W. van Hoeve and I. Katriel, “Global constraints,” in Handbook of Constraint Programming, ser. Foundations of Artificial Intelligence, F. Rossi, P. van Beek, and T. Walsh, Eds. Elsevier, 2006, pp. 169–208. [Online]. Available: https://doi.org/10.1016/S1574-6526(06)80010-6 [4] F. Rossi, P. van Beek, and T. Walsh, Eds., Handbook of Constraint Programming, ser. Foundations of Artificial Intelligence. Elsevier, 2006, vol. 2. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S1574652606X8001X [5] Ö. Akgün, A. M. Frisch, I. P. Gent, C. Jefferson, I. Miguel, and P. Nightingale, “Conjure: Automatic Generation of Constraint Models from Problem Specifications,” Artificial Intelligence, vol. 310, p. 103751, Sep. 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370222000911 [6] P. Nightingale, Ö. Akgün, I. P. Gent, C. Jefferson, I. Miguel, and P. Spracklen, “Automatically improving constraint models in Savile Row,” Artificial Intelligence, vol. 251, pp. 35–61, Oct. 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370217300747 [7] S. J. Zhang, J. Sun, C. Sun, Y. Liu, J. Ma, and J. S. Dong, “Constraint-based automatic symmetry detection,” in 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), 2013, pp. 15–25. [8] P. Spracklen, N. Dang, Ö. Akgün, and I. Miguel, “Automated streamliner portfolios for constraint satisfaction problems,” Artificial Intelligence, vol. 319, p. 103915, Jun. 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0004370223000619 [9] L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown, “SATzilla: portfolio-based algorithm selection for SAT,” Journal of Artificial Intelligence Research, vol. 32, no. 1, pp. 565–606, Jun. 2008. [10] M. Lindauer, H. H. Hoos, F. Hutter, and T. Schaub, “AutoFolio: An Automatically Configured Algorithm Selector,” Journal of Artificial Intelligence Research, vol. 53, pp. 745–778, Aug. 2015. [Online]. Available: https://jair.org/index.php/jair/article/view/10955 [11] F. Hutter, H. H. Hoos, and K. Leyton-Brown, “Sequential Model-Based Optimization for General Algorithm Configuration,” in Learning and Intelligent Optimization, C. A. C. Coello, Ed. Berlin, Heidelberg: Springer, 2011, pp. 507–523. [12] Y. Mechqrane and C. Bessiere, “Active Constraint Acquisition Using Large Language Models,” Journal of Artificial Intelligence Research, vol. 85, Feb. 2026. [Online]. Available: https://www.jair.org/index.php/jair/article/view/19277 [13] F. Régin, E. De Maria, and A. Bonlarron, “Combining Constraint Programming Reasoning with Large Language Model Predictions,” in 30th International Conference on Principles and Practice of Constraint Programming (CP 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), P. Shaw, Ed., vol. 307. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 25:1–25:18. [Online]. Available: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.25 [14] K. Michailidis, D. Tsouros, and T. Guns, “Constraint Modelling with LLMs Using In-Context Learning,” in 30th International Conference on Principles and Practice of Constraint Programming (CP 2024), ser. Leibniz International Proceedings in Informatics (LIPIcs), P. Shaw, Ed., vol. 307. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 20:1–20:27. [Online]. Available: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.20 [15] ——, “CP-Bench: Evaluating large language models for constraint modelling,” in ECAI 2025 - 28th European Conference on Artificial Intelligence, 25-30 October 2025, Bologna, Italy - Including 14th Conference on Prestigious Applications of Intelligent Systems (PAIS 2025), ser. Frontiers in Artificial Intelligence and Applications, I. Lynce, N. Murano, M. Vallati, S. Villata, F. Chesani, M. Milano, A. Omicini, and M. Dastani, Eds., vol. 413. IOS Press, 2025, pp. 861–868. [Online]. Available: https://doi.org/10.3233/FAIA250890

13

[16] Y. Song and E. Cohen, “Do LLMs Understand Constraint Programming? Zero-Shot Constraint Programming Model Generation Using LLMs,” in Learning and Intelligent Optimization, Y. Zhang, M. Hladík, and H. Moosaei, Eds. Cham: Springer Nature Switzerland, 2026, pp. 16–31. [17] S. Szeider, “CP-Agent: Agentic Constraint Programming,” in International Workshop on Agentic Engineering (AGENT@ICSE 2026), 2026, to appear, preprint at https://arxiv.org/abs/2508.07468. [18] A. Pellegrino and J. Mauro, “When Words Change the Model: Sensitivity of LLMs for Constraint Programming Modelling,” Nov. 2025, arXiv:2511.14334 [cs]. [Online]. Available: https://arxiv.org/abs/2511.14334 [19] F. Voboril, V. Peruvemba Ramaswamy, and S. Szeider, “Generating Streamlining Constraints with Large Language Models,” Journal of Artificial Intelligence Research, vol. 84, Oct. 2025. [Online]. Available: https://www.jair.org/index.php/jair/article/view/18965 [20] ——, “StreamLLM: Enhancing Constraint Programming with Large Language Model-Generated Streamliners,” in 2025 IEEE/ACM 1st International Workshop on Neuro-Symbolic Software Engineering (NSE). Ottawa, ON, Canada: IEEE, May 2025, pp. 17–22. [Online]. Available: https://ieeexplore.ieee.org/document/11039264/ [21] ——, “Balancing Latin Rectangles with LLM-Generated Streamliners,” in 31st International Conference on Principles and Practice of Constraint Programming (CP 2025), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. G. de la Banda, Ed., vol. 340. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, pp. 36:1–36:17. [Online]. Available: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.36 [22] T. Guns, “CPMpy: Constraint Programming and Modeling in Python — CPMpy documentation.” [Online]. Available: https://cpmpy.readthedocs.io/ [23] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. R. Narasimhan, and Y. Cao, “ReAct: Synergizing Reasoning and Acting in Language Models,” in The Eleventh International Conference on Learning Representations (ICLR 2023), 2023. [Online]. Available: https://openreview.net/forum?id=WE_vluYUL-X [24] D. J. Abraham, R. W. Irving, and D. F. Manlove, “Two algorithms for the Student-Project Allocation problem,” Journal of Discrete Algorithms, vol. 5, no. 1, pp. 73–90, Mar. 2007. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S1570866706000207

14

Related documents

• SLBench: Evaluating How LLM Agents Follow Logical Relations in Skills#361415
• Engineering Simplicity: Simple Mechanism Interfaces Steer LLM Agents#1131207
• Break It Down, Pass It On: Cross-Task Skill Transfer in LLM Agents#471273
• Hypothesis-Driven Skill Optimization for LLM Agents#300012
• Implicit Manipulation for Skill Selection in LLM Agents with Semantic Matching#632785