The OPTMODEL Procedure
Linearization
PROC OPTMODEL supports the transformation of certain nonlinear expressions in objectives and constraints into equivalent linear forms. This enables the processing of some MINLP formulations by using the MILP solver. Use the LINEARIZE option with the EXPAND, SAVE MPS, or SOLVE statement to request the linearization transformations.
Linearization examines each nonlinear objective, constraint, or IMPVAR expression, replacing nonlinear subexpressions with equivalent linear subexpressions. Fixed variables are treated as constants to enable more opportunities for linearization. The transformations might require the creation of additional variables and constraints. For example, the product of binary variables can be replaced by a new binary variable, with added constraints to relate the new variable value to the original variable values.
The added variables are elements of the predefined array _ADDED_VAR_, which has an integer index that starts from 1. Added constraints are elements of the predefined array _ADDED_CON_, which has an integer index that starts from 1. You can specify the name _ADDED_VAR_ or _ADDED_CON_ in the EXPAND statement with the LINEARIZE option to examine the added variables or constraints in the transformed problem.
When the problem is updated, added variables and constraints are re-created during problem generation. The optimal values for added variables from one SOLVE statement might not be meaningful in the next SOLVE statement, so the values that are assigned to the variables are ignored when PROC OPTMODEL determines initial values for the solver. The procedure attempts to determine initial values that are consistent with the values of the user-defined variables.
The LINEARIZE option is most often used with the MILP solver, although it can be used with other solvers. The MILP solver does not support dual values and reduced costs. PROC OPTMODEL does not attempt to recover the dual values and reduced costs of a problem that has been transformed by linearization, and it reports missing values.
The following types of subexpressions can be transformed:
binary-binary products
binary-bounded products
polynomials with binary and bounded variables
MIN/MAX/ABS function calls, <> expressions, and >< expressions
linear ratio constraint bodies
Problem generation fails if linearization is unable to transform a nonlinear subexpression or if the required linear coefficients are out of range or undefined.
Binary-Binary Products
The product of two or more binary variables can be replaced by a new binary variable in combination with added constraints. For example, the product of binary variables 
for indices i in a set S can be replaced by a new binary variable z, with the following constraints:
The first set of constraints ensures that z is 0 when any is 0. The last constraint ensures that z is 1 when all are 1. This covers all the possibilities, so z is constrained to equal the product.
The following code shows a simple example of the binary-binary product transformation:
proc optmodel;
var x binary;
var y binary;
minimize obj = x*y + y*2*x;
con c: x*y >= 1;
expand / linearize;
solve linearize;
print x y;
The output is shown in Figure 66. PROC OPTMODEL recognizes that all the uses of 
are equivalent, and it reuses the same variable. The SOLVE statement invokes the MILP solver because the transformed problem uses binary variables. Note that the problem summary describes the problem before transformation.
Figure 66: Binary-Binary Products
Var x BINARY Var y BINARY Var _ADDED_VAR_[1] BINARY Minimize obj=3*_ADDED_VAR_[1] Constraint c: _ADDED_VAR_[1] >= 1 Constraint _ADDED_CON_[1]: _ADDED_VAR_[1] - x <= 0 Constraint _ADDED_CON_[2]: _ADDED_VAR_[1] - y <= 0 Constraint _ADDED_CON_[3]: - _ADDED_VAR_[1] + x + y <= 1 |
| Problem Summary | |
|---|---|
| Objective Sense | Minimization |
| Objective Function | obj |
| Objective Type | Quadratic |
| Number of Variables | 2 |
| Bounded Above | 0 |
| Bounded Below | 0 |
| Bounded Below and Above | 2 |
| Free | 0 |
| Fixed | 0 |
| Binary | 2 |
| Integer | 0 |
| Number of Constraints | 1 |
| Linear LE (<=) | 0 |
| Linear EQ (=) | 0 |
| Linear GE (>=) | 0 |
| Linear Range | 0 |
| Nonlinear LE (<=) | 0 |
| Nonlinear EQ (=) | 0 |
| Nonlinear GE (>=) | 1 |
| Nonlinear Range | 0 |
| Constraint Coefficients | 0 |
| Solution Summary | |
|---|---|
| Solver | MILP |
| Algorithm | Branch and Cut |
| Objective Function | obj |
| Solution Status | Optimal |
| Objective Value | 3 |
| Relative Gap | 0 |
| Absolute Gap | 0 |
| Primal Infeasibility | 0 |
| Bound Infeasibility | 0 |
| Integer Infeasibility | 0 |
| Best Bound | 3 |
| Nodes | 0 |
| Solutions Found | 2 |
| Iterations | 0 |
| Presolve Time | 0.00 |
| Solution Time | 0.01 |
| x | y |
|---|---|
| 1 | 1 |
Binary-Bounded Products
The product of a binary variable x and a bounded variable y can be replaced by a continuous variable, z, which is equal to 0 when x is 0 and equal to y when x is 1. You can also use a linearizable operand for y, such as an IMPVAR reference or a MIN/MAX/ABS function call, provided that the OPTMODEL presolver can determine the bounds for the operand. Let the lower bound for the value of y be L and the upper bound be U. Linearization adds the following constraints:
When x is 0, the second pair of constraints ensure that z is 0, and the first pair hold trivially, based on the bounds of y. When x is 1, the first pair of constraints ensure that 
. The second pair of constraints hold trivially, based on the bounds of y.
The following code shows a simple example of the binary-bounded transformation:
proc optmodel;
var x binary;
var y >=1 <=2;
minimize obj1 = x*y;
expand / linearize;
The output is shown in Figure 67.
Figure 67: Binary-Bounded Products
Var x BINARY Var y >= 1 <= 2 Var _ADDED_VAR_[1] >= 0 <= 2 Minimize obj1=_ADDED_VAR_[1] Constraint _ADDED_CON_[1]: _ADDED_VAR_[1] - y - x <= -1 Constraint _ADDED_CON_[2]: _ADDED_VAR_[1] - y - 2*x >= -2 Constraint _ADDED_CON_[3]: _ADDED_VAR_[1] - 2*x <= 0 Constraint _ADDED_CON_[4]: _ADDED_VAR_[1] - x >= 0 |
Polynomials with Binary and Bounded Variables
More complex expressions, including linearizable subexpressions that are raised to constant nonnegative integer powers, are handled by expansion into a sum of product terms. Each expanded product term can include zero or more binary variables in combination with an optional bounded operand or a general variable. These terms are then linearized, if necessary, using the binary-binary and binary-bounded product transformations. An expanded term that contains multiple variables and includes either a general variable or multiple bounded nonbinary variables cannot be linearized.
When processing products, PROC OPTMODEL recognizes that an operand like 
, where C is a constant and x is a binary variable, is a scaled version of the complement of x, 
. The expansion into product terms uses the rule 
to remove unneeded product terms.
The value of 
is not defined, so a linear subexpression 
is not linearized (as 1) unless PROC OPTMODEL can determine that the value of 
cannot be 0. A linear subexpression 
is treated as .
The following code shows an example of the polynomial transformation:
proc optmodel;
var x {1..4} binary;
minimize obj = (x[1] + x[2]) * (x[3] + x[4]);
con c: (x[1] + x[2] + x[3]) * x[4]**3 >= 1;
expand / linearize;
The output is shown in Figure 68.
Figure 68: Polynomial Linearization
Var x[1] BINARY Var x[2] BINARY Var x[3] BINARY Var x[4] BINARY Var _ADDED_VAR_[1] BINARY Var _ADDED_VAR_[2] BINARY Var _ADDED_VAR_[3] BINARY Var _ADDED_VAR_[4] BINARY Var _ADDED_VAR_[5] BINARY Minimize obj=_ADDED_VAR_[4] + _ADDED_VAR_[1] + _ADDED_VAR_[5] + _ADDED_VAR_[2] Constraint c: _ADDED_VAR_[1] + _ADDED_VAR_[2] + _ADDED_VAR_[3] >= 1 Constraint _ADDED_CON_[1]: _ADDED_VAR_[1] - x[1] <= 0 Constraint _ADDED_CON_[2]: _ADDED_VAR_[1] - x[4] <= 0 Constraint _ADDED_CON_[3]: - _ADDED_VAR_[1] + x[1] + x[4] <= 1 Constraint _ADDED_CON_[4]: _ADDED_VAR_[2] - x[2] <= 0 Constraint _ADDED_CON_[5]: _ADDED_VAR_[2] - x[4] <= 0 Constraint _ADDED_CON_[6]: - _ADDED_VAR_[2] + x[2] + x[4] <= 1 Constraint _ADDED_CON_[7]: _ADDED_VAR_[3] - x[3] <= 0 Constraint _ADDED_CON_[8]: _ADDED_VAR_[3] - x[4] <= 0 Constraint _ADDED_CON_[9]: - _ADDED_VAR_[3] + x[3] + x[4] <= 1 Constraint _ADDED_CON_[10]: _ADDED_VAR_[4] - x[1] <= 0 Constraint _ADDED_CON_[11]: _ADDED_VAR_[4] - x[3] <= 0 Constraint _ADDED_CON_[12]: - _ADDED_VAR_[4] + x[1] + x[3] <= 1 Constraint _ADDED_CON_[13]: _ADDED_VAR_[5] - x[2] <= 0 Constraint _ADDED_CON_[14]: _ADDED_VAR_[5] - x[3] <= 0 Constraint _ADDED_CON_[15]: - _ADDED_VAR_[5] + x[2] + x[3] <= 1 |
MIN/MAX/ABS Function Calls, <> Expressions, and >< Expressions
Subexpressions that call the MIN, MAX, and ABS functions or use the <> (maximum) and >< (minimum) operators can be linearized. When the function or operator is a convex term in the containing objective or constraint, PROC OPTMODEL can linearize the value by using a simplified transformation, adding one constraint for each argument and a single variable for the result term. For nonconvex terms, the transformation requires additional binary variables and constraints.
The function or operator is a convex term if it is used with a constant linear coefficient of the correct sign in the containing objective or constraint. For the linearizable subexpressions 
and 
, with positive constant coefficient c and constant bound B, the following examples of objectives and constraints can be linearized by using the transformation for convex terms:
As an example of the convex linearization transformation, consider the subexpression 
used with a positive coefficient in a minimization objective. The subexpression can be replaced by a new variable, z, with these added constraints:
Because the variable z is used with a positive coefficient in a minimization objective, the solver drives z toward 
, subject to the added constraints. This results in an optimal value, with z equal to the largest of the MAX arguments. If the original subexpression were used with a positive coefficient in a constraint that had an upper bound, then the optimal solution value of z might not be equal to any of the arguments. But the transformed constraint is feasible if and only if the original constraint is feasible.
The following code shows some examples of the convex transformation:
proc optmodel;
var x;
var y;
minimize obj = 2*max(-x+1, x-1) + y;
expand / linearize;
fix y = 7;
minimize obj2 = y*abs(x+1) + 3*abs( x );
con c: min(x, 2*x-1) >= 0;
expand / linearize;
The output from the two EXPAND statements is shown in Figure 69.
Figure 69: Convex MIN/MAX/ABS Linearization
Var x Var y Var _ADDED_VAR_[1] Minimize obj=y + 2*_ADDED_VAR_[1] Constraint _ADDED_CON_[1]: - x - _ADDED_VAR_[1] <= -1 Constraint _ADDED_CON_[2]: x - _ADDED_VAR_[1] <= 1 |
Var x Fix y = 7 Var _ADDED_VAR_[1] Var _ADDED_VAR_[2] Var _ADDED_VAR_[3] Minimize obj2=7*_ADDED_VAR_[2] + 3*_ADDED_VAR_[3] Constraint c: _ADDED_VAR_[1] >= 0 Constraint _ADDED_CON_[1]: x - _ADDED_VAR_[1] >= 0 Constraint _ADDED_CON_[2]: 2*x - _ADDED_VAR_[1] >= 1 Constraint _ADDED_CON_[3]: x - _ADDED_VAR_[2] <= -1 Constraint _ADDED_CON_[4]: x + _ADDED_VAR_[2] >= -1 Constraint _ADDED_CON_[5]: x - _ADDED_VAR_[3] <= 0 Constraint _ADDED_CON_[6]: x + _ADDED_VAR_[3] >= 0 |
When the function or operator is a nonconvex term, linearization requires additional variables and constraints. Consider the subexpression 
. The nonconvex transformation requires a new binary variable, 
, for each argument. Linearization replaces the subexpression with a new variable, z, that has these added constraints:
The first three constraints match the convex transformation. The next three indicator constraints require z to be at most (hence equal to) the argument value when the corresponding variable is true. The final constraint ensures that one of the indicator constraints is active. The active constraint must correspond to an argument that has the maximum value because of the first three constraints.
When MIN or MAX has two arguments, the nonconvex transformation requires a single binary variable in order to select the active argument. For example, linearization replaces the function with a new variable, z, that has these constraints:
The new binary variable, 
, selects an argument that has the maximum value.
The nonconvex transformation for 
is similar, because 
:
The following code shows some examples of the nonconvex transformation:
proc optmodel;
var x{1..4} >= 0 <= 100;
con c1: max(x[1], x[2]) >= 50;
con c2: min(x[1], x[2]) <= 10;
maximize obj = abs(x[3]-x[4]);
expand / linearize;
The output from the EXPAND statement is shown in Figure 70. Note that a big-M transformation was applied to the indicator constraints.
Figure 70: Nonconvex MIN/MAX/ABS Linearization
Var x[1] >= 0 <= 100 Var x[2] >= 0 <= 100 Var x[3] >= 0 <= 100 Var x[4] >= 0 <= 100 Var _ADDED_VAR_[1] Var _ADDED_VAR_[2] BINARY Var _ADDED_VAR_[3] Var _ADDED_VAR_[4] BINARY Var _ADDED_VAR_[5] Var _ADDED_VAR_[6] BINARY Maximize obj=_ADDED_VAR_[5] Constraint c1: _ADDED_VAR_[1] >= 50 Constraint c2: _ADDED_VAR_[3] <= 10 Constraint _ADDED_CON_[1]: x[1] - _ADDED_VAR_[1] <= 0 Constraint _ADDED_CON_[2]: x[2] - _ADDED_VAR_[1] <= 0 Constraint _ADDED_CON_[3]: x[1] - _ADDED_VAR_[1] + 100*_ADDED_VAR_[2] >= 0 Constraint _ADDED_CON_[4]: x[2] - _ADDED_VAR_[1] - 100*_ADDED_VAR_[2] >= -100 Constraint _ADDED_CON_[5]: x[1] - _ADDED_VAR_[3] >= 0 Constraint _ADDED_CON_[6]: x[2] - _ADDED_VAR_[3] >= 0 Constraint _ADDED_CON_[7]: x[1] - _ADDED_VAR_[3] - 100*_ADDED_VAR_[4] <= 0 Constraint _ADDED_CON_[8]: x[2] - _ADDED_VAR_[3] + 100*_ADDED_VAR_[4] <= 100 Constraint _ADDED_CON_[9]: x[3] - x[4] - _ADDED_VAR_[5] <= 0 Constraint _ADDED_CON_[10]: x[3] - x[4] + _ADDED_VAR_[5] >= 0 Constraint _ADDED_CON_[11]: x[3] - x[4] - _ADDED_VAR_[5] + 200*_ADDED_VAR_[6] >= 0 Constraint _ADDED_CON_[12]: x[3] - x[4] + _ADDED_VAR_[5] + 200*_ADDED_VAR_[6] <= 200 |
Linear Ratio Constraints
A singly bounded constraint on the ratio of linear expressions can be transformed into a linear constraint by multiplying the bound by the denominator, provided that the denominator cannot equal 0. For example, the ratio constraint with linearizable expressions and and bound B,
can be linearized (assuming 
) as
If 
, then the bound is multiplied by 
:
To handle a range constraint with bounds L and U,
the original constraint is replaced by an equality constraint that introduces a new variable, z,
and the following added constraints (assuming ):
Note that the body value for ratio constraints is not preserved by the transformation.
The following code shows examples of the linearization of ratio constraints:
proc optmodel;
var x {1..4} >=1;
minimize obj = sum {i in 1..4} x[i];
con c1: (x[1] + x[2] + 1) / (x[3] + x[4]) = 4;
con c2: (x[1] + x[3]) / (x[2] + x[4]) <= 0.8;
con c3: 4*(x[1] - x[2]) / (-x[3] - x[4]) >= -1;
con c4: 2 <= (x[1] + x[2] + 1) / (x[3] + x[4] + 1) <= 3;
expand / linearize;
The output is shown in Figure 71.
Figure 71: Ratio Constraint Linearization
Var x[1] >= 1 Var x[2] >= 1 Var x[3] >= 1 Var x[4] >= 1 Var _ADDED_VAR_[1] Minimize obj=x[1] + x[2] + x[3] + x[4] Constraint c1: x[1] + x[2] - 4*x[3] - 4*x[4] = -1 Constraint c2: x[1] + x[3] - 0.8*x[2] - 0.8*x[4] <= 0 Constraint c3: - 4*x[1] + 4*x[2] + x[3] + x[4] >= 0 Constraint c4: x[1] + x[2] - _ADDED_VAR_[1] = -1 Constraint _ADDED_CON_[1]: _ADDED_VAR_[1] - 2*x[3] - 2*x[4] >= 2 Constraint _ADDED_CON_[2]: _ADDED_VAR_[1] - 3*x[3] - 3*x[4] <= 3 |