The Big-M method is a common modeling technique used in Mixed Integer Programming (MIP) to represent logical conditions or implications using linear constraints. It introduces a large constant, typically denoted as M, to "turn on" or "turn off" constraints based on the value of binary variables. I usually call these “switch constraints”.
How It Works
Suppose you have a binary variable y ∈ {0,1} and
a constraint that should only be active when y=1. You can use the Big-M
method to model this:
Example:
You want the constraint:
x ≤ b only if y = 1
Using Big-M, you rewrite it as:
x ≤ b + M(1−y)
- When y
= 1: the constraint becomes x ≤ b
- When y
= 0: the constraint becomes x ≤ b+M which is effectively non-binding
if M is large enough
Common Use Cases
- Indicator
constraints: Linking binary decisions to continuous variables.
- Conditional
constraints: Enforcing constraints only when certain binary variables
are active.
- Modeling
piecewise linear functions.
- Disjunctive
constraints: Representing "either-or" logic.
Choosing the Right M
Choosing M is critical:
- Too
small: The model may become infeasible.
- Too
large: It can cause numerical instability and slow
down the solver.
A good practice is to estimate the smallest possible
M that still ensures correctness, based on the problem's data bounds.
Example:
Suppose we wanted to know if any of stand 234 was harvested?
If we have a theme (TH3) in the LANDSCAPE section that tracks standID, we can
do this easily. We need to know the area of stand 234, a theme-based output
that tracks harvest area by stand (oaHarv(_TH3)
and a binary variable (vb234).
The setup is straightforward:
OUTPUTS
*OUTPUT oaHarv(_TH3) Harvest area
*SOURCE .MASK() aHARV _AREA
OPTIMIZE
*VARIABLE
vb234 _BINARYARRAY ; valid for any planning period
*CONSTRAINTS
oaHARV(234) – M * vb234 <= 0
1.._LENGTH
So, what should be the value of M? Suppose that the AREAS
section lists the area of stand 234 as 8.23483834 acres? If you use 8.2 as the
value of M in the constraint, it will be too small to completely offset the harvest area if the
entire stand is harvested. If you use M = 1E6, the constraint will be arithmetically correct, but the value of M is way too large and may cause problems with the
solver. Remember, the value of M should be just big enough to offset the maximum
value of your continuous variable (oaHarv). That means we should use the same value used in the AREAS section: 8.23483834.
Tip 1: Remember that stands may be composed of
different polygons, so make sure that your total stand area includes all
polygons (area records).
Tip 2: Consider carrying at least 8 decimal places
for area records. Representing real numbers in computers is not always exact, so the
more significant figures you carry, the less likely you’ll introduce numerical
difficulties.
Tip 3: In Woodstock models, almost everything is a
function of land area. If you are setting up a lot of constraints involving
binary variables, consider using thematic indexing to represent stand area. In
this construct, all area records have a value of 1 and the true area of the
stand is introduced in the LANDSCAPE section. Doing so will simplify the writing of
switch constraints because the value of M is always integer (usually 1 but may
be larger depending on the number of area records represented). In turn, the
value of M will necessarily be of small magnitude.
Wrap-Up
If you’re interested in learning more about mixed integer
programming or how to deploy thematic indexing in your models, give me a shout!
If you have questions, don’t hesitate to ask in the comments.