Constraint Programming (PPC) makes it possible to solve Constraint Satisfaction (CSP) type problems. A CSP is a modeling problem in the form of a set of constraints posed on variables, each of these variables taking its values in a defined domain.
Constraint Programming Solution
Solving a CSP consists of assigning values to variables, so that all the constraints are satisfied. For this, we need a precise vocabulary:
In constraint programming, when a CSP has no solution, it is said to be overconstrained. In this case, we can find the total assignment that violates the fewest constraints possible. We then speak of max-CSP.
Another possibility in programming by constraints is to assign a weight to each constraint, one then seeks to minimize the weight of the violated constraints. We then speak of VCSP (valued). A max-CSP is a VCSP where all the constraints have the same weight.
When a CSP admits several different solutions, we say that it is under-constrained. If the solutions are not all equal, then it is possible to establish preferences between the solutions. We add a function which associates a numerical value with each solution, representing the quality of this solution. The objective is to maximize this objective function. We then speak of CSOP (constraint satisfaction optimization problem).
Example of Constraint Programming: n-queens problem
A builder has land with 16 plots (4 rows and 4 columns) forming a chessboard. He wants to dispose of the wind turbines in such a way that they are not engaged. Two wind turbines are engaged if they are on the same row, the same column or the same diagonal.
Constraint programming 1
The variables are the row and column positions of the wind turbines on the chessboard. We associate with each wind turbine i two variables Li and Ci corresponding respectively to the row and the column on which to place the wind turbine. We have the following constraint programming modeling:
This modelization is naive since one considers all the constraints without looking for their meaning.
Constraint programming 2
It is easy to notice that there will be at least one wind turbine per column of the chessboard (or row, etc.). The programming by constraints then consists in determining on which row is the wind turbine placed on column i, the variable will be noted Xi :
There are many other ways to model the problem. In this case, what is the best model? For that, there are three criteria making it possible to evaluate the relevance of the modeling: does it best model the problem? was the modeling trivial? does modeling allow the problem to be solved effectively?
Resolution of a CSP
The resolution of a CSP is a Np-Complete problem in the general case. The resolution mechanism consists of repeating the following two steps:
- reduction of problems by filtering;
- browsing the search tree.
These two stages make use of notions such as the consistency of arcs or the propagation of constraints that we will not develop in this course. There are many solvers of a CSP such as for example the Google OR-tools library.