Capacity as a Natural Big-M in Flow Models

In fixed-charge and facility-location network flow models, arc flow variables $x_{ij}$ are linked to binary open/closed indicators $y_{ij}$ through constraints of the form $x_{ij}\le M y_{ij}$ . This lesson shows how to choose the tightest valid $M$ using the natural bounds already present in the flow model: arc capacities $u_{ij}$ , source supplies $s_i$ , and sink demands $d_j$ .

Step 1 of 157%

Tutorial

Linking Flow to an Indicator Variable

In a fixed-charge network flow model, each arc $(i,j)$ has a nonnegative flow variable $x_{ij}\ge 0$ and a binary indicator $y_{ij}\in\{0,1\}$ that equals $1$ if the arc is open and $0$ if it is closed. To force $x_{ij}=0$ whenever $y_{ij}=0,$ we add a linking constraint

x_{ij}\le M\, y_{ij}.

We need $M$ large enough that the constraint does not cut off any flow the arc could legitimately carry when $y_{ij}=1,$ but as small as possible so the LP relaxation is tight.

When the arc has an explicit capacity $u_{ij},$ the flow already satisfies $x_{ij}\le u_{ij}.$ The capacity is therefore a valid upper bound on $x_{ij},$ and it is the tightest one available from the arc alone:

M_{ij}=u_{ij}.

We call this the natural Big-M for arc $(i,j).$ For example, an arc with capacity $u_{ij}=40$ gives the linking constraint

x_{ij}\le 40\, y_{ij}.