Constraint programming

Constraint programming (CPP) helps to solve decision-making problems. An optimization problem is solved successively after several decision problems. For example, to determine a shorter path, we will try to find a path of less than 100 (possible), then less than 50 (impossible), then less than 75, and so on. until you find the optimal solution. CPP has a broader scope than exact methods or meta-heuristics.

Definition

The CPP solves a constraint satisfaction problem (CSP).

The latter is defined by a triplet <X, D, C> with X the set of variables, D the set of domains and C the set of constraints. Domain Dis the set of possible values for the variable Xi. Each constraint Cj is defined by its arity (the number of variables it covers), the list of these variables and the set of tuples that satisfy it.
  • variables : A, B, C, D
  • domains :
    • DA = {1,4,5,8}
    • DB = {2,3,5,7,9}
    • DC = {4,8,9}
    • DD = {1,4,5,7,9}
  • contraints :
    • C1(A,C) : {(1,7); (1,9); (5,9); (8,9)}
    • C2(A,D) : (1,1);(1,5);(5,5);(5,9);(8,9)}
    • C3(C,D) : {(4,1);(8,1);(9,7)}
    • C4(B,D) : {(2,7);(2,9);(5,8);(7,9);(9,9)}

It is possible to encode the constraints in extension, by a set of tuples, or in intention, by using operators whose semantics are known. An instantiation is a complete assignment of values to variables, for example {<A, 1>, <B, 7>, <C, 4>, <D, 9>}. Instantiation is a valid solution if the values given to variables such as all constraints are checked.

There is talk of partial or complete instantiation (if it takes all the variables or not), and inconsistent or consistent (if valid constraints or not). A valid solution is therefore a complete and consistent instantiation.

Naive method : Generate & Test

We generate all possible assignments. Then we check if they are consistent, as soon as an assignment is consistent we have a valid solution.

We have a problem with n variables, each one can take only two values, the processor makes 1,000,000 calculations per second. For 30 variables, the resolution takes at most 1s, for 50 variables, we go to 11 days; for 70 variables it is necessary to wait 317 centuries.

With backtrack

The allocation tree is generated and then traversed in depth. If a partial assignment (during the course) is inconsistent, then the corresponding subtree is cut.

It’s like Branch & Cut.

ppc1

This method does not generate the entire possibilities tree contrary to the naive method. On the other hand, all the constraints are tested at each partial assignment and the convergence time also depends on the order of the variables.

Constraint propagation resolution

This method consists in propagating the constraints in the domain of the variables.

For example, take x between 0 and 10 and y between 3 and 9; then with the constraint x> y we can restrict the domain of X between 4 and 10.

ppc2

There are three cases in which information is spread:

  • when a domain is reduced
  • when one of the boundaries of the domain is changed
  • when a domain is a singleton.

It is then possible to propagate the information once (node-consistency), twice (arc-consistency) or more.

In the consistency node, for each unassigned variable Xi in A, we remove from DXi of any value v such that the assignment A ∪{(Xi,v)} is inconsistent. The we propagate the allowed values in depth.

ppc3

In the arc-consistency, for each variable Xi not affected in A, we remove from DXi any value v such that there exists an unaffected variable Xj for which, for any value w of DXj, the assignment A ∪{(Xi,v);(Xj,w)} is inconsistent. Propagate the allowed values in depth.

ppc4

The larger the comparison tuple, the longer is the computation time to define the valid domain of the variables. The arc-consistency is less effective than the node-consistency if the domains are large.

 

Publicités