Constraint programming

Constraint programming

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.

A CSP is defined by a triplet (X, D, C, R) such that:

  • X = {X1, X2,…, Xnot} the set of variables of the problem;
  • 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 of assigning values to variables, so 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 which 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 verified by the 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, 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, 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).

constraint programming

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:

  • 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 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 :

  • 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 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.