308. Network Simplex

A specialization of the simplex method for network flow problems (transportation, transshipment, min-cost flow). Exploits the tree structure of basic feasible solutions for speed-up over generic simplex.

308.1. Key insight: basis = spanning tree

For a network with nodes, a basic feasible solution corresponds to a spanning tree of the network (plus a choice of source / sink directions). There are basic variables (one per tree arc), exactly matching the LP’s basis dimension.

Non-basic arcs have flow zero or equal to their capacity.

308.2. Why this matters

Operations that are in general simplex become on a tree:

• Pivot (replace one basic arc with one non-basic arc) → just update the tree path
• Dual prices → propagate from root to leaves of the tree
• Reduced costs → compute from dual prices via

308.3. Algorithm

Initialize a feasible spanning tree T (e.g., via big-M or two-phase)
While there exists a non-basic arc (i, j) with reduced cost < 0:
    Add (i, j) to T forming a cycle
    Push flow around the cycle until some basic arc hits zero or capacity
    Remove that arc from T (it leaves the basis)
Return optimal flow

308.4. Complexity

• In theory: not polynomial (can cycle in degenerate cases without Bland-style rules)
• In practice: extremely fast — to per pivot, sub-linear pivots needed on real instances
• State-of-the-art MCNF solver in CPLEX, Gurobi, MINOS, etc.

308.5. When to use

• Min-cost flow problems
• Transportation / transshipment / assignment (which are MCNF special cases)
• Always faster than generic LP simplex for network problems

308.6. See also

• Simplex Method — the general parent
• Min-Cost Flow — problem solved
• Transportation Problem — special case
• Min-Cost Flow Algorithms — alternative methods