Big-M Formulation

Suppose you have a continuous variable x that is bounded above by a constant 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:

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.

Basic Problem: Reservoir Flows

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

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

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

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

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:

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:

Express Logical Constraints Using Binary Variables

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.

z = 1 - w;

z + w >= 1;

z + w <= 1;

f >= z;
f >= w;
f <= z + w;

f <= z;
f <= w;
f >= z + w - 1;

f >= z - w;
f >= w - z;
f <= z + w;
f <= 2 - (z + w);

Express Logical Constraints Using Real Functions and Binary Indicator Variables

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

g(x) <= M*(1 - z);

g(x) >= -M*(1 - z);

g(x) <= M*(1 - z);
g(x) >= -M*(1 - z);

g(x) >= -M*z;

g(x) <= M*z;

g(x) <= M*z;

g(x) >= -M*z1;

z + z1 == 1;

Combine Logical Constraints to Create New Formulas

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

g(x) <= M*z;
h(x) >= -M*(1 - z);

g(x) <= x + M*(1-z);
g(x) >= x - M*(1-z);
g(x) <= M*z;
g(x) >= -M*z;

Example: Fixed Cost

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

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.

Example: OR Constraints

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 z1 = 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.

Example: Convert Binary Quadratic Problem to Binary Linear Problem

Consider the problem in binary variables x_i of minimizing

where x is a column vector of optimization variables of length N, and Q is a given N-by-N matrix. To solve this problem when N is not too large, convert the binary quadratic problem to a binary linear problem using an N-by-N array of binary variables xij. If xij(i,j) = x(i)*x(j), then you can represent the objective function as:

sum(Q.*xij,"all")

To ensure that the xij variables are equal to x(i)*x(j), use the following three linear inequality constraints. This code uses the problem-based approach.

N = 100; % Specify the number of variables
x = optimvar("x",N,Type="integer",LowerBound=0,UpperBound=1);
xij = optimvar("xij",N,N,Type="integer",LowerBound=0,UpperBound=1);
prob = optimproblem;

% Constraint xij = 1 when x(i) = 1 and x(j) = 1
prob.Constraints.f = xij >= repmat(x,1,N) + repmat(x',N,1) - 1;
% Constraint xij = 0 when x(i) = 0
prob.Constraints.g = xij <= repmat(x,1,N);
% Constraint xij = 0 when x(j) = 0
prob.Constraints.h = xij <= repmat(x',N,1);

prob.Objective = sum(Q.*xij,"all");

Now that the problem is linear in the optimization variables and constraints, solve calls intlinprog to compute the solution.

[sol,fval] = solve(prob);

Solving problem using intlinprog.
...

The intlinprog solution is reasonably quick for N ≤ 100, but slows for larger values of N, with a limit of roughly 200 variables for reasonable performance.

Further Reading

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].