## Constraint programming

Constraint programming makes it possible 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 less than 100 (possible), then less than 50 (impossible), then less than 75, etc. until you find the optimal solution. PPC has a wider field of action than exact methods or meta-heuristics.

# Definition

PPC solves a constraint satisfaction problem (CSP).

_{i}is the set of possible values for the variable X

_{i}. Each constraints C

_{j}is defined by its arity (the number of variables on which it relates), the list of these variables and the set of tuples which satisfy it.

Let's take an example of a triplet:

- variables: A, B, C, D
- areas :
- D
_{TO}= {1,4,5,8} - D
_{B}= {2,3,5,7,9} - D
_{VS}= {4,8,9} - D
_{D}= {1,4,5,7,9}

- D
- constraints:
- VS
_{1}(A, C): {(1.7); (1.9); (5.9); (8.9)} - VS
_{2}(A, D): (1.1); (1.5); (5.5); (5.9); (8.9)} - VS
_{3}(C, D): {(4.1); (8.1); (9.7)} - VS
_{4}(B, D): {(2.7); (2.9); (5.8); (7.9); (9.9)}

- VS

It is possible to code the constraints in extension, by a set of tuples, or in intention, using operators whose semantics are known. An instantiation is a complete assignment of values to variables, for example { ,** , , }. Instantiation is a valid solution if the values given to the variables of which such as all the constraints are verified.**