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.
For more details
please contact us
Name / First Name
Company
Your details
*
Your request
*

* Mandatory fields

  • 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