Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy
This paper presents CPMpy, a modular open-source framework that translates high-level finite-domain integer constraint models into various lower-level solving formalisms (CP, SMT, ILP, PB, and SAT) to enable easy comparison of different solving technologies without requiring manual remodelling.
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
In the vast landscape of artificial intelligence, there is a persistent challenge known as the model-and-solve approach. Imagine a person trying to organize a complex event, such as a conference with hundreds of speakers, rooms, and time slots. They do not write a step-by-step computer program to figure out the schedule. Instead, they write down a set of rules: "Speaker A cannot be in Room B," "Room C must be used before 2 PM," and "Speaker D must speak after Speaker E." This list of rules is called a constraint model. It is a high-level description of the problem, written in a language that humans can understand. The computer's job is then to take these rules and find a solution that satisfies them all.
The difficulty arises because there is no single computer program that is best at solving every type of rule. Some programs are excellent at handling logical "if-then" statements, while others are better at arithmetic calculations or managing large lists of possibilities. Researchers have built many different types of these solving programs, each with its own strengths and weaknesses. However, a major hurdle exists: a problem written for one type of solver often cannot be understood by another. To use a different solver, a human expert usually has to manually rewrite the entire set of rules into a new format, a tedious and error-prone process that limits the ability to compare which tool works best for a specific task.
A team of researchers at KU Leuven and other institutions has developed a solution to this translation problem. They created a software library called CPMpy that acts as a universal translator for these constraint models. Their work focuses on taking a high-level description of a problem, written with standard mathematical and logical rules, and automatically converting it into the specific language required by five different families of solving technologies. These technologies range from constraint programming solvers, which are specialized for complex logical puzzles, to integer linear programming solvers, which excel at optimization problems, and even to SAT solvers, which are designed to check the truth of logical statements. The researchers did not just build a translator; they built a modular pipeline where each step of the conversion process is a distinct, reusable component. This allows the system to strip away complex features that a specific solver cannot handle, replacing them with simpler, equivalent rules that the solver can understand.
The core of their method is a "waterfall" of transformations. When a model enters the system, it first undergoes a safety check to ensure that any mathematical operations, such as division, are defined for all possible values. If a division by zero is possible, the system adds a guard to prevent it. Next, the system removes any "not" operators that might be buried deep inside complex expressions, pushing them down until they only apply to simple variables. This simplifies the logical structure. The system then breaks down "global constraints," which are powerful, high-level rules like "all these people must have different schedules," into basic building blocks that simpler solvers can process.
As the model moves down the pipeline, it is flattened. Complex, nested expressions are replaced with simple variables, and the system keeps track of these replacements to avoid creating duplicate variables. This step is crucial because many solvers cannot handle rules where one rule is nested inside another. For solvers that only understand linear equations, the system performs a process called linearization. It converts logical rules and inequalities into straight-line equations. Finally, for solvers that only work with true-or-false variables, the system encodes every integer number into a series of Boolean switches. Throughout this entire process, the system is careful to preserve the exact meaning of the original problem. It ensures that if a solution exists for the original high-level model, a solution will exist for the translated low-level model, and vice versa.
To test their system, the researchers took 250 real-world optimization problems from a major international competition. They ran these problems through their translation pipeline and fed the results into three different types of solvers: a leading integer linear programming solver, a pseudo-boolean solver, and a maximum satisfiability solver. They measured how long it took each solver to find the best possible answer. The results showed that the translation process significantly changed the structure of the models. The number of rules and variables often increased dramatically as the complex high-level rules were broken down into their simplest forms. However, this expansion was necessary to make the problems understandable to the different solvers.
The study also revealed that the way a model is translated matters greatly for performance. For the integer linear programming solver, using specialized ways to break down complex rules led to faster solving times. For the other solvers, the impact was more nuanced. The researchers found that for some solvers, a standard translation worked best, while for others, a more aggressive translation that treated numbers as simple true-or-false switches was superior. They discovered that a one-size-fits-all approach does not work; the best translation strategy depends entirely on the specific solver being used. In fact, for one type of solver, using the most efficient translation for another type actually made the solving process slower. This highlights the importance of having a flexible system that can adapt the translation to the target tool.
The researchers concluded that their modular approach successfully bridges the gap between high-level problem modeling and low-level solving technologies. By automating the translation, they allow users to write a problem once and then test it against multiple different solving engines without manual rewriting. This capability enables a direct comparison of which technology is best suited for a specific application. While the translation process inevitably increases the size of the problem model, the ability to leverage the strengths of different solvers outweighs this cost. The work demonstrates that with the right translation tools, the diverse world of constraint solving can be made accessible and comparable, helping researchers and practitioners find the most effective solutions for complex combinatorial problems.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.