Constraint programming

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.

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

  • X={X1,X2,…,Xn} the set of variables;
  • D a function that associates each variable Xi with its domain (set of possible values) D(Xi);
  • C=C1,C2,…,Ck} the set of constraints

CSP solution

Solving a CSP is to assign values to variables such that all constraints are satisfied. For that, we need a precise vocabulary:

  • An assignment is an instance of values on variables of their respective domains. We will denote A={(X1,V1),…} the assignment which instantiates the variable X1 by the value V1, etc;
  • An assignment is called total if it instantiates all the variables of the problem, otherwise it is called 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.

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.

Modeling 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 respectively corresponding to the line and the column on which to place the wind turbine. We have the following modeling:

  • Variables:
    • X={L1, L2, L3, L4, C1, C2, C3, C4}
  • Domains:
    • 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:
    • Clig = allDiff({L1, L2, L3, L4}) -> Li are all differents
    • Ccol = allDiff({C1, C2, C3, C4}) -> Ci are all differents
    • Cdm={Ci+Li != Cj+Lj / for  i and j in {1,2,3,4} and i != j}
    • Cdd={Ci-Li != Cj-Lj / for i and j in {1,2,3,4} and i != j}
    • C is the union of these sets

This modeling is naive since we consider all the constraints without seeking their meaning.

Modeling 2

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:

  • Variables:
    • X={X1, X2, X3, X4}
  • Domains:
    • D(X1)=D(X2)=D(X3)=D(X4)={1,2,3,4}
  • Constraintes:
    • Clig = allDiff({X1, X2, X3, X4})
    • Cdm={Xi+i != Xj+j /for i and j in {1,2,3,4} and i != j}
    • Cdd={Xi-i != Xj-j / for i and j in {1,2,3,4} and i != j}
    • C is the union of these sets

Discussion

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?

Publicités