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.^[1]^[2]

Choose one node as a computational root and derive node potentials \(\pi\) so that every tree arc has zero reduced cost under a fixed sign convention, for example \(\bar c_{ij}=c_{ij}+\pi_i-\pi_j\). The root only fixes the otherwise arbitrary additive constant in the potentials; it does not say that physical flow originates there or that the input network is itself a tree. For minimization, a lower-bound non-tree arc with \(\bar c_{ij}<0\) can improve the objective by increasing its flow. An upper-bound non-tree arc with \(\bar c_{ij}>0\) can improve it by decreasing its flow, equivalently by entering in the reverse residual direction. If no bound-fixed arc has an improving reduced-cost sign, the current feasible flow satisfies the primal-dual optimality conditions.^[3]^[1]

When an eligible arc enters, adding it to \(T\) creates exactly one undirected fundamental cycle. Orient that cycle in the improving residual direction and change all cycle flows by a common amount \(\theta\). Flow conservation is preserved because every node on the cycle gains and loses the same increment. Feasibility determines the disposition. If a basic tree arc is the finite residual bottleneck, that arc leaves, the entering arc joins the tree, and the ordinary tree exchange produces another basis. If the entering arc itself reaches its opposite bound before any tree arc limits, the step is a bound flip: the arc remains nonbasic at its opposite bound and the tree basis is unchanged. If no finite residual bottleneck exists on the improving cycle, the objective is unbounded in that direction. The algorithm then updates potentials and prices arcs again. The family identity is this closed loop—tree basis → potentials and reduced costs → eligible entering arc → fundamental-cycle augmentation → tree exchange, bound flip, or unbounded disposition → optimality test—not any particular pricing scan or tree data structure.

Degeneracy matters. A basic tree arc can already be at a bound, so the limiting step can be \(\theta=0\): the basis changes while the flow and objective do not. Careless pivot selection can revisit bases or cycle; strongly feasible trees, tie-breaking rules, and other anti-cycling disciplines manage that risk. The execution contract begins by constructing or verifying a primal-feasible tree basis, using Phase I or an artificial-tree method when necessary; if that phase cannot produce feasibility, the algorithm reports infeasibility. Ordinary pivots and bound flips then preserve feasibility until the algorithm returns an optimality certificate or an unboundedness disposition. Initialization supports that contract without becoming a separate algorithmic identity. Nor does the familiar algorithm under every ordinary pivot rule automatically have a polynomial worst-case bound. Orlin proved polynomial time for a qualifying cost-scaling primal network-simplex variant built around a premultiplier rule, with \(O(\min\{nm\log(nC),nm^2\log n\})\) pivots and \(O(\min\{n^2m\log(nC),n^2m^2\log n\})\) time under the paper's parameterization; that result must not be generalized to arbitrary entering-arc rules.^[4] Efficient conventional implementations remain important because the method often performs very well empirically on minimum-cost-flow instances even though natural pivot rules can have exponential worst cases.^[5]

Structural Signature¶

Sig role-phrases:

The capacitated, costed flow network — directed arcs carry lower and upper bounds, unit costs, and node-balance obligations.
The feasible \((T,L,U)\) tree basis — a spanning tree holds the basic arcs while non-tree arcs sit at lower or upper bounds.
The rooted node-potential system — one arbitrary root anchors potentials that make tree-arc reduced costs zero.
The bound-aware pricing test — reduced-cost signs identify a lower-bound arc to increase or an upper-bound arc to decrease.
The entering arc and fundamental cycle — adding one eligible non-tree arc to the tree creates the unique cycle along which feasibility-preserving adjustment is possible.
The residual bottleneck and pivot disposition — the smallest forward residual capacity or backward removable flow fixes \(\theta\); a limiting tree arc triggers an exchange, a limiting entering arc triggers a bound flip, and absence of any finite bottleneck establishes unboundedness.
The basis-update branch — an ordinary entering/leaving exchange preserves a new spanning tree, a bound flip preserves the same tree, and a zero-step limiting tree arc preserves flow while changing the basis.
The reduced-cost optimality certificate — the absence of an eligible non-tree arc closes the process with compatible primal feasibility and dual signs.

Three invariants distinguish the method. First, node balances and arc bounds survive every augmentation. Second, the basis representation remains a spanning tree after each exchange, with non-tree arcs classified by their active bounds. Third, the objective-improving direction is read jointly from an arc's bound status and reduced cost; the sign alone is not meaningful without the chosen convention and whether flow may move upward or downward.

The signature excludes algorithms that solve the same problem without maintaining this representation. Cycle-canceling also looks for improving residual cycles, and successive-shortest-path and cost-scaling methods also use reduced-cost ideas, but they do not thereby preserve a one-entering/one-leaving spanning-tree basis. Conversely, a generic simplex pivot supplies entering and leaving variables but not node-potential pricing or the fundamental-cycle update induced by a network incidence matrix.

What It Is Not¶

Not the general simplex method. General simplex traverses adjacent bases of a linear program. Network simplex specializes that pattern to the node-arc incidence structure of minimum-cost flow, where bases have spanning-tree representations and a pivot becomes a fundamental-cycle flow update. A tableau pivot that has no flow network or tree basis is not network simplex.
Not the minimum-cost flow problem itself. Minimum-cost flow is the problem/model: balances, bounds, costs, and an objective. Network simplex is one solver. Cycle-canceling, successive-shortest-path, cost-scaling push-relabel, and other methods can solve the same model without using its tree-pivot closure.^[1]^[5]
Not a claim that the physical network is a tree. The maintained tree is a basis selected from an arbitrary connected network. Non-tree arcs remain part of the instance and are precisely the arcs whose possible entry creates fundamental cycles.
Not transportation simplex as a lossless synonym. A transportation tableau has a bipartite supply-to-demand structure and its own specialized presentation. Transportation simplex is a close specialization/co-instance of tree-basis pivoting, but general network simplex also covers transshipment nodes, arbitrary directed network topology, lower and upper arc bounds, and other minimum-cost-flow reductions.
Not cycle-canceling merely because both augment around cycles. A cycle-canceling algorithm selects a negative-cost residual cycle and augments until an arc saturates. Network simplex selects an entering non-tree arc by bound-aware reduced cost, obtains its unique fundamental cycle relative to the current tree, and exchanges one basis arc. The tree-basis invariant is decisive.
Not uniformly polynomial under every pivot rule. Orlin's polynomial result belongs to a particular cost-scaling premultiplier variant. It does not transform arbitrary Dantzig-style, first-eligible, block-search, or implementation-specific pivot rules into polynomial algorithms.^[4]
Not guaranteed to change the flow at every pivot. Degeneracy can make \(\theta=0\). The basis changes but the primal solution and objective remain fixed, which is why pivot discipline is not cosmetic.

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.
Transportation problems. Bipartite source-to-destination shipping tables are structured minimum-cost flows. Transportation-simplex presentations are a narrower specialization; a general network-simplex implementation can solve the same reduction.
Assignment and bipartite matching. Unit supplies and demands with unit-capacity worker-to-task arcs turn a costed assignment into minimum-cost flow. Integrality of the network formulation makes a basic optimal flow an integral matching when the data are integral.^[3]^[1]
Shortest paths and selected routing formulations. Sending one unit from a source to a sink with arc lengths as costs is a minimum-cost-flow model only when the assumptions or formulation exclude exploitable negative-cost circulations; otherwise a minimum-cost flow may add a cost-reducing circulation that is not part of any source-to-sink path. Under that qualification, specialized shortest-path algorithms are normally preferable, but the reduction remains literal and helps show the model family's breadth.^[4]
Production, logistics, and scheduling reductions. Many allocation and time-expanded network models encode inventories or activities as nodes and feasible movements as arcs. Network simplex applies only after the side constraints have been represented without destroying the single-commodity network matrix; arbitrary additional linear constraints generally break the pure tree-basis structure.^[1]
Reoptimization and warm starts. When costs, capacities, or supplies change modestly, an existing feasible or near-feasible tree basis can be updated rather than discarded. The tree/potential representation makes basis sensitivity and reoptimization natural, though the payoff depends on the changed instance and implementation.^[1]
Large sparse minimum-cost-flow software. Practical codes combine tree data structures, candidate-list or block-search pricing, initialization strategies, and pivot heuristics. Experimental work shows that network simplex and cost-scaling can both be highly competitive, with relative performance depending on instance size and structure rather than a universal winner.^[5]

The boundary is equally important. Multicommodity coupling, nonlinear costs, gains or losses along arcs, and general side constraints require extensions or reformulations; they are not automatically covered by the ordinary identity. A general LP solver may solve such a model with simplex, but that does not make its pivots network-simplex 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. If the answer names only residual negative cycles, shortest augmenting paths, a cost-scaling admissible graph, or a generic LP tableau, it is not.

The \((T,L,U)\) notation also prevents a common half-correct explanation. In an uncapacitated, zero-lower-bound classroom presentation, nonbasic flows can all be zero. In the bounded problem, however, one set of non-tree arcs is at lower bounds and another at upper bounds. Reduced-cost eligibility reverses with that status: a lower-bound arc can move only upward, while an upper-bound arc can move only downward. Stating “choose a negative-reduced-cost nonbasic arc” without the bound qualification silently drops half of the algorithm.

Finally, the root, tree, and cycle are computational structures rather than claims about the modeled system. The root normalizes potentials; the tree identifies a basis; the fundamental cycle determines the unique conservation-preserving direction created by one entering arc. That interpretation separates the actual method from pictures that merely happen to contain a rooted graph.

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. The algorithm therefore replaces a dense-looking linear-algebra update with a sparse combinatorial data structure and local tree operations.^[1]^[2]

This compression makes the next decision explicit. Pricing asks which bound-fixed arc violates the dual sign conditions. The ratio/residual test asks how far the corresponding cycle direction can move. The leaving-arc choice asks which bound becomes active. Rather than search all feasible flows, the method walks adjacent basic feasible solutions while retaining a compact certificate of feasibility. When it stops, potentials and reduced-cost signs provide an optimality certificate; the method does not merely report that no locally appealing route was found.

Implementation complexity remains real. Full pricing scans every non-tree arc and may spend much of an iteration finding an entering candidate; partial pricing and candidate lists reduce scanning but can accept weaker improvements. Tree updates, potential updates, initialization, degeneracy, and memory layout can dominate practical performance. Király and Kovács's implementation study is instructive precisely because it treats pivot rule, search strategy, and data structure as consequential algorithm engineering and finds different solvers favored on different instance regimes.^[5]

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.
Complete the residual-capacity branch before updating the basis. If a tree arc limits, exchange it with the entrant; if the entrant reaches its opposite bound first, flip its bound status and keep the tree; if the improving cycle has no finite bottleneck, report unboundedness.
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. Repeated zero-change pivots call for an anti-cycling or strongly feasible-tree discipline.
If no non-tree arc is eligible under its bound-aware sign condition, stop with an optimality certificate. Primal feasibility is already maintained; the node potentials now satisfy the required reduced-cost inequalities.
If the implementation spends most of its time pricing, change the entering-arc search policy before redesigning augmentation. Candidate lists, block search, and partial pricing trade per-iteration search cost against the quality and number of pivots.
If a model adds arbitrary side constraints, expect the spanning-tree basis representation to fail. The correct intervention may be decomposition, a generalized-network method, or a general LP solver; forcing the pure network-simplex label hides a structural change.
If someone claims polynomial time for “network simplex,” ask for the pivot rule and variant. Orlin's theorem supports a cost-scaling premultiplier algorithm with specified bounds, not every conventional implementation.^[4]

These deductions are stronger than “use a graph algorithm.” They predict which local object to inspect (bound status and reduced cost), what change preserves feasibility (cycle augmentation), why progress can stall (degeneracy), and what evidence justifies termination (dual-compatible reduced costs).

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.

Engineering techniques also transfer within this solver family. An artificial-tree Phase I construction provides an initial basis when a natural feasible tree is unavailable. Candidate-list or block pricing reduces repeated arc scans. Tree data structures accelerate predecessor, depth, thread, or subtree updates. Warm starting preserves a useful basis under modest data changes. Anti-cycling rules address degenerate basis sequences. Each intervention modifies a stable role in the same closure and can be compared across network-optimization applications.^[1]^[5]

Beyond mathematical programming, “keep a backbone, admit a promising connection, adjust around the loop, and remove the bottleneck” is only analogy. The portable residue belongs to the broader catalog abstractions algorithm, optimization, duality, iteration, and tree exchange. Without conserved flows, linear arc costs, bound-aware reduced costs, and a fundamental-cycle basis pivot, the network-simplex mechanism is not literally present. That boundary is why this entry is domain-specific rather than a prime.

Examples¶

Canonical: one fundamental-cycle pivot¶

Cheung's instructional network-simplex example begins from a four-node feasible tree solution with tree arcs \(T=\{e_1,e_3,e_6\}\) and flow vector \((4,0,3,0,0,2)\). Rooted node potentials are \((7,4,2,0)\). Non-tree arc \(e_2\), directed from node 1 to node 3 with cost 1, is eligible because the potential difference \(7-2=5\) exceeds its cost under the notes' sign convention. Adding \(e_2\) creates the unique cycle through \(e_1,e_2,e_3\). Increasing \(e_2\) requires decreasing the two oppositely oriented tree flows; their available amounts are 4 and 3, so \(\theta=3\). The new flow is \((1,3,0,0,0,2)\), arc \(e_3\) reaches its lower bound and leaves, and the new tree is \(\{e_1,e_2,e_6\}\). Node balances persist although three arc values change.^[3]

Mapped back: the costed flow network supplies the costs and balances; \(\{e_1,e_3,e_6\}\) is the feasible tree basis; \((7,4,2,0)\) is the node-potential system; \(e_2\) passes the bound-aware pricing test; \(e_2\) plus the tree gives the fundamental cycle; \(\theta=3\) exposes \(e_3\) as the leaving arc; and replacing \(e_3\) by \(e_2\) completes the one-arc basis exchange.

Applied / In Practice: a costed three-worker assignment¶

Consider an illustrative assignment with workers \(W_1,W_2,W_3\), jobs \(J_1,J_2,J_3\), and cost matrix

\[ \begin{pmatrix} 4&1&3\\ 2&0&5\\ 3&2&2 \end{pmatrix}. \]

Construct a network with a source supplying three units, unit-capacity arcs to each worker, worker-to-job arcs carrying the matrix costs, and unit-demand arcs from each job to a sink. This is the standard assignment-to-minimum-cost-flow reduction; integer supplies and capacities yield an integral optimal flow.^[3]^[1] A network-simplex implementation maintains a feasible spanning-tree basis over this expanded network and pivots eligible worker-job arcs into it. At optimality the positive worker-job flows select \(W_1\to J_2\), \(W_2\to J_1\), and \(W_3\to J_3\), with total cost \(1+2+2=5\). The assignment interpretation is applied, but the solver's objects remain flows, bounds, potentials, reduced costs, and tree exchanges.

Mapped back: unit source, worker, job, and sink arcs form the bounded costed network; a feasible initial assignment is encoded by the tree basis; potentials and reduced-cost pricing rank non-tree worker-job arcs; an entering reassignment creates a fundamental alternating cycle; the unit residual limit identifies the leaving arc; repeated basis exchanges preserve one worker per job; and the final lack of an eligible arc supplies the optimality certificate.

Structural Tensions¶

T1: Sparse graph exploitation versus model generality. The algorithm is powerful because it treats a minimum-cost-flow basis as a tree and a pivot as one fundamental-cycle update. Add arbitrary side constraints, multiple coupled commodities, nonlinear arc interactions, or gains and losses, and that representation may no longer describe a basis. Keeping the network form buys sparse specialized operations; expanding the model buys fidelity but can force a general LP, decomposition method, or different algorithm.

Diagnostic: Do the added constraints preserve a node-arc incidence basis with bound-fixed non-tree arcs, or has the model crossed the boundary where a tree no longer represents feasible bases?

T2: Strong pricing versus cheap pricing. Scanning every non-tree arc can find a strongly improving entrant but spend most of the iteration on search. Partial pricing, block search, and candidate lists cut that cost, yet may choose weaker pivots and require more iterations. There is no context-free best choice because performance depends on graph size, sparsity, cost distribution, and how quickly reduced costs become stale after tree updates.^[5]

Diagnostic: Is runtime dominated by arc scanning or by too many low-value pivots, and which pricing policy moves that specific bottleneck?

T3: Primal feasibility versus dual improvement. The tree flow is kept feasible at every ordinary primal pivot, while reduced costs reveal dual violations. Aggressively following an improving reduced cost is useless unless the corresponding cycle augmentation respects every lower and upper bound; conversely, preserving feasibility without pricing can leave a costly flow untouched. The method works because the entering test and residual bottleneck are paired.

Diagnostic: Has the proposed entrant been checked together with its feasible residual cycle, or is one side of the primal-dual pair being optimized in isolation?

T4: Basis motion versus objective progress. Degenerate pivots are legitimate basis exchanges and may be necessary to expose a productive neighbor, but \(\theta=0\) means no primal or objective progress. Uncontrolled ties can lead to long stalls or cycling; overly rigid anti-cycling choices can sacrifice practical pivot quality. The algorithm must distinguish structural motion from numerical improvement.

Diagnostic: Are zero-change pivots rare transitions toward a better basis, or is the basis sequence revisiting equivalent states without a termination-preserving rule?

T5: Practical speed versus worst-case guarantee. Conventional network simplex is valued for implementation simplicity, warm starts, and strong empirical performance, yet natural pivot rules can be exponential in the worst case. Orlin's qualifying polynomial variant restores a theorem through cost scaling and premultiplier structure, not by blessing all implementations. The theoretically safer variant and the empirically fastest code need not be the same design.^[4]^[5]

Diagnostic: Is the decision governed by a proof obligation on worst-case pivots, or by measured performance on a known instance distribution—and has the claim been stated at the corresponding level?

T6: Autonomous named method versus reduction to its parents. Network simplex deserves a separate name because the tree-basis/potential/fundamental-cycle closure provides precise diagnostics, variants, and implementation interventions. Yet its cross-domain reach does not belong to that name: algorithm supplies procedural closure, network_flow_models supplies the problem grammar, and tree_graph_theory supplies the unique-cycle exchange. Treating the child as a prime overstates portability; reducing it to generic parents hides the solver-specific identity.

Diagnostic: Does the question require bound-aware pricing, a fundamental-cycle pivot, and degeneracy handling—in which case the named child is useful—or only the broader algorithm/network/tree structure, in which case the parents carry the reasoning?

Structural–Framed Character¶

Network Simplex Algorithm is structural-leaning on the structural–framed spectrum. Its mechanism is formal, neutral, and reproducible, but the operative vocabulary and guarantees remain tied to the mathematical-programming frame that makes a flow basis a tree.

On evaluative weight, it is structural: “minimum” refers to an explicitly supplied linear objective, not an unspoken judgment about what ought to count as good. On human-practice-boundedness, the procedure can be defined and executed mechanically once a network instance is given, although modeling a real situation as costs, capacities, and balances is a human act. On institutional origin, it is an artifact of operations research and linear programming rather than a naturally occurring causal process. On vocabulary travel, it is framed: tree basis, nonbasic bound status, node potential, reduced cost, entering arc, and leaving arc retain their inferential force only within network optimization. On import versus recognition, one recognizes the same method across transportation and assignment reductions, but importing its cycle-exchange metaphor into an organization does not instantiate the algorithm.

The portable skeleton is the prime algorithm: maintain a representation, test a stopping condition, apply a correctness-preserving update, and iterate. Network Flow Models and Tree (Graph Theory) supply more specific mathematical prerequisites, but their joint reach still does not make the solver name travel beyond optimization.

Its character: a highly structural formal procedure whose identity nevertheless depends on a specialized network-flow frame.

Structural Core vs. Domain Accent¶

This section decides why Network Simplex Algorithm is a domain-specific abstraction and not a prime.

What is skeletal (could lift toward a cross-domain prime). The thin portable structure is iterative basis improvement: maintain a feasible representation, evaluate excluded alternatives by a local certificate, introduce one promising alternative, follow the unique repair path it creates, remove the limiting incumbent element, and stop when no admissible improvement remains. algorithm, iteration, optimization, and exchange-style reasoning can carry that skeleton into other settings. The more specific tree fact—adding one non-tree edge creates a unique fundamental cycle—also travels wherever the object literally is a graph-theoretic spanning tree, but that reach belongs to tree_graph_theory, not to network simplex itself.

What is domain-bound. The named method requires the minimum-cost-flow LP: directed arc variables with linear costs and lower/upper bounds; node supplies and demands; conservation constraints; a basic feasible solution represented by a spanning tree and bound-fixed non-tree arcs; node potentials derived from tree costs; reduced-cost signs interpreted against bound status; and a cycle augmentation whose limiting residual capacity identifies the leaving arc. Remove conserved flow or the network incidence matrix and “tree basis” loses its LP meaning. Remove potentials and reduced costs and the method cannot price entrants or certify optimality. Remove the fundamental-cycle exchange and it becomes some other minimum-cost-flow algorithm or a generic simplex implementation.

Why this does not clear the prime bar. Its in-domain transfer is broad but bounded. Assignment, transportation, transshipment, routing reductions, and time-expanded scheduling can all instantiate the exact mechanism because they are represented as minimum-cost flows. Outside that mathematical habitat, phrases such as “add a promising relationship and remove the bottleneck around the resulting loop” borrow only the shape. The actual diagnostics—whether an arc is in \(L\) or \(U\), whether \(\bar c_{ij}\) violates its sign condition, whether \(\theta=0\), whether a tree remains strongly feasible—do not survive. Cross-domain reasoning should therefore route to the parent primes; the network-simplex node remains the precise solver-level abstraction needed inside operations research.

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 its specified variant. It adds a particular representation, pivot rule family, invariants, and stopping certificate to the general algorithm structure. Remove the algorithmic parent and there is no ordered execution or correctness claim; the parent remains meaningful without network flows.

prime:network_flow_models — composition / presupposes. The algorithm presupposes the parent model's directed arcs, costs, capacities, supplies/demands, and conservation equations. Those objects define feasibility, objective value, and dual node potentials. Network Flow Models already mentions network simplex as one possible solver, but does not entail a tree basis or any particular pivot mechanism; many other algorithms solve the same models.

domain_specific:tree_graph_theory — composition / presupposes. The selected basis is a spanning tree, adding one non-tree arc creates exactly one fundamental cycle, and exchanging one cycle arc restores a tree. Those are literal tree-graph-theory consequences, not decorative vocabulary. This direct relation remains useful because network_flow_models as a broad parent does not require a tree representation: cost-scaling and successive-shortest-path solvers use the model without it.

prime:linear_programming_lp is a real broader ancestor but is declined as a direct working parent: the LP structure is already carried through network_flow_models, and adding it would not sharpen the child's placement. prime:optimization and prime:duality are likewise true but transitively or compositionally remote. They belong in explanatory prose and related, not in the minimal proposed parent set.

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

Not to Be Confused With¶

General simplex method. This is the LP-wide parent method that exchanges entering and leaving variables between adjacent bases. Network simplex exploits a node-arc incidence matrix so a basis is a tree and a pivot is a fundamental-cycle flow update. Tell: Can the basis and ratio test be performed through a spanning tree and residual cycle, or does the method require general LP basis algebra?
Minimum-cost flow / Network Flow Models. This is the optimization problem and model family, not a solver. It can be solved by network simplex, cycle-canceling, successive shortest paths, cost scaling, or general LP methods. Tell: Are you specifying costs, bounds, balances, and an objective, or specifying the tree-potential-pivot procedure used to solve them?
Transportation simplex. This is a closely related specialization for bipartite transportation-table structure. It shares basic-cell/tree and alternating-cycle ideas, but is narrower than arbitrary directed capacitated min-cost flow. Tell: Does the formulation require only supply-to-demand table cells, or can it include transshipment nodes and general directed arc bounds?
Tree (Graph Theory). A spanning tree supplies unique paths and fundamental cycles after an edge is added. It does not supply flow conservation, arc bounds, node potentials, reduced costs, an objective, or a pivot rule. Tell: Is the tree merely the graph object, or is it being maintained as an LP basis with priced bound-fixed arcs?
Cycle-canceling algorithm. This solver augments along improving residual cycles. The shared cycle operation does not imply a maintained tree basis or a one-entering/one-leaving exchange. Tell: Is each cycle uniquely induced by adding a priced non-tree arc to the current basis, or is an improving residual cycle selected independently of a basis tree?
Generic pivot algorithm. Pivoting broadly means changing representation around a chosen element or coordinate. Network simplex requires the minimum-cost-flow dual and feasibility obligations. Tell: Do node-potential reduced costs and residual cycle capacities determine the pivot, or is “pivot” only a generic local update?
Dual network-simplex methods. Dual variants maintain different feasibility conditions and repair primal violations while preserving a dual structure; they are related but not lossless aliases for the primal feasible-tree loop developed here. Tell: Does every ordinary iteration preserve primal flow feasibility while repairing reduced-cost violations, or preserve dual feasibility while repairing the primal side?

References¶

[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Chapter 11 treats network-simplex algorithms, tree solutions, potentials, pivot rules, sensitivity, and their relationship to general simplex. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i

[2] Hochbaum, D. S. (2018/2019). Lecture Notes for IEOR 266: Graph Algorithms and Network Flows. University of California, Berkeley, §§19.1–19.5. Gives the bounded minimum-cost-flow formulation, \((T,L,U)\) structure, tree-basis correspondence, optimality conditions, and cycle-canceling comparison. registry ↩a ↩b

[3] Cheung, K. (n.d.). “MATH 3802: Network Simplex Method.” Carleton University. Gives the tree-solution algorithm, potentials, entering and leaving arcs, worked cycle pivots, reduced-cost stopping condition, and assignment reduction. registry ↩a ↩b ↩c ↩d

[4] Orlin, J. B. (1997). “A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows.” Mathematical Programming, 78, 109–129. Establishes the polynomial cost-scaling premultiplier variant and its pivot/time bounds; it does not claim the same bound for every pivot rule. registry ↩a ↩b ↩c ↩d ↩e

[5] Király, Z., & Kovács, P. (2012). “Efficient Implementations of Minimum-Cost Flow Algorithms.” Technical report and LEMON implementation study. Compares network simplex, cost scaling, cycle-canceling, and established codes; documents pricing and implementation choices and instance-dependent practical performance. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g