Constraint Programming solves Constraint Satisfaction (CSP) problems. A CSP is a modeling problem in the form of a set of constraints placed on variables, each of these variables taking its values in a defined domain.
Solving a CSP is to assign values to variables such that all constraints are satisfied. For that, we need a precise vocabulary:
When a CSP has no solution, it is said that it is over-constrained. In this case, we can find the total allocation that violates the fewest constraints. We are talking about max-CSP.
Another possibility is to assign a weight to each constraint, so we try to minimize the weight of the constraints violated. This is called VCSP (valued). A max-CSP is a VCSP where all constraints have the same weight.
When a CSP admits several different solutions, it is said that it is under-constrained. If the solutions are not all equivalent, then it is possible to establish preferences between the solutions. We add a function that associates a numerical value with each solution, representing the quality of this solution. The goal is to maximize this objective function. This is called CSOP (constraint satisfaction optimization problem).
Example: problem of n-queens
A builder has a field with 16 plots (4 rows and 4 columns) forming a chessboard. He wants to have wind turbines so that they are not engaged. Two wind turbines are engaged if they are on the same line, the same column or the same diagonal.
The variables are the row and column positions of the wind turbines on the chessboard. Each wind turbine i is associated with two variables Li and Ci respectively corresponding to the line and the column on which to place the wind turbine. We have the following modeling:
This modeling is naive since we consider all the constraints without seeking their meaning.
It is easy to notice that there will be at least one wind turbine per column of the chessboard (or line etc). The problem is then to determine on which line is the wind turbine placed on the column i, the variable will be noted Xi:
There are many other ways to model the problem. In this case, what is the best modeling? For this, there are three criteria for assessing the relevance of modeling: does it best model the problem? was the modeling trivial? can modeling solve the problem effectively?