Propagation of arithmetic constraints

Propagation of arithmetic constraints works to reduce the bounds of the incident decision variables.

In the C++ API, CP Optimizer can handle arithmetic expressions created with the operators +, -, * and /. Arithmetic constraints are created with arithmetic expressions and operators like ==, <=, >=, < and >.

For example, the constraint 17*p*q + x/y <= 100, where p, q, x and y are decision variables, can be handled by CP Optimizer. These operators are discussed in more detail in the section Arithmetic constraints and expressions. The Java™ API and C# API equivalents of the operators are listed there as well.

Apart from a few cases that are described below, arithmetic constraints do not achieve full domain reduction because there does not always exist an efficient algorithm for full domain reduction. Thus, domain reduction is mostly applied to bounds of decision variables and is called bound reduction. Bound reduction is considered as a good trade-off between the number of values removed and the efficiency of the domain reduction algorithm.

For example, consider the model:

    IloIntVar x(env, -7, 7);
    IloIntVar y(env, -7, 7);
    IloModel model(env);
    model.add(0.5*x + 3*y == 5);

The two solutions of this model are x = -2, y = 2 and x = 4, y = 1. Full constraint propagation would give the domain of x as [-2 4] and the domain of y as [1 2]. However, CP Optimizer does not perform this domain reduction. The constraint propagation engine does not create “holes” in the domain of x. The reduced domain of x is [-2..4].

There are exceptions to this behavior. These are binary constraints of the form y == a*x + b, where y and x are variables and a and b are numerical values. In this case, full domain reduction is achieved.

For instance consider the constraint y == 2*x over the variables x with domain [1..3] and y with domain [0..10]. This constraint forces y to be even. Full domain reduction is performed and reduces the domain of y to [2 4 6]. The main reason for achieving full domain reduction in this case is that it does not hurt the efficiency of constraint propagation, and it can be effective to propagate holes in domains from a constraint to another when there are linking constraints like x == y in a model.

Another case is that of linear inequalities such as x + 3y - 4z <= 10. Achieving bound reduction for these constraints is sufficient to achieve full domain reduction.

CP Optimizer provides bound reduction for expressions such as absolute value, minimum, maximum and piecewise linear functions. On these expressions, achieving bound reduction is sufficient to maintain full domain reduction.

In the C++ API, an absolute value expression is created with the function IloAbs. Consider the following code:

    IloIntVar x(env, -10, 20);
    IloIntVar y(env, -3, 4);
    IloModel model(env);
    model.add(y == IloAbs(x));
    IloCP cp(model);
    if (cp.propagate()){
      cp.out() << " Domains reduced: " << std::endl;
      cp.out() << " Domain of x = " << cp.domain(x) << std::endl;
      cp.out() << " Domain of y = " << cp.domain(y) << std::endl;
    }else{
      cp.out() << " Model has no solution." << std::endl;
    }

Running this code, the domains of both x and y are reduced. The domain of y is reduced so that it is positive and the domain of x is reduced to take into account the maximum value of y:

 Domains reduced:
 Domain of x = [-4..4]
 Domain of y = [0..4]

In the C++ API, minimum and maximum values expressions over a set of variables are created with the IloMin and IloMax expressions. For example consider the model:

    IloIntVar x(env, 0, 10);
    IloIntVar y(env, 4, 6);
    IloIntVar u(env, 2, 10);
    IloModel model(env);
    model.add(u == IloMin(x, y));
    IloCP cp(model);
	 if ( cp.propagate() ) {
      cp.out() << " Domains reduced: " << std::endl;
      cp.out() << " Domain of x = " << cp.domain(x) << std::endl;
      cp.out() << " Domain of y = " << cp.domain(y) << std::endl;
      cp.out() << " Domain of u = " << cp.domain(u) << std::endl;
    }else{
      cp.out() << " Model has no solution." << std::endl;
    }

The value of u cannot exceed the smallest upper bound of x and y, that is 6. Moreover, x nor y cannot have a value smaller than the lower bound of u, which is 2. The domains of the variables after running this code are:

 Domains reduced:
 Domain of x = [2..10]
 Domain of y = [4..6]
 Domain of u = [2..6]