Each variable may take on a certain number of values that make up its domain. Constraints create relations between variables and thus limit their domains. Constraint Programming solves optimization problems through a combination of two techniques:
- Variable selection and instantiation: choosing the next variable to consider, and the value it will be assigned in its domain
- Constraint propagation: applying the choices made during the previous step to domains of other variables
If the domain of a variable is empty following the constraint propagation step, then the choice made during the previous variable selection and instantiation step is reviewed; otherwise the process continues. Processing stops if it is possible to assign a value to all the problem’s variables (in which case you have a solution) or if no solution can be found (in which case the problem cannot be solved).
To harness the power of constraint propagation (i.e. its capacity to manage “industrial” problems), you must adopt a cautious approach to seeking the solution:
- It is possible to include your industry-specific knowledge of a problem during the variable selection and instantiation step, in order to find a solution more quickly
- However, research strategies are not always based on “industry-specific” experience, since it is not always relevant to transpose practices applied when solving a problem “manually” or via other techniques. In that case you must rely on modeling expertise to develop specific strategies which involve resolving sub-problems.
- In this context, constraint propagation can be successfully linked with other techniques than merely parsing a tree:
- tabu search, simulated annealing
- linear programming (used to propagate non-linear constraints coupled with a system of linear equations).
Efficient propagation is vital because it « breaks » the combinatorial. It is contingent upon the quality of the modeling and the representational power of the tools used. You can use a method that applies iterations to analyse a search’s behaviour in detail (by analyzing the impact of “bad decisions”) in order to improve:
- the completeness of the propagation
- the criteria for controlling the search