Constraint Model

Definition and Structure

A constraint model is the formal representation of a constraint satisfaction problem (CSP). In concrete terms, a constraint model defines:

• Constraint variables, each with an appropriate variable domain.
• Constraints that restrict combinations of variable assignments.
• A call to a constraint solver to enumerate solutions that are consistent with the posted constraints.

Evidence from a published implementation states: "The code is a constraint model, because constraint variables with appropriate variable domains are defined, constraints are defined (here by post), and finally the constraint solver is called to generate solutions which are consistent with the posted constraints." (b99c9fa6)

Components in Practice

In the PyChoco/Choco API used by recent LLM-based generation work, a constraint model is built by:

1. Instantiating integer variables with bounds, e.g., model.intvar(0, max_cost, f"arc_cost_{i}") (c75586e0).
2. Posting global constraints such as model.all_different(tour) and arithmetic constraints such as model.arithm(...) or model.sum(...) followed by .post() (b99c9fa6, c75586e0).
3. Calling solver.find_all_solutions() (or similar) to produce solutions consistent with the model (b99c9fa6, c75586e0).

Automated Generation of Constraint Models

Refinement-Based Approach

Automating the constraint modelling process has been identified as "one of the key challenges facing the constraints field, and one of the principal obstacles preventing widespread adoption of constraint solving." The refinement-based approach works as follows: "a user specifies a problem in an abstract constraint specification language and it is then automatically refined into a constraint model." The Conjure system implements this approach for the Essence specification language, "refined into a constraint model" with broad coverage of Essence (arxiv:1109.1774v1).

Integration with Database Query Languages

Constraint modelling has been integrated with relational database systems by proposing "extensions of standard query languages such as relational algebra and SQL, by adding constraint modelling capabilities to them." Non-deterministic extensions, via a guessing operator that declares a set of relations to have an arbitrary extension, "result in languages with higher expressive power, able to express all problems in the complexity class NP." Syntactical restrictions yield polynomial data complexity (arxiv:cs/0601043v1).

LLM-Based Generation with Test-Driven Verification

Recent work demonstrates that "correct constraint models can be generated with the help of an LLM if one combines their verification with constraint solvers in an iterative loop." The architecture iterates through prompts to the LLM, generates Python code, runs the code (which calls a constraint solver), and verifies the output via a verify_solutions method acting as a validation checkpoint (49499ebb, e22022aa).

Key features of this test-driven approach:

• The user supplies "concrete constraints of a constraint problem," a "test method for checking these restrictions of the CSP in general," and "explanations as output if errors occur for guiding the LLM to a solution" (b99c9fa6).
• "If all relevant conditions are checked, then a generated model that passes verification can be regarded as correct" (b99c9fa6).
• The method "ensures complete (global) consistency and, in the case of the TSP, optimality of the resulting constraint model" (e22022aa).
• Generated models are expressed in Python using the PyChoco API, requiring the LLM to produce syntactically correct Python code that uses Choco's modeling primitives (c75586e0).

Input Forms for Model Generation

The published LLM-based approach accepts several input styles:

• A name of a commonly known CSP (e.g., N-Queen, TSP) that "was used when the LLM had been trained" (c75586e0).
• A natural-language description of restrictions (e.g., the Zebra Puzzle: "There are five houses. The Englishman lives in the red house…") (c75586e0).
• A general description of an abstract problem with a concrete task instance (c75586e0).

The reported implementation focuses on names as input (c75586e0).

Solvers and Descriptive Models

Constraint solvers "implement specific efficient algorithms that are general and work on descriptive models." However, those algorithms must be invoked through the solver's API; in the reported experiments the LLM did not use these APIs efficiently (e.g., find_all_optimal_solutions) but instead "generates an algorithm for the brute-force method" (e22022aa). The work notes that "specific prompts for leveraging these APIs should be developed to make use of these efficient algorithms" (e22022aa).

Example Problems Modeled

The LLM-based approach successfully generated and verified constraint models for several benchmark problems:

• N-Queen (with N = 8) (b99c9fa6)
• Magic Square (b99c9fa6)
• Map Coloring (b99c9fa6)
• Travelling Salesman Problem (TSP) (b99c9fa6, c75586e0)

For Map Coloring and Magic Square only one-step iteration was needed; the N-Queen solution sometimes required several iterations due to API misuse, with error messages returned to the LLM in subsequent turns (b99c9fa6).

Scope and Limitations

The reported LLM-based approach is "particularly suitable for small to medium-sized CSPs or as a prototyping tool, while the scalability to industrial-size configuration tasks remains open for future work" (c75586e0). The approach is also bound to the expressive power and syntax of the chosen solver (PyChoco/Choco) (c75586e0).

Role in Knowledge Acquisition

Constraint modelling is described as "often complex and labor-intensive and triggers a need for enhanced knowledge acquisition support." Automated generation of constraint models from high-level descriptions can therefore ease the burden on knowledge engineers when translating domain constraints into formal representations (49499ebb).