Network simplex algorithm
The network simplex algorithm is a specialization of the simplex algorithm for solving the minimum-cost flow problem. It exploits the incidence structure of a directed network, representing a linear-programming basis by a spanning tree rather than by a general matrix factorization. The resulting pivots correspond to sending flow around cycles and replacing one tree arc with another.
The algorithm applies to capacitated transshipment models in which flow is conserved at each vertex subject to a prescribed supply or demand. Transportation and assignment problems arise as structured instances of this formulation, while minimum-cost circulation is obtained when every vertex has zero net supply.
Mathematical formulation
Let (G=(V,A)) be a directed graph. Each arc ((i,j)\in A) has cost (c_{ij}), lower bound (l_{ij}), and upper bound (u_{ij}). Every vertex (i\in V) has a balance (b_i), with positive values denoting supply under the convention used here. The optimization problem is
[ \min \sum_{(i,j)\in A} c_{ij}x_{ij} ]
subject to
[ \sum_{j:(i,j)\in A}x_{ij}
\sum_{j:(j,i)\in A}x_{ji} =b_i \qquad \text{for every } i\in V, ]
and
[ l_{ij}\leq x_{ij}\leq u_{ij} \qquad \text{for every }(i,j)\in A. ]
Feasibility requires the total balance to vanish within each disconnected component that carries no flow to the remainder of the network. In the usual connected formulation,
[ \sum_{i\in V}b_i=0. ]
The coefficient matrix of the conservation equations is a directed incidence matrix. After one redundant conservation equation has been removed, this matrix has rank (|V|-1). A nonsingular collection of (|V|-1) arc columns therefore corresponds to a spanning tree of the underlying undirected graph. This correspondence is the structural basis of the network simplex method.
Tree solutions and reduced costs
A network-simplex basis consists of a spanning tree together with a classification of the remaining arcs. Each nonbasic arc is fixed at either its lower bound or its upper bound. The flows on the tree arcs are then determined by the vertex-balance equations, although a tree arc may itself lie at a bound in a degenerate basis.
Associated with the tree is a vector of node potentials (\pi_i). Under a common sign convention, the reduced cost of arc ((i,j)) is
[ \bar c_{ij}=c_{ij}-\pi_i+\pi_j. ]
The potentials are selected so that every tree arc has zero reduced cost. Since adding the same constant to every potential leaves all reduced costs unchanged, one vertex potential is conventionally normalized to zero.
For a minimization problem, a nonbasic arc at its lower bound satisfies the optimality condition when its reduced cost is nonnegative. A nonbasic arc at its upper bound satisfies the corresponding condition when its reduced cost is nonpositive. A feasible tree solution meeting both conditions is optimal by linear programming duality.
The potentials constitute dual information associated with the conservation constraints. Reduced costs measure the change in the objective per unit of admissible movement from a bound, provided that the induced adjustment along the tree remains possible. This interpretation connects the combinatorial representation directly to the revised simplex method.
Pivot structure
An arc whose reduced cost violates its bound-dependent optimality condition is eligible to enter the tree. Adding that arc to a spanning tree creates a unique undirected cycle, called the fundamental cycle of the entering arc. Flow changes along the directed orientations of this cycle while all vertex balances remain unchanged.
The allowable magnitude of the change is limited by the first arc on the cycle to reach one of its bounds. That limiting arc leaves the tree, and the entering arc takes its place. The exchange preserves the spanning-tree structure and produces another feasible basis. When the entering arc itself reaches its opposite bound before any tree arc becomes limiting, the tree remains unchanged and the arc merely changes its nonbasic bound status.
The objective change for a nondegenerate pivot equals the entering arc’s reduced cost multiplied by the signed flow adjustment. An eligible pivot therefore decreases the objective under the stated minimization convention. A degenerate pivot has zero flow adjustment because a limiting tree arc is already at the relevant bound, so the basis can change without changing either the flow vector or the objective value.
A general simplex implementation would update an inverse or factorization of the basis matrix. The network simplex algorithm instead updates tree relationships, node potentials, and cycle information. Parent pointers and subtree data provide a compact representation of the basis, while threaded tree orders permit groups of affected vertices to be traversed without scanning the entire graph.
Historical development
George Dantzig formulated the network simplex method during the early development of linear programming in the 1950s. His formulation recognized that bases of the network incidence matrix correspond to trees and that simplex pivots can consequently be interpreted as cycle-flow adjustments. This interpretation separated network optimization from the matrix operations required by a general linear-programming solver.
During the same decade, William Orchard-Hays incorporated specialized network structures into computational linear-programming systems. His work connected the mathematical tree representation with the storage constraints and basis-management techniques of early digital computers.
In 1956, You Watanabe described a predecessor-and-depth representation for maintaining rooted network bases during arc exchanges. The representation stored the parent arc of each nonroot vertex and restricted potential revisions to the component detached by the leaving arc. It became one of several contemporary approaches to avoiding reconstruction of the full incidence basis after every pivot.
Later implementations refined arc pricing, tree traversal, and degeneracy control. William H. Cunningham developed the theory of strongly feasible spanning trees, which supplies an orientation-based basis rule that prevents cycling in primal network-simplex variants. Subsequent computational work integrated these basis rules with candidate lists and localized updates, producing the family of implementations generally called the primal network simplex algorithm.
Initialization and artificial structure
The method requires an initial feasible tree basis. When an appropriate feasible flow is already available, a spanning-tree basis can be derived by designating suitable arcs as basic and placing the remaining arcs at bounds. More generally, an augmented network supplies an artificial initial basis.
A common augmented construction introduces an artificial root connected to every original vertex. Artificial arcs carry whatever flow is necessary to satisfy the original balance equations, and their costs are chosen to distinguish solutions that retain artificial flow from solutions feasible in the original network. The initial basis is then the star centered on the artificial root.
This construction is the network analogue of Phase I of the simplex method. If the optimized artificial objective remains positive, the original model is infeasible. If all necessary artificial flow disappears, the remaining basis represents a feasible solution of the original network, although zero-flow artificial arcs may temporarily remain basic under degeneracy.
Degeneracy and cycling
Degeneracy is frequent in network models because many tree arcs can lie exactly at their lower or upper bounds. It is especially prominent when capacities and balances are integral, since the total unimodularity of the incidence matrix makes integral basic solutions natural whenever the input data are integral.
A sequence of degenerate pivots can revisit a previous basis unless the pivot rule imposes an anti-cycling structure. Lexicographic perturbations conceptually distinguish otherwise equal bounds and objective changes. Strongly feasible tree rules achieve an analogous effect through rooted-tree orientations and a consistent choice of the leaving arc.
Degeneracy also separates progress in basis space from progress in flow space. Many distinct tree bases can represent the same feasible flow, and a change of basis may expose an improving arc that was not useful under the previous tree. Consequently, an implementation’s treatment of ties affects its sequence of bases even when the underlying optimization problem has a unique optimal flow.
Pricing and data organization
Pricing is the examination of nonbasic arcs for reduced-cost violations. Complete pricing evaluates every eligible arc before each pivot and selects one according to a specified rule. Partial pricing maintains a smaller collection of candidates and periodically refreshes it from the full arc set. The two policies generate the same type of simplex pivot but differ in the amount of work devoted to identifying an entering arc.
Once an entering arc is selected, the principal tree operations are identification of the fundamental cycle and determination of the limiting residual capacity. After the leaving arc is removed, one component of the former tree becomes attached through the entering arc. Potentials in that component receive a uniform offset, restoring zero reduced cost on the new tree arc without altering reduced costs of arcs whose endpoints both remain in the same component.
Efficient implementations represent the rooted tree through parent relationships, depths, and traversal links. Subtree sizes can support decisions about which component to relabel after an exchange. These structures do not alter the mathematical pivot; they reduce the amount of tree information that must be recomputed.
Correctness and computational behavior
Every nondegenerate pivot preserves feasibility and improves the objective. Under an anti-cycling rule, the finite number of possible bases implies finite termination. At termination, the reduced-cost conditions provide dual feasibility, while the maintained flow provides primal feasibility. Complementary slackness then establishes optimality.
The classical network simplex method does not possess a generally polynomial bound on the number of pivots under ordinary pricing rules. Carefully constructed networks can force exponentially long pivot sequences, reflecting the corresponding worst-case behavior of the general simplex method. This limitation concerns theoretical worst cases rather than the definition of the method or the validity of its optimality conditions.
In computational optimization, network simplex implementations are often compared with cycle-canceling algorithms, successive shortest-path algorithms, and cost-scaling methods. Their relative running behavior depends on network structure, degeneracy, capacity distribution, and the cost of maintaining shortest-path or tree information. The network simplex method remains distinguished by its direct use of spanning-tree bases and by its close correspondence with linear-programming geometry.