Main Content

Integer constraints allow you to create models with these important features:

Implications, such as "If Condition A holds then Condition B holds."

Transaction costs or setup costs, such as "The cost of an item is zero if I buy zero of the item, but the cost is $A transaction cost plus $B per item if I buy more than zero." See Example: Fixed Cost.

Logical constraints, such as "Airlock door A and door B cannot both be open at the same time."

Many modeling problems are equivalent to logical models that use indicator variables.
This topic describes how to use indicator variables and logical models. These models are
based on the *Big-M* formulation, where a variable
*x* and a constant *M* are assumed to satisfy the
inequalities –*M* ≤ *x* ≤
*M*.

Recall that constraints in optimization have an implied "and." Constraints c1, c2, and c3 are satisfied when all three constraints are satisfied: c1 and c2 and c3.

Suppose you have a continuous variable *x* that is bounded above
by a constant *M*:

*x* ≤ *M*.

You want to associate a binary indicator variable *z* to
*x* so that *z* = 1 whenever *x* > 0. To do so, use the Big-M formulation by including the
constraint:

*x* ≤ *M*
*z*.

This constraint ensures that whenever *x* > 0, then *z* = 1 necessarily. The Big-M formulation has more applications, as
discussed in Express Logical Constraints Using Real Functions and Binary Indicator Variables.

Suppose that you want to model a reservoir over integer times. At each positive
integer time *t* in a fixed range, the reservoir can accept water
of quantity xin(*t*), or can discharge an amount of water
xout(*t*), in continuous amounts up to a maximum
*M* either in or out. Your model should enforce that if xin(*t*) > 0 then xout(*t*) = 0, and if xout(*t*) > 0 then xin(*t*) = 0. How do you model this constraint? One way is to constrain

xin(*t*) * xout(*t*) = 0.

However, this constraint causes the problem to become nonlinear, and solvers generally have difficulty with this type of constraint.

A better way to implement the constraint is to use an indicator binary variable
zin(*t*) that is 1 whenever xin(*t*) > 0, and a similar binary variable zout(*t*) that is
1 whenever xout(*t*) > 0. Assuming that you have such variables, add the constraint

zin(*t*) + zout(*t*) ≤ 1,

which ensures that xin(*t*) and xout(*t*) are
not both positive.

To ensure that zin(*t*) = 1 whenever xin(*t*) > 0, use the Big-M formulation. Assume that xin(*t*)
is bounded above by *M*, a positive number, for all
*t*. Include the constraint

xin(*t*) ≤
*M**zin(*t*).

To ensure that zin(*t*) = 0 whenever xin(*t*) = 0, include zin(*t*) in the objective function. In
this way, minimizing the objective function causes zin(*t*) to be
zero whenever possible.

Similarly, to connect zout(*t*) and xout(*t*),
incorporate the constraint

xout(*t*) <=
*M**zout(*t*).

In summary, to enforce the constraint that xin(*t*) and
xout(*t*) cannot both be positive, you create two binary
variables zin(*t*) and zout(*t*) for each time
*t*, and include these three constraints:

xin(*t*) <=
*M**zin(*t*) % Ensures that
zin(*t*) = 1 whenever xin(*t*) >
0.

xout(*t*) <=
*M**zout(*t*) % Ensures that
zout(*t*) = 1 whenever xout(*t*) >
0.

zin(*t*) + zout(*t*) <= 1 % Ensures
that zin(*t*) and zout(*t*) are not both
positive.

The MATLAB^{®} commands in the problem-based approach are as follows:

T = 50; % Number of times M = 40; % Maximum size of x variables xin = optimvar('xin',T,'LowerBound',0,'UpperBound',M); xout = optimvar('xout',T,'LowerBound',0,'UpperBound',M); zin = optimvar('zin',T,'Type','integer','LowerBound',0,'UpperBound',1); zout = optimvar('zout',T,'Type','integer','LowerBound',0,'UpperBound',1); prob = optimproblem; xinzin = xin <= M*zin; xoutzout = xout <= M*zout; zinzout = zin + zout <= 1; prob.Constraints.xinzin = xinzin; prob.Constraints.xoutzout = xoutzout; prob.Constraints.zinzout = zinzout; prob.Objective = sum(zin + zout);

Note the following:

All the constraints are vectors of constraints of length

`T`

, as are the optimization variables and indicator variables.All the constraints are defined with single statements, not in a loop, which gives the best performance.

This section contains logical statements and the corresponding MATLAB commands with binary variables. The statements assume that the
variables `z`

, `w`

, and `f`

are
binary optimization variables, meaning each has type `"integer"`

,
lower bound `0`

, and upper bound `1`

.

Description | Logical Statement | MATLAB Commands |
---|---|---|

`z` and `w` have opposite
values | `z = not w` |
z = 1 - w; |

At least one of `z` or `w` is
true | `z or w` |
z + w >= 1; |

At most one of `z` or `w` is
true | `(not z) or (not w)` |
z + w <= 1; |

`f` is true exactly when `z` is
true or `w` is true | `f` = `z or w` |
f >= z; f >= w; f <= z + w; |

`f` is true exactly when both
`z` and `w` are true | `f` = `z and w` |
f <= z; f <= w; f >= z + w - 1; |

`f` is true exactly when one of
`z` or `w` is true | `f` = `z xor w` |
f >= z - w; f >= w - z; f <= z + w; f <= 2 - (z + w); |

This section connects a real function *g*(*x*)
and a binary variable *z*. Typically, you introduce
*z* into the problem as an indicator variable to model some
aspect of the problem, such as an indicator of when *g*(*x*) > 0. All of these constraints are based on the Big-M
formulation.

Assume that the constant *M* and the function
*g*(*x*) satisfy the bounds

*–M* ≤ *g*(*x*) ≤
*M*.

Condition | Constraint Code |
---|---|

If z = 1 then g(x) ≤
0 |
g(x) <= M*(1 - z); |

If z = 1 then g(x) ≥
0 |
g(x) >= -M*(1 - z); |

If z = 1 then g(x) =
0 |
g(x) <= M*(1 - z); g(x) >= -M*(1 - z); |

If g(x) ≤
0 then z = 1 |
g(x) >= -M*z; |

If g(x) ≥
0 then z = 1 |
g(x) <= M*z; |

If If | Create a new binary variable
g(x) <= M*z;
g(x) >= -M*z1;
z + z1 == 1; This formulation is indeterminate when |

Use the previous logical constraints together with binary indicator variables to create code that implements new formulas.

Condition | Constraint Code |
---|---|

For scalar functions
If | Introduce a binary indicator variable
g(x) <= M*z; h(x) >= -M*(1 - z); |

g(x) =
z*x where z is a binary
variable | Represent this condition as two constraints: If If
g(x) <= x + M*(1-z); g(x) >= x - M*(1-z); g(x) <= M*z; g(x) >= -M*z; |

Suppose that the cost of producing a quantity *x* of an item
is

$$\text{cost}=\{\begin{array}{ll}a+bx\hfill & \text{if}x0\hfill \\ 0\hfill & \text{if}x=0.\hfill \end{array}$$

You can model this nonlinear cost using a linear variable *x* and
a binary indicator variable *z*. Create constraints so that *z* = 1 whenever *x* > 0, and include *z* in the objective function so
that *z* = 0 whenever *x* = 0. Assume that the problem includes a bound *M* so
that *x* ≤ *M*.

```
x <= M*z; % Constraint, makes z = 1 when x > 0
cost = a*z + b*x;
```

If you minimize the cost, when `x`

= 0 then `z`

= 0 also.

Sometimes you want to model a constraint that is enforced when condition A holds
or condition B holds or condition C holds. To do so, create binary indicator
variables `zA`

, `zB`

, and `zC`

that indicate when the corresponding conditions A, B, and C hold, and include the
additional constraint

zA + zB + zC >= 1;

As another example, model the absolute value constraint |*x*| = 5, which means *x* = 5 or *x* = –5. Create two indicator variables `z1`

and
`z2`

that indicate when *x* = 5 and *x* = –5, respectively. Then include the constraint

z1 + z2 >= 1;

One way to set *z*1 = 1 when *x* = 5 is to introduce three new indicator variables
`z11`

, `z12`

, and `z13`

for
these conditions:

`z11`

= 1 when `x`

< 5 and
`z1`

= 0,

`z12`

= 1 when `x`

= 5 and `z1`

= 1,

`z13`

= 1 when `x`

> 5 and `z1`

= 0.

Then introduce the constraint

z11 + z12 + z13 = 1;

To specify `z11`

, use these three constraints.

-(1 - z11) <= z1; z1 <= (1 - z11); x - 5 <= M(1 - z11);

To specify `z12`

, use these four constraints.

-(1 - z12) <= z1 - 1; z1 - 1 <= (1 - z12); -M(1 - z12) <= x - 5; x - 5 <= M(1 - z12);

To specify `z13`

, use these three constraints.

-(1 - z13) <= z1; z1 <= (1 - z13); x - 5 >= -M(1 - z13);

To finish the model, specify similar constraints for `z21`

,
`z22`

, and `z23`

that correspond to
`z2`

and the condition *x* = –5.

The classic book on modeling for optimization is Williams [1]. For a discussion of why the Big-M formulation of binary indicator variables is mathematically complete and not extensible, see Hooker [2]. For further examples of using binary indicator variables in mathematical modeling, see Brown and Dell [3] and Stevens and Palocsay [4].

[1] Williams, H. Paul.
*Model Building in Mathematical Programming, 5th Edition.*
Wiley, 2013.

[2] Hooker, John. *A
Principled Approach to MILP Modeling.* Carnegie Mellon University,
2008. Available at https://coral.ise.lehigh.edu/mip-2008/talks/hooker.pdf.

[3] Brown, Gerald G. and
Robert F. Dell. *Formulating Integer Linear Programs: A Rogues'
Gallery.* INFORMS Transactions on Education 7 (2), 2007, pp. 153–159.
Available at https://doi.org/10.1287/ited.7.2.153.

[4] Stevens, Scott P. and
Susan W. Palocsay. *Teaching Use of Binary Variables in Integer Linear
Programs: Formulating Logical Conditions.* INFORMS Transactions on
Education 18 (1), 2017, pp. 28–36. Available at https://doi.org/10.1287/ited.2017.0177.

`intlinprog`

| `ga`

(Global Optimization Toolbox) | `gamultiobj`

(Global Optimization Toolbox) | `surrogateopt`

(Global Optimization Toolbox)