Max Flow: LP Formulation

The maximum flow problem on a directed network with arc capacities, formulated as a linear program. We write the flow-conservation and capacity constraints explicitly, then express them compactly using the node-arc incidence matrix together with the return-arc trick.

Step 1 of 157%

Tutorial

The Max Flow Problem and Its LP

A flow network is a directed graph $G = (V, A)$ together with a nonnegative capacity $u_{ij}$ on each arc $(i,j) \in A$ , a designated source $s \in V$ , and a sink $t \in V$ .

A flow assigns a real number $x_{ij}$ to each arc and must satisfy two requirements:

Capacity constraints: $0 \le x_{ij} \le u_{ij}$ for every arc $(i,j)$ .
Flow conservation: at every node $i \neq s, t$ ,

\sum_{j:(i,j)\in A} x_{ij} \;-\; \sum_{j:(j,i)\in A} x_{ji} \;=\; 0,

that is, total flow out of $i$ equals total flow into $i$ .

The value of the flow is the net flow leaving the source:

v \;=\; \sum_{j:(s,j)\in A} x_{sj} \;-\; \sum_{j:(j,s)\in A} x_{js}.

The max flow problem asks for a flow of largest possible value. With decision variables $x_{ij}$ it is the linear program

\begin{aligned} \max\;\;& v = \sum_{j:(s,j)\in A} x_{sj} - \sum_{j:(j,s)\in A} x_{js} \\ \text{s.t.}\;\;& \sum_{j:(i,j)\in A} x_{ij} - \sum_{j:(j,i)\in A} x_{ji} = 0 \quad \forall\, i \neq s, t, \\ & 0 \le x_{ij} \le u_{ij} \quad \forall\, (i,j) \in A. \end{aligned}

Every constraint is linear in the arc flows, so this is a standard LP.