The constraint propagation algorithm

The constraint propagation algorithm is straightforward in principle. When the domain of a decision variable is modified, the constraints containing that variable are examined to determine whether any values in the domains of other decision variables are now inconsistent.

To see how the propagation algorithm works with constraints, consider the constraint x <= y, written with the following fragment of code: 


  IloCPEngine cp;
  ...
  IlcIntVar x(cp,0,3), y(cp,0,2); 
  cp.add( x <= y );

When this constraint is added to the optimizer, the invariant expressed in the previous section becomes active and reduces the domain of x by removing the value 3. For the moment, that is all that can be deduced from the constraint. Since the constraint has to be taken into account by CP Optimizer every time one of the variables in it is modified, the constraint itself is physically attached to these two variables.

CP Optimizer has been designed to automate and to optimize the reduction of the domains of decision variables. The CP Optimizer propagation algorithm for that purpose is straightforward in principle. When the domain of a decision variable is modified, the constraints containing that variable are examined to determine whether any values in the domains of other decision variables are now inconsistent. If this is the case, necessary domain reductions are carried out in turn.

The examination of the constraints incident on a variable is triggered by any modification of that variable. There are several different kinds of modifications, depending on the class of variable under consideration. Those modifications are referred to as propagation events.

For the class of decision variables, there are, in fact, these propagation events:

  • value means that a value has been assigned to the decision variable, that is, the variable has been fixed;

  • range indicates that the minimum of the domain has increased or the maximum of the domain has decreased;

  • domain indicates that the domain of the decision variable has been modified.

When you define a new class of constraint, you must also define the propagation events for that class of constraint. You do so by means of the pure virtual member function, post.

Sometimes more than one event can be triggered after a variable modification. Specifically, the value event is always accompanied by the range and domain events. Likewise, a range event is always accompanied by a domain event.

Consider a search decision variable, var, with a domain containing only two values, value1 and value2, where value1 < value2. If you add a constraint that var != value1, three events are triggered:

  • the domain event is triggered since value1 is actually removed from the domain of var;

  • the range event is triggered since the minimal boundary of the domain of var has been increased;

  • the value event is triggered since the variable is fixed by the reduction of its domain to a single value.