Network Simplex Algorithm¶

Solve a minimum-cost flow by maintaining a spanning-tree basis, pricing bound-fixed arcs with node-potential reduced costs, augmenting around an entering arc's fundamental cycle, and exchanging the limiting arc until dual signs certify optimality.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2364
Origin domain: operations research
Subdomain: network optimization
Aliases: Network Simplex, Network Simplex Method, Primal Network Simplex Method

Core Idea¶

The network simplex algorithm is a simplex-family method specialized to a minimum-cost flow problem. On a directed network \(G=(V,A)\), the ordinary bounded formulation chooses arc flows \(x_{ij}\) to minimize

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

subject to a supply-or-demand balance at every node and bounds \(l_{ij}\le x_{ij}\le u_{ij}\). Its defining move is to represent a basic feasible solution combinatorially: a spanning tree \(T\) supplies the basic arcs, while each non-tree arc is fixed at its lower or upper bound. In the common \((T,L,U)\) description, \(L\) contains non-tree arcs at lower bounds and \(U\) contains those at upper bounds. This is more precise than saying that every nonbasic arc is zero; upper-bound nonbasic arcs are essential in capacitated formulations.

Scope of Application¶

The algorithm's habitat is bounded linear minimum-cost network flow and problems reduced faithfully to that form. The economic or physical interpretation may change, but literal use requires conserved node balances, linear arc costs, bounds, and a solver that actually maintains the tree-basis pivot mechanism.

Transshipment and distribution networks. Multiple supply, demand, and intermediate nodes fit the native formulation. Arcs encode feasible routes, costs, and capacities; the tree basis provides a sparse representation for repeated pivots.

Clarity¶

The name clarifies a three-way distinction that is otherwise easy to collapse: the model is minimum-cost flow, the general parent procedure is simplex, and the specialized algorithm is the spanning-tree implementation connecting them. The quickest reader-facing diagnostic is to ask: “What is the maintained basis, and what does one pivot do?” If the answer is “a spanning tree plus bound-fixed non-tree arcs; insert an eligible arc, augment on its unique fundamental cycle, and remove a limiting tree arc,” the network-simplex identity is present.

Manages Complexity¶

A general LP basis is a matrix object, and a general simplex pivot can require matrix-factorization machinery. The node-arc incidence matrix turns that algebra into graph operations. A basis is represented by (n-1) tree arcs (plus the standard treatment of one redundant balance equation or an artificial root); potentials are propagated along tree paths; adding a non-tree arc exposes exactly one cycle; and changing flow on that cycle automatically preserves every node balance.

Abstract Reasoning¶

The mechanism licenses several in-domain inferences and interventions:

If a lower-bound non-tree arc has an improving reduced-cost sign, increasing it defines a candidate descent direction. Add it to the tree, orient the fundamental cycle accordingly, and inspect residual capacities; do not change that arc alone, because doing so would violate node balance.
If an upper-bound non-tree arc has the opposite violating sign, reason in the reverse residual direction. A pricing routine that ignores upper-bound arcs can falsely certify optimality on capacitated instances.
If a pivot changes the basis but neither flow nor objective, diagnose degeneracy rather than an arithmetic error. The limiting tree arc was already at a bound.

Knowledge Transfer¶

The algorithm transfers literally across applications that preserve the minimum-cost-flow formulation. In transportation, a unit of flow is shipped product; in assignment, it is the selection of a worker-task edge; in a time-expanded schedule, it can represent inventory or activity moving from one time-state to another. The words “arc,” “capacity,” “node balance,” “tree basis,” “potential,” “reduced cost,” and “fundamental cycle” keep their mathematical roles. Only their application labels change.

Relationships to Other Abstractions¶

Current abstraction Network Simplex Algorithm Domain-specific

Parents (3) — more general patterns this builds on

Network Simplex Algorithm is a kind of Algorithm Prime

prime:algorithm — strict subsumption. Network simplex is a definite iterative procedure mapping a feasible minimum-cost-flow instance and starting-basis construction to an optimal flow or an infeasibility/unboundedness disposition under.
Network Simplex Algorithm presupposes Tree (Graph Theory) Domain-specific

prime:algorithm — strict subsumption. Network simplex is a definite iterative procedure mapping a feasible minimum-cost-flow instance and starting-basis construction to an optimal flow or an infeasibility/unboundedness disposition under.
Network Simplex Algorithm presupposes Network Flow Models Prime

prime:algorithm — strict subsumption. Network simplex is a definite iterative procedure mapping a feasible minimum-cost-flow instance and starting-basis construction to an optimal flow or an infeasibility/unboundedness disposition under.

Hierarchy paths (6) — routes to 5 parentless roots

Network Simplex Algorithm → Algorithm → Function (Mapping)

Show alternative paths (5)

Neighborhood in Abstraction Space¶

Network Simplex Algorithm sits in a sparse region of the domain-specific corpus (87^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08