Network Simplex Method

The network simplex method is the simplex method specialized to the min-cost flow LP. It exploits two facts about the structure of basic feasible solutions on a network with $n$ nodes.

Fact 1. Every basic feasible solution (BFS) corresponds to a spanning tree $T$ of the network. The $n-1$ tree arcs are basic; the remaining arcs are non-basic and sit at their lower bound $x_{ij}=0$ (uncapacitated case).

Fact 2. The dual variables of the flow-conservation constraints — one per node — are called node potentials $y_1,y_2,\ldots,y_n$. They are pinned down by the requirement that every tree arc has zero reduced cost:

$$\bar{c}_{ij} \;=\; c_{ij} - y_i + y_j \;=\; 0 \quad \text{for every } (i,j) \in T.$$

Rearranging, $y_j = y_i - c_{ij}$ along each tree arc.

The $n-1$ tree-arc equations leave one degree of freedom in the $n$ potentials. To pin them down, pick any node as the root, set its potential to $0$, and propagate $y_j = y_i - c_{ij}$ outward through $T$.

For example, if the tree arcs are $(1,2)$ with $c_{12}=4$ and $(2,3)$ with $c_{23}=6$, setting $y_1=0$ gives

$$y_2 = y_1 - c_{12} = -4,\qquad y_3 = y_2 - c_{23} = -4 - 6 = -10.$$