Constraint programming
Constraint Programming (CPP) solves Constraint Satisfaction (CSP) type problems. A CSP is a modeling problem in the form of a set of constraints imposed on variables, each of these variables taking its values in a defined domain.
A CSP is defined by a triplet (X, D, C, R) such that:
- X = {X1, X2,…,Xnot} the set of problem variables;
- D a function which associates with each variable Xi its domain (set of possible values) D (Xi);
- C = C1,VS2,…,VSk} the set of constraints.
Constraint Programming Solution
Solving a CSP consists in assigning values to the variables, such that all the constraints are satisfied. For this, we need a precise vocabulary:
- An assignment is an instance of certain variables by values from their respective domains. We will denote by A = {(X1, V1),…} assignment that instantiates the variable X1 by the value V1, etc;
- An assignment is said to be total if it instantiates all the variables of the problem, otherwise it is said to be partial;
- An assignment A violates a constraint Ck if all the variables of Ck are instantiated in A and if the relation defined by Ck is not checked by assignment:
- A total or partial assignment is consistent if it does not violate any constraint, otherwise it is said to be inconsistent;
- A CSP solution is a consistent total assignment.
In constraint programming, when a CSP has no solution, it is said to be overconstrained. In this case, one can find the total assignment that violates the fewest possible constraints. We then speak of max-CSP.
Another possibility in constraint programming 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 constraints have the same weight.
When a CSP admits several different solutions, it is said to be 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 to 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 owns a piece of land with 16 plots (4 rows and 4 columns) forming a chessboard. He wants to arrange the wind turbines in such a way that they are not in contact. Two wind turbines are in mesh if they are on the same line, 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. Each wind turbine i is associated with 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 model:
- Variables:
- X = {L1, THE2, THE3, THE4, VS1, VS2, VS3, VS4}
- Areas :
- D (L1) = D (L2) = D (L3) = D (L4)={1,2,3,4}
- D (C1) = D (C2) = D (C3) = D (C4)={1,2,3,4}
- Constraints:
- VSlig = allDiff ({L1, THE2, THE3, THE4}) to have L valuesi all different from each other
- VScollar = allDiff ({C1, VS2, VS3, VS4}) to have C valuesi all different from each other
- VSdm= {Ci+ Li ! = Cj+ Lj / for all i and j in {1,2,3,4} and i! = j}
- VSdd= {Ci-THEi ! = Cj-THEj / for all i and j in {1,2,3,4} and i! = j}
- It is the union of these together.
This modeling is naive since all the constraints are considered 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 line etc). Constraint programming then consists of determining on which line the wind turbine placed on column i is located, the variable will be noted Xi :
- Variables:
- X = {X1, X2, X3, X4}
- Areas :
- D (X1) = D (X2) = D (X3) = D (X4)={1,2,3,4}
- Constraints:
- VSlig = allDiff ({X1, X2, X3, X4}) to have X valuesi all different from each other
- VSdm= {Xi+ i! = Xj+ j / for all i and j in {1,2,3,4} and i! = j}
- VSdd= {Xi-i! = Xj-j / for all i and j in {1,2,3,4} and i! = j}
- It is the union of these together.
Discussion
There are many other ways to model the problem. In this case, what is the best model? For this, there are three criteria for evaluating the relevance of the modelling: does it best model the problem? was the modeling trivial? does the modeling solve the problem effectively?
Solving a CSP
Solving a CSP is an Np-Complete problem in the general case. The resolution mechanism consists of repeating the following two steps:
- reduction of problems by filtering;
- traversing the search tree.
These two steps call on notions such as the consistency of arcs or the propagation of constraints that we will not develop in this course. There are many CSP solvers such as the Google OR-tools library.
