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
Email *
Phone number
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