311. 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 $50-100\times$ speed-up over generic simplex.

311.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 $𝑛-1$ basic variables (one per tree arc), exactly matching the LP’s basis dimension.

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

311.2. Why this matters

Operations that are $𝑂\left({𝑛}^3\right)$ in general simplex become $𝑂\left(𝑛\right)$ 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 ${\left|𝑐\right|}_{𝑖𝑗}={𝑐}_{𝑖𝑗}-{𝜋}_{𝑖}+{𝜋}_{𝑗}$

311.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

311.4. Complexity

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

311.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

311.6. See also

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