Network Simplex

Imagine a gas pipeline network, a shipping company, or a city's water grid. At each junction, supply arrives and demand leaves. Pipes have capacity limits and per-unit transport costs. The question is always the same: how do you route the flow to meet all demands at minimum total cost?

This is the minimum-cost flow problem, one of the most fundamental in combinatorial optimization. You can write it as a linear program, feed it to a general LP solver, and get the right answer — but it's slow. LP solvers don't know you're on a graph.

The network simplex method does. Instead of pivoting arbitrary LP columns, it maintains a spanning tree of the network as its basis. Each pivot swaps exactly one edge in and one edge out of the tree — a move that takes $O(n)$ time instead of $O(n^{3})$. In practice, the method often solves million-edge networks in a fraction of a second, making it the algorithm of choice in logistics, operations research, and infrastructure planning.

The result is exact (no approximation) and proven correct — a rare combination of mathematical elegance and engineering speed.

Below is a small supply-and-demand network. Green nodes are sources (positive supply), red nodes are sinks (positive demand), and the edges carry unit costs. The thick blue edges form the current spanning tree basis.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="420" height="265"></canvas>
<div class="info" id="info">{{info_initial}}</div>
<div class="btns">
  <button id="pivot" type="button">{{btn_pivot}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="leg-item"><span class="dot supply"></span> {{legend_supply}}</span>
  <span class="leg-item"><span class="dot demand"></span> {{legend_demand}}</span>
  <span class="leg-item"><span class="dot neutral"></span> {{legend_neutral}}</span>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .55rem; line-height: 1.45; }
canvas { display: block; border-radius: 10px; background: #f4f7fa;
         border: 1px solid #dce3ea; max-width: 100%; }
.info { font-size: .88rem; font-weight: 600; margin: .45rem 0; min-height: 1.3em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .42; cursor: default; }
.legend { display: flex; gap: .9rem; flex-wrap: wrap; font-size: .8rem; color: #555; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.dot { width: 11px; height: 11px; border-radius: 50%; display: inline-block; border: 1.5px solid #888; }
.dot.supply { background: #2e7d32; border-color: #1b5e20; }
.dot.demand  { background: #c62828; border-color: #7f0000; }
.dot.neutral { background: #e8eef3; border-color: #8898a9; }

// Code not found

Press Next pivot to run one step of network simplex. Each step finds an arc not in the tree whose reduced cost is negative (meaning sending flow through it can save money), adds it to the tree, and removes the arc that leaves the resulting cycle. When every non-tree arc has a non-negative reduced cost the flow is optimal — press Reset to start over.

Network simplex is a specialization of the simplex method (George Dantzig, 1947) that exploits one key insight: the basic feasible solutions of the min-cost flow LP correspond exactly to spanning trees of the underlying graph.

• Each basis = a spanning tree. In any basic feasible solution, the flow is uniquely determined by which $n-1$ edges form the basis. Non-tree edges carry either zero flow or their maximum capacity (at their lower/upper bounds).
• Pivots are cheap. Adding a non-tree edge to the tree creates exactly one cycle. Sending as much flow as possible around that cycle (the cycle-canceling step) costs $O(n)$ to find and $O(n)$ to update. Compare this with the $O(n^{3})$ cost of a general LP pivot.
• Reduced costs guide the search. For each non-tree arc (i,j), the reduced cost $\tilde{c}_{ij} = c_{ij} - \pi_i + \pi_j$, where $\pi$ are the node potentials (dual variables maintained on the tree). An arc with a negative reduced cost can improve the objective; choosing one and pivoting is a valid simplex step.
• Termination and optimality. When no non-tree arc has a negative reduced cost, the current spanning tree solution is optimal by LP duality. Orlin (1997) proved a strongly polynomial bound of $O(nm \log(nC))$ pivots, where n = nodes, m = edges, C = max cost — though in practice the method converges in far fewer steps.

The closest relative is min-cost flow solved by the successive shortest-paths algorithm, which is also polynomial but typically slower in practice. Network simplex dominates real-world benchmarks on transportation and assignment instances. Unlike linear programming in general, no exponential examples are known for typical network simplex implementations.

Minimum-cost flow is a universal modeling language. If you can express a problem as "route flow on a graph at minimum cost," network simplex will solve it faster than almost anything else:

• Transportation and logistics: shipping goods from warehouses to stores, routing trucks or planes, assigning drivers to shifts — the classic transportation and assignment problems are special cases of min-cost flow.
• Scheduling: job scheduling on machines and crew scheduling for airlines are naturally modeled as flow problems, and network simplex is the workhorse solver.
• Image segmentation: graph-cut methods in computer vision reduce certain segmentation tasks to min-cut / max-flow (which is dual to min-cost flow), and network simplex implementations underpin fast solvers.
• Operations research: facility-location, distribution planning, and supply-chain design all lean on min-cost flow sub-problems solved by network simplex.
• Network design: telecommunications routing, power-grid load balancing, and water-distribution optimization are direct applications.

The algorithm is so practically efficient that LEMON (Library for Efficient Modeling and Optimization in Networks) and OR-Tools list it as the default solver for min-cost flow. If your problem fits the flow template, network simplex is almost certainly the right tool.

Network simplex is a textbook example of why exploiting problem structure pays off enormously. A naïve LP solver ignores the graph; network simplex bets everything on it — and wins. By maintaining a spanning tree as the LP basis and pivoting one edge at a time, it turns an $O(n^{3})$-per-pivot algorithm into an $O(n)$-per-pivot one.

The deeper lesson is one of the themes of linear programming: the geometry of a feasible polytope can be extremely special when the constraint matrix has structure. For network flow, that structure is so rich that an exact polynomial-time algorithm exists, and it's fast enough to route the flow of an entire country in milliseconds.

Next time you order something online and it arrives via an optimized shipping route, there's a good chance a spanning-tree pivot is responsible.