Integrality of Single-Commodity Network Flow

When every node supply/demand and every arc capacity in a single-commodity min-cost flow problem is an integer, the linear-programming relaxation automatically has an integer optimal solution. The result follows from total unimodularity of the node-arc incidence matrix and explains why transportation and assignment problems can be solved by ordinary LP and still return integer (in particular, 0/1) answers.

Step 1 of 157%

Tutorial

The Integrality Theorem

The single-commodity min-cost flow problem chooses arc flows $x_{ij}\geq 0$ on a directed network to minimize cost subject to flow conservation and capacity bounds:

\min \sum_{(i,j)\in A} c_{ij}\, x_{ij}

subject to

\sum_{j:(i,j)\in A} x_{ij} \;-\; \sum_{j:(j,i)\in A} x_{ji} \;=\; b_i \qquad \text{for every node } i,

0 \;\leq\; x_{ij} \;\leq\; u_{ij} \qquad \text{for every arc } (i,j).

Here $b_i > 0$ at sources, $b_i < 0$ at sinks, and $b_i = 0$ at transshipment nodes.

Integrality theorem (single-commodity min-cost flow). If every supply/demand $b_i$ and every arc capacity $u_{ij}$ is an integer, and the problem is feasible, then the LP has an optimal solution in which every flow $x_{ij}^{*}$ is an integer. The (network) simplex method returns such a solution.

The costs $c_{ij}$ may be arbitrary real numbers — they have no effect on integrality of the optimal flow.

This is striking: even though the LP imposes no integrality constraints on the variables, integer data force the optimum to occur at an integer vertex of the feasible polytope.