The OPTMODEL Procedure
Indicator Constraints
An indicator constraint conditions the enforcement of a constraint on the value of a binary variable. For example, the indicator constraint
con indcon: y=0 IMPLIES sum{i in 1..10} (a[i] * x[i]) >= l;
means that if in a solution y is equal to 0, then the constraint 
must be satisfied, and if in a solution y is equal to 1, then the constraint might or might not be violated. The part of the indicator constraint that precedes IMPLIES is also known as the conditional of the indicator constraint, and the part that follows IMPLIES is the consequent. The binary variable in the conditional is the indicator variable.
When an indicator constraint is present in the model, first its consequent must be linearized if it is not already linear. After that, the presolver applies a big-M transformation, and the resulting linear constraint(s) is passed on to the solver.
For example, consider the indicator constraint that is mentioned earlier. If 
is bounded from below, then using 
in the constraint 
enforces the consequent if 
. On the other hand, if 
, then this constraint is satisfied for any x; thus the consequent is not enforced. This is the big-M transformation of the indicator constraint. The presolver uses the best big-M value that it can for every indicator constraint.
Note: If there is no provably correct big-M value, or if the value would be so big as to be likely to cause numerical difficulties, the presolver issues a warning and uses a value that is still likely to provide a useful solution.
Note: Because there is a binary variable in an indicator constraint, the solver that you use must be able to handle integrality restrictions. By default, the MILP solver is used when indicator constraints are present.
Note: Because the consequent of an indicator constraint must be linear, the LINEARIZE option is automatically set when the SOLVE or SAVE MPS statement is executed in the presence of indicator constraints. When the EXPAND statement is executed together with the LINEARIZE option, indicator constraints undergo a big-M transformation. When the EXPAND statement is executed without the LINEARIZE option, indicator constraints are displayed in their original form.
Here is an example of a more complex indicator constraint:
proc optmodel;
var x binary;
var y >= 0;
var z >= 1 <= 100;
var u binary;
con c0: x=0 implies y <= 10;
con c1: x=1 implies u*z = 50;
print "===== expand =====";
expand;
print "===== expand/linearize =====";
expand / linearize;
The EXPAND statements produce the output in Figure 58.
Figure 58: Expansion of Indicator Constraints
| ===== expand ===== |
Var x BINARY Var y >= 0 Var z >= 1 <= 100 Var u BINARY Constraint c0: x = 0 IMPLIES y <= 10 Constraint c1: x = 1 IMPLIES u*z = 50 |
| ===== expand/linearize ===== |
Var x BINARY Var y >= 0 Var z >= 1 <= 100 Var u BINARY Var _ADDED_VAR_[1] >= 0 <= 100 Constraint c0: y - 8388608*x <= 10 Constraint c1: _ADDED_VAR_[1] - 50*x >= 0 Constraint _ADDED_CON_[1]: _ADDED_VAR_[1] - z - u <= -1 Constraint _ADDED_CON_[2]: _ADDED_VAR_[1] - z - 100*u >= -100 Constraint _ADDED_CON_[3]: _ADDED_VAR_[1] - 100*u <= 0 Constraint _ADDED_CON_[4]: _ADDED_VAR_[1] - u >= 0 Constraint _ADDED_CON_[5]: _ADDED_VAR_[1] + 50*x <= 100 |
You can see that without the LINEARIZE option, the EXPAND statement simply displays the indicator constraints as they are specified.
In the linearized version, x has a large coefficient in constraint c0. This is the big-M value that is used here, even though in theory infinity is the only “correct” big-M value. The log file displays a warning about this:
WARNING: The big-M value (1.797693E308) generated for indicator constraint 'c0'
was lowered (to 100000) to avoid serious numerical difficulties. This
might affect the optimal solution and value. To avoid numerical issues,
you can bound the variables as much as reasonable or use the INTTOL=
option to decrease the integrality tolerance.
You can avoid this warning and help set a smaller big-M value by setting an upper bound on y.
Then you can see that the product u*z has been linearized using the constraints _ADDED_CON_[1] through _ADDED_CON_[4] and u*z has been replaced by _ADDED_VAR_[1] in indicator constraint c1. Afterward the indicator constraint itself is linearized using two linear constraints: c1 and _ADDED_CON_[5]. Two constraints are needed, because the big-M transformation must be applied to the equality in both directions—that is, as 
and as 
.
Linearization of nonlinear expressions can add indicator constraints to the updated model. The big-M transformation can produce large values when it is applied to these constraints, if the variables that the nonlinear expressions use are not suitably bounded. The following code shows an example that produces large big-M values:
proc optmodel;
var x >= -100;
max obj = abs(x);
expand / linearize;
The EXPAND statement produces the output in Figure 59. The constraints _ADDED_CON_[3] and _ADDED_CON_[4] have large big-M values that you can reduce by supplying a suitable upper bound for the variable x.
Figure 59: Linearization with Indicator Constraints
Var x >= -100 Var _ADDED_VAR_[1] Var _ADDED_VAR_[2] BINARY Maximize obj=_ADDED_VAR_[1] Constraint _ADDED_CON_[1]: x - _ADDED_VAR_[1] <= 0 Constraint _ADDED_CON_[2]: x + _ADDED_VAR_[1] >= 0 Constraint _ADDED_CON_[3]: x - _ADDED_VAR_[1] + 8388608*_ADDED_VAR_[2] >= 0 Constraint _ADDED_CON_[4]: x + _ADDED_VAR_[1] + 8388608*_ADDED_VAR_[2] <= 8388608 |
The log file displays a warning when large big-M values are detected in added indicator constraints:
WARNING: Linearization of the expression for 'obj' produced big-M values that
were lowered to avoid serious numerical difficulties. This might
affect the optimal solution and value. To avoid numerical issues,
you can bound the variables as much as reasonable or use the INTTOL=
option to decrease the integrality tolerance.