Constraint propagation

Constraint propagation is the process of communicating the domain reduction of a decision variable to all of the constraints that are stated over this variable.

Constraint propagation is the process of communicating the domain reduction of a decision variable to all of the constraints that are stated over this variable. This process can result in more domain reductions. These domain reductions, in turn, are communicated to the appropriate constraints. This process continues until no more variable domains can be reduced or when a domain becomes empty and a failure occurs. An empty domain during the initial constraint propagation means that the model has no solution.

For example, consider the decision variables y with an initial domain [0..10], z with an initial domain [0..10] and t with an initial domain [0..1], and the constraints

     y + 5*z <= 4
     t != z
     t != y

over these three variables.

The domain reduction of the constraint y + 5*z <= 4 reduces the domain of y to [0..4] and z to [0]. The variable z is thus fixed to a single value. Constraint propagation invokes domain reduction of every constraint involving z. Domain reduction is invoked again for the constraint y + 5*z <= 4, but the variable domains cannot be reduced further. Domain reduction of the constraint t != z is invoked again, and because z is fixed to 0, the constraint removes the value 0 from the domain of t. The variable t is now fixed to the value 1, and constraint propagation invokes domain reduction of every constraint involving t, namely t != z and t != y. The constraint that can reduce domains further is t != y. Domain reduction removes the value 1 from the domain of y.

Constraint propagation is performed on constraints involving y; however, no more domain reduction can be achieved and the final domains are:

• y = [0 2..4],

• z = [0] and

• t = [1].

To invoke the constraint propagation process in CP Optimizer, the propagate function of the optimizer object is called. In the C++ API, this function is IloCP::propagate; in the Java™ API, this function is IloCP.propagate; and in the C# API, this function is CP.Propagate. This function invokes domain reduction on every constraint of the model and propagates the domain reductions. It returns true (IloTrue in the C++ API) if propagation succeeds; in other words, if no empty domains result. It returns false (IloFalse in the C++ API) otherwise.

As an example using the C++ API, a code that invokes propagation on the model above is;

    IloIntVar y(env, 0, 10);
    IloIntVar z(env, 0, 10);
    IloIntVar t(env, 0, 1);
    IloModel model(env);
    model.add(y + 5*z <= 4);
    model.add(t != z);
    model.add(t != y);
    IloCP cp(model);
    if (cp.propagate()){
      cp.out() << " Domains reduced: " << std::endl;
      cp.out() << " Domain of y = " << cp.domain(y) << std::endl;
      cp.out() << " Domain of z = " << cp.domain(z) << std::endl;
      cp.out() << " Domain of t = " << cp.domain(t) << std::endl;
    }else{
      cp.out() << " Model has no solution." << std::endl;
    }

The call to the method IloCP::domain(IloIntVar x) is directed to an output stream to display the current domain of the decision variable x. Running this code produces the output:

 Domains reduced:
 Domain of y = [0 2..4]
 Domain of z = [0]
 Domain of t = [1]