What happens when a flow network has no interior?
Network flow and min-cut (topic 06), its special case the transportation problem (18), which keeps only two flat layers of nodes, matching and assignment (07), and shortest paths with dynamic programming (08): the structure real shipping, scheduling and routing problems have.
Take topic 06's network-flow picture (a source, a sink, and whatever tangle of intermediate nodes and pipes sits between them) and strip out everything except two flat layers: a row of supply nodes, each holding a fixed amount of stock, and a row of demand nodes, each needing a fixed amount delivered, with a direct edge from every supply node to every demand node and nothing in between. That is the transportation problem: minimise total shipping cost, where each edge (i, j) costs cij per unit and every supply and every demand must be met exactly.
It is the single most structured special case of network flow on this whole page: bipartite, no intermediate nodes, every unit of supply going somewhere and every unit of demand coming from somewhere, and that extra structure is not incidental, as the mathematics below makes precise.
It is also, unusually for this course, a problem with two independent discoveries rather than one. Frank Hitchcock published it first, as a pure distribution problem with no economic framing at all (1941). Tjalling Koopmans arrived at the same mathematical structure eight years later from the opposite direction: he spent 1942–44 as a statistician for the British Merchant Shipping Mission and the Combined Shipping Adjustment Board in Washington, a joint American–British wartime agency, working out how to route merchant shipping efficiently, and wrote the general problem up as a question about optimally allocating scarce cargo capacity to routes (1949). Koopmans shared the 1975 Nobel Memorial Prize in Economic Sciences with Leonid Kantorovich, awarded jointly "for their contributions to the theory of optimum allocation of resources": work whose starting point was this same shipping-and-supply structure, reached from economics rather than from mathematics.
The trap here rhymes with topic 04's rounding trap and topic 07's greedy trap: a plan that is feasible (every supply used, every demand met) is not automatically a good plan. The northwest-corner plan in the figure satisfies every constraint and still costs 25% more than necessary.
As a linear program, with xij the amount shipped from source i to destination j, supplies si and demands dj (balanced: Σsi = Σdj):
minimise Σᵢ Σⱼ cᵢⱼ xᵢⱼ
s.t. Σⱼ xᵢⱼ = sᵢ every source ships its whole supply
Σᵢ xᵢⱼ = dⱼ every destination receives its whole demand
xᵢⱼ ≥ 0
Compare this to the assignment problem's integer program in topic 07: identical shape, with every si and every dj pinned to exactly 1 and xij restricted to {0, 1}. The assignment problem is not merely similar to the transportation problem. It is the transportation problem's own special case, one supply unit and one demand unit per node.
Topic 04 stated the totally-unimodular rule without deriving it; here is the derivation it left out. Call a matrix totally unimodular (TU) if every square submatrix has determinant 0, +1 or −1 (the whole matrix, taken as a submatrix of itself, is included). A basic feasible solution of a linear program (a vertex of the feasible polytope) comes from choosing a square, invertible submatrix B of the constraint matrix (the "basis") and solving x_B = B⁻¹b for the basic variables, with every non-basic variable set to 0. By Cramer's rule, each entry of B⁻¹ is a cofactor of B (itself the determinant of a square submatrix of B, hence of the original matrix) divided by det(B). If the constraint matrix is TU, det(B) = ±1 for every basis B, so B⁻¹ is an integer matrix outright, and x_B = B⁻¹b is integral whenever b is integral. Every vertex of the feasible region is therefore an integer point already: no rounding, no branch and bound, no gap between the LP relaxation and the true integer optimum.
The transportation problem's constraint matrix is the node–arc incidence matrix of a bipartite graph: exactly the network structure topic 06 already proved is TU, here with no intermediate nodes at all. So its integrality is not a new theorem; it is topic 06's theorem, applied to the flattest network there is. (Checked directly for the instance in the figure: all 461 square submatrices of its 5×6 constraint matrix have determinant in {−1, 0, +1}, computed in the verification script cited below.)
Restructuring a supply chain, for real Procter & Gamble's mid-1990s redesign of its North American product-sourcing and distribution network combined a facility-location decision (which plants stay open) with exactly this problem sitting underneath it: once the surviving plants and distribution centres are fixed, shipping product from each open plant to each distribution centre at minimum cost, against fixed plant capacities and centre demands, is a transportation problem in the textbook sense. Camm, Chorman, Dill, Evans, Sweeney & Wegryn, "Blending OR/MS, Judgment, and GIS: Restructuring P&G's Supply Chain," Interfaces 27(1) (1997), 128–142, report the outcome: almost 20% fewer North American plants and over $200 million a year in pretax savings.
Check yourself
A northwest-corner shipping plan is feasible and costs 300; the optimum costs 240. What does that show?
Both plans are feasible; only one is optimal. 300/240 = 1.25. It is the same trap as the rounding trap and the greedy trap.