Hubbry Logo
Network simplex algorithmNetwork simplex algorithmMain
Open search
Network simplex algorithm
Community hub
Network simplex algorithm
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Network simplex algorithm
Network simplex algorithm
Network simplex algorithm
View on Wikipedia
from Wikipedia

In mathematical optimization, the network simplex algorithm is a graph theoretic specialization of the simplex algorithm. The algorithm is usually formulated in terms of a minimum-cost flow problem. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.[1]

History

[edit]

For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 Orlin provided the first polynomial algorithm with runtime of where is maximum cost of any edges.[2] Later Tarjan improved this to using dynamic trees in 1997.[3] Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.[4]

Overview

[edit]

The network simplex method is an adaptation of the bounded variable primal simplex algorithm. The basis is represented as a rooted spanning tree of the underlying network, in which variables are represented by arcs, and the simplex multipliers by node potentials. At each iteration, an entering variable is selected by some pricing strategy, based on the dual multipliers (node potentials), and forms a cycle with the arcs of the tree. The leaving variable is the arc of the cycle with the least augmenting flow. The substitution of entering for leaving arc, and the reconstruction of the tree is called a pivot. When no non-basic arc remains eligible to enter, the optimal solution has been reached.

Applications

[edit]

The network simplex algorithm can be used to solve many practical problems including,[5]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Network simplex algorithm

View on Grokipedia
from Grokipedia
The network simplex algorithm is a specialized implementation of the simplex method for linear programming, tailored to solve minimum-cost flow problems on directed graphs by leveraging the inherent network structure to enhance computational efficiency. In these problems, flows are assigned to arcs connecting nodes, subject to capacity bounds and node supply/demand constraints, with the goal of minimizing total transportation cost while satisfying all requirements. The algorithm represents basic feasible solutions as spanning trees of the graph, where pivot operations correspond to adding an entering arc and removing a leaving arc from a fundamental cycle, systematically moving between extreme points of the feasible region until optimality is achieved. Developed as an adaptation of George B. Dantzig's general method, the network simplex was first applied to transportation problems in a 1951 , where it demonstrated how the simplex framework could efficiently handle structured linear programs arising in and allocation. Subsequent refinements, including anti-cycling rules like the leaving arc selection to prevent unbounded loops, have made it a of network optimization, with polynomial-time variants introduced in the to address worst-case exponential behavior. In practice, the algorithm excels due to its use of graph-specific data structures for rapid pivot computations, often requiring far fewer iterations than the general method for large-scale network problems, though it may degenerate without careful . It typically starts from an initial basis, computes reduced costs using node potentials (simplex multipliers), and selects entering arcs with negative reduced costs to decrease the objective value, ensuring feasibility throughout. This approach not only simplifies the representation of constraints but also facilitates extensions to generalized networks with arc gains or losses, broadening its applicability in .

Background

Minimum-Cost Flow Problem

The involves finding the least expensive way to route a specified amount of flow through a network of nodes and , respecting capacity limits and satisfying supply and demand requirements at each node. This problem generalizes classical transportation and assignment problems by allowing intermediate transshipment nodes and is a cornerstone of network optimization. Formally, the problem is posed on a G=([V](/page/V.),[E](/page/E!))G = ([V](/page/V.), [E](/page/E!)), where [V](/page/V.)[V](/page/V.) denotes the set of nodes and [E](/page/E!)[E](/page/E!) the set of arcs. Each node i∈[V](/page/V.)i \in [V](/page/V.) is associated with a supply/demand value bi∈Rb_i \in \mathbb{R}, satisfying ∑i∈[V](/page/V.)bi=0\sum_{i \in [V](/page/V.)} b_i = 0 (positive bib_i indicates supply, negative indicates ). Each arc (i,j)∈[E](/page/E!)(i, j) \in [E](/page/E!) has a nonnegative capacity uij≥0u_{ij} \geq 0 and a per-unit cost cij∈Rc_{ij} \in \mathbb{R}. The objective is to determine a flow xij≥0x_{ij} \geq 0 on each arc (i,j)(i, j) that minimizes the total transportation cost ∑(i,j)∈Ecijxij\sum_{(i,j) \in E} c_{ij} x_{ij}, subject to flow conservation constraints ∑j:(i,j)∈Exij−∑k:(k,i)∈Exki=bi\sum_{j : (i,j) \in E} x_{ij} - \sum_{k : (k,i) \in E} x_{ki} = b_i for all i∈Vi \in V, and capacity constraints xij≤uijx_{ij} \leq u_{ij} for all (i,j)∈E(i,j) \in E. Node potentials and cycle structures provide essential theoretical foundations for network flows, enabling the analysis of optimality and the design of efficient algorithms. Node potentials are real-valued labels πi\pi_i assigned to each node i∈Vi \in V, which define reduced costs cij′=cij+πi−πjc'_{ij} = c_{ij} + \pi_i - \pi_j for arcs; these reduced costs preserve the total flow cost while simplifying the detection of improving directions. Cycle structures refer to directed cycles in the residual graph, where a flow is optimal if and only if there exists a set of node potentials such that all reduced costs are nonnegative, implying no negative-cost cycles that could reduce the objective further. A representative example is a capacitated network with five nodes (1 through 5), where nodes 1 and 2 supply 2 and 1 units respectively (b1=2b_1 = 2, b2=1b_2 = 1), node 4 demands 5 units (b4=−5b_4 = -5), node 3 has zero net balance (b3=0b_3 = 0), and node 5 acts as a slack supply node with b5=2b_5 = 2 to ensure feasibility. The network includes eight arcs with specified capacities and costs as follows:
ArcFromToCapacity uiju_{ij}Cost cijc_{ij}
112511
213416
323312
424418
534313
6355-25
745310
851511
In this setup, flow originates from supply nodes, passes through transshipment node 3, and satisfies the demand at node 4, potentially flow through the slack node to minimize .

Relation to Method

The network represents a specialized adaptation of the general for , tailored to exploit the structured of network flow problems. In the standard simplex method, the algorithm maintains a defined by a set of n linearly independent variables forming a basis, with the remaining non-basic variables set to zero or bounds; it iteratively selects an entering variable with a negative reduced cost to improve the objective, performs a pivot to update the basis by exchanging entering and leaving variables, and continues until optimality is reached where all reduced costs are non-negative. For network problems, such as the minimum-cost flow formulation, basic feasible solutions correspond directly to of the underlying , where the basic arcs form a tree connecting all nodes without cycles, ensuring linear independence of the corresponding columns in the . Non-basic arcs, when added to this , create a unique fundamental cycle, allowing the algorithm to identify the leaving arc through flow augmentation along this cycle while preserving feasibility and restoring the . This graph-theoretic interpretation simplifies pivot operations compared to the general case. In the dual formulation, the simplex multipliers—dual variables associated with the flow balance constraints—are interpreted as node potentials πi\pi_i for each node ii. The reduced cost for an arc (i,j)(i,j) is then given by cij′=cij+πi−πj,c'_{ij} = c_{ij} + \pi_i - \pi_j, where cijc_{ij} is the original arc cost; optimality holds when cij′≥0c'_{ij} \geq 0 for all non-basic arcs (or satisfies bound conditions for capacitated flows), ensuring no improving direction exists. These potentials can be efficiently computed and updated using the spanning tree, as the differences πj−πi\pi_j - \pi_i along tree paths define consistent values. This specialization yields significant advantages over the general method applied to the equivalent linear program, including a sparser structure with far fewer non-basic variables (typically on the order of the number of arcs rather than the full dimension), and explicit via traversals that avoids costly matrix inversions or full tableau updates, often resulting in pivots that are computationally faster by factors of 200 to 300 in practice for large networks.

Core Concepts

Network Representation

The network simplex algorithm models the underlying optimization problem using a directed graph G=(V,E)G = (V, E), where VV denotes the set of nodes and EE the set of directed arcs. Each node i∈Vi \in V has an associated supply or demand bib_i, satisfying ∑i∈Vbi=0\sum_{i \in V} b_i = 0, while each arc (i,j)∈E(i,j) \in E carries a cost cijc_{ij}, an upper capacity bound uiju_{ij} (possibly infinite), and a flow value xij≥0x_{ij} \geq 0. This graph representation captures the conservation of flow at nodes and the objective of minimizing total arc costs subject to capacity constraints. To handle cases where the original network has unbalanced supplies and demands—preventing an immediate feasible flow—artificial nodes or arcs are incorporated. A common approach introduces an artificial root node ss not in VV, connected via return arcs (i,s)(i, s) for nodes with positive supply bi>0b_i > 0 and supply arcs (s,i)(s, i) for nodes with negative demand bi<0b_i < 0. These artificial elements, often assigned zero or high costs and infinite capacities, ensure the extended graph admits a basic feasible solution for initialization, with initial flows set to ∣bi∣|b_i| on these arcs. Central to the algorithm is an acyclic spanning tree T⊆ET \subseteq E, comprising ∣V∣−1|V| - 1 arcs that connect all nodes without forming cycles, thereby defining a basic feasible solution where node supplies uniquely determine arc flows via tree paths. Adding any non-tree arc e∉Te \notin T to the tree induces a unique fundamental cycle consisting of ee and the path in TT between its endpoints, which plays a crucial role in identifying adjustment directions for flows during iterations. Node potentials πi\pi_i for i∈Vi \in V are computed relative to this spanning tree structure to evaluate reduced costs efficiently. The tree is rooted at an arbitrary node, inducing a hierarchical ordering of nodes by levels or depths along tree paths from the root, which allows solving the system πi−πj=cij\pi_i - \pi_j = c_{ij} for all tree arcs (i,j)∈T(i,j) \in T in linear time via backward substitution. For computational efficiency, the graph employs adjacency lists to store outgoing and incoming arcs per node, facilitating O(∣E∣)O(|E|) traversals for residual network updates. The spanning tree is augmented with specialized data structures, such as parent arrays (e.g., predecessor links) for path tracing, depth arrays for level-based ordering, and thread links connecting nodes at the same level to enable O(∣V∣)O(|V|) cycle identification and potential recomputation without full graph rescans.

Basis and Tree Structure

In the network simplex algorithm, a feasible basis for the minimum-cost flow problem corresponds to a spanning tree of the underlying directed graph, where the tree arcs represent the basic variables and non-tree arcs the non-basic ones. This structure leverages the totally unimodular property of the node-arc incidence matrix, ensuring that each spanning tree defines a unique basic solution. The tree is typically rooted at an arbitrary node, such as a reference node with zero supply, to facilitate flow computations. A basic feasible solution is obtained by assigning flows solely to the tree arcs such that the flow conservation constraints (node balances) are satisfied, with non-tree arcs carrying zero flow. Specifically, for a tree arc directed from node ii to node jj, the flow value is equal to the negative of the sum of supplies (or demands) over all nodes in the subtree rooted at jj, assuming supplies are positive for sources and negative for sinks. This recursive computation begins at the leaves of the tree, where a leaf node's flow on its outgoing arc matches its own supply, and propagates upward, ensuring global balance without cycles. If the resulting flows on tree arcs violate capacity bounds, the solution is infeasible, but a feasible basis requires all flows to lie within their bounds. Reduced costs for non-basic arcs can then be computed relative to dual variables associated with the tree, analogous to the general simplex method. Degeneracy arises when one or more tree arcs carry zero flow, meaning the basic solution has fewer than n−1n-1 positive variables for a graph with nn nodes, yet still spans the feasible region. In such cases, these zero-flow tree arcs serve as potential candidates for removal during pivots, allowing the algorithm to handle degenerate bases without explicit perturbation techniques common in general linear programming. This property simplifies degeneracy resolution in network contexts compared to dense LPs. A key property is the cycle theorem: introducing a non-basic (non-tree) arc into the spanning tree creates exactly one unique fundamental cycle, consisting of the new arc and the unique path in the tree connecting its endpoints. Augmenting flow along this cycle—by increasing flow on forward arcs and decreasing on reverse arcs—preserves feasibility as long as the augmentation amount does not exceed the minimum residual capacity on the cycle, maintaining node balances since the cycle nets zero supply. This ensures that the updated flow remains a valid basic solution associated with the new spanning tree obtained by removing the appropriate tree arc from the cycle. To illustrate, consider a simple network with four nodes (1,2,3,4) and supplies b1=5b_1 = 5, b2=−3b_2 = -3, b3=−4b_3 = -4, b4=2b_4 = 2, rooted at node 1. A spanning tree might include arcs (1,2), (1,3), and (3,4). The flow on (3,4) would be −b4=−2-b_4 = -2 (directed toward the root, but adjusted for direction), on (1,3) the sum for subtree at 3 (b3+b4=−2b_3 + b_4 = -2), and on (1,2) simply b2=−3b_2 = -3. Adding a non-tree arc (2,3) forms a cycle 1-2-3-1; augmenting along it would adjust flows while preserving the total supplies in subtrees. This tree structure with flows and the induced cycle highlights how bases encode feasible solutions compactly.

Algorithm Steps

Initialization Phase

The initialization phase of the network simplex algorithm requires establishing an initial basic feasible solution, represented by a spanning tree that satisfies the node balance constraints of the minimum-cost flow problem. One approach to finding this initial tree involves constructing a shortest-path tree rooted at an arbitrary node, where paths are computed using reduced costs (initially set to original costs) to ensure the tree arcs form a feasible basis without cycles. Alternatively, greedy methods can build the spanning tree by iteratively selecting arcs that connect components while respecting supply and demand balances, often starting from a forest and merging until a single tree is formed. These methods ensure the tree has exactly n−1n-1 arcs for nn nodes, providing a basic solution where flows can be determined to meet the balances. For networks that are unbounded or unbalanced (e.g., total supply not equal to total demand), dummy nodes are introduced to facilitate feasibility. A dummy source node is added with supply equal to the excess demand, connected to demand nodes via zero-cost arcs of sufficient capacity, while a dummy sink node receives excess supply from supply nodes through similar zero-cost arcs. This transformation balances the network, allowing the spanning tree to incorporate these arcs temporarily without affecting the original costs, and ensures a feasible circulation can be computed. If capacities are infinite on some arcs, additional checks during tree construction verify boundedness by detecting infinite residual cycles. In cases where an obvious feasible tree is unavailable, artificial variables are employed in a Phase I procedure to reach feasibility. A root node ss is selected, and artificial arcs are added from ss to nodes with positive supply (or vice versa for demands) with high penalty costs (e.g., larger than any original cost) and infinite capacity. Initial flows on these arcs are set to the absolute values of the imbalances ∣bi∣|b_i|, forming a trivial tree. The network simplex is then run on this auxiliary problem with minimized artificial flow as the objective; if the optimal solution has zero artificial flow, the resulting tree and flows provide the initial basic feasible solution for Phase II on the original problem. Otherwise, the problem is infeasible. Once the initial spanning tree is obtained (including any artificial or dummy arcs), the flows on the tree arcs are computed via backward substitution from the leaves to satisfy the balance equations. This process, known as the Compute-Flows algorithm, processes nodes in a post-order traversal, assigning flows based on node imbalances and propagating adjustments upward.

pseudocode

Algorithm Compute-Flows(T, b): Initialize e_i = b_i for all nodes i S = set of tree arcs T While S is not empty: Select a leaf node i ≠ root in the current tree Let (i,j) or (j,i) be the unique tree arc incident to i If arc is (i,j): set x_{ij} = e_i Else: set x_{ji} = -e_i Update e_j = e_j - x_{ij} (or +x_{ji}) Remove node i and the arc from S Return flows x on tree arcs

Algorithm Compute-Flows(T, b): Initialize e_i = b_i for all nodes i S = set of tree arcs T While S is not empty: Select a leaf node i ≠ root in the current tree Let (i,j) or (j,i) be the unique tree arc incident to i If arc is (i,j): set x_{ij} = e_i Else: set x_{ji} = -e_i Update e_j = e_j - x_{ij} (or +x_{ji}) Remove node i and the arc from S Return flows x on tree arcs

This yields a basic feasible solution where flows respect capacities and balances, with non-tree arcs set to zero. To prepare for iterations, compute initial node potentials π by rooting the tree at an arbitrary node r with π_r = 0, then propagating along the directed arcs: for each basic arc from parent p to child c, set π_c = π_p + c_{pc}, ensuring reduced costs for tree arcs are zero.

Iteration and Pivot Selection

In the network simplex algorithm, each iteration begins with the selection of an entering arc, which is a non-basic arc (i,j)(i, j) in the residual network exhibiting a negative reduced cost cij′<0c'_{ij} < 0. This reduced cost, defined as cij′=cij−πi+πjc'_{ij} = c_{ij} - \pi_i + \pi_j where π\pi are the node potentials and cijc_{ij} is the original arc cost, signals an opportunity to decrease the total cost by incorporating the arc into the basis. Heuristically, the arc with the most negative reduced cost is often chosen to accelerate convergence, though various pricing strategies, such as candidate lists, may be employed to identify eligible arcs efficiently. Adding the entering arc to the current spanning tree basis creates a unique directed cycle in the network, oriented in the direction of the entering arc. This cycle is efficiently identified by finding the unique path in the tree between nodes i and j, for example, by tracing paths from i and j to their lowest common ancestor using predecessor indices in a rooted tree representation, then combining the segments. The cycle consists of the entering arc and the tree path arcs, forming the basis for the subsequent pivot operation. To determine the pivot's extent, the augmenting amount θ\theta is computed as the minimum residual capacity along the forward arcs of the cycle: θ=min⁡(k,l)∈W+{ukl−xkl}\theta = \min_{(k,l) \in W^+} \{ u_{kl} - x_{kl} \} where W+W^+ denotes the forward arcs in the cycle WW, uklu_{kl} is the capacity, and xklx_{kl} is the current flow. The leaving arc is then selected as the tree arc on the cycle achieving this minimum θ\theta, which will be driven to its bound during augmentation. In cases of ties or degeneracy (where θ=0\theta = 0), selection rules prioritize arcs by cost impact or apply Bland's rule to prevent cycling and ensure finite termination. Following the pivot, which exchanges the entering and leaving arcs in the basis, the node potentials are updated to maintain dual feasibility. Specifically, for the subtree separated by the leaving arc, all potentials are adjusted by the negative of the entering arc's reduced cost (with appropriate sign based on orientation), ensuring that reduced costs for the new basic arcs revert to zero. This update preserves the optimality conditions for the revised basis without recomputing all reduced costs from scratch.

Augmentation and Update

Once the entering arc and leaving arc have been selected based on reduced costs and feasibility, the augmentation phase adjusts the current flow along the unique cycle formed by incorporating the entering arc into the spanning tree. This cycle consists of the entering arc and the path in the tree connecting its endpoints. The augmentation amount θ is determined as the minimum residual capacity along this cycle, ensuring that no arc violates its capacity bounds: specifically, θ is the smallest value such that increasing flow on forward arcs and decreasing it on backward arcs (relative to the cycle direction) keeps all flows feasible. For forward arcs in the cycle, flow increases by θ, while for backward arcs, flow decreases by θ; this adjustment propagates the change around the entire cycle, improving the objective function by the cycle's reduced cost times θ. The tree update follows immediately after augmentation, replacing the leaving arc (the one that reaches its bound first, limiting θ) with the entering arc to maintain a feasible spanning tree basis. This involves removing the leaving arc, which partitions the tree into two subtrees, and then reconnecting them via the entering arc. To efficiently identify and update paths in the new tree, is typically used to traverse from the endpoints of the entering arc, relinking nodes and updating predecessor pointers; alternatively, union-find structures can accelerate subtree mergers by maintaining path compression and union by rank for O(α(n)) amortized time per operation, where α is the inverse Ackermann function. Flow propagation occurs concurrently, applying the θ adjustment along the updated paths using the new tree structure, ensuring consistency across all affected arcs. Node potentials are updated to preserve the reduced costs for non-basic arcs in the new basis. Specifically, after the pivot, let δ = -c'_{entering} (>0); the potentials π for nodes in the subtree separated by the leaving arc (the one not containing the , say) are adjusted by adding or subtracting δ depending on whether the or head of the entering arc is in that subtree; this can be done efficiently via a DFS traversal or by leveraging the 's hierarchical structure to propagate the change in O(n time per pivot in basic implementations, or faster with dynamic structures that support subtree updates in O(log n) time. Degeneracy arises when θ = 0, meaning the entering arc can be added without changing flows, as the leaving arc is already at its bound. In this case, the pivot simply swaps the arcs in the basis without altering flows or potentials, but anti-cycling rules (such as lexicographic ordering or perturbation) must be applied to ensure progress and prevent infinite loops. The following outlines the core steps for tree relinking and flow propagation after augmentation, assuming a rooted representation with predecessor arrays:

Procedure UpdateTreeAndFlow(entering_arc = (k, l), leaving_arc = (p, q), θ, c_prime_entering): δ = -c_prime_entering // Positive adjustment amount for potentials // Step 1: Identify the cycle path using proper tree path finding // Trace path from k to root and l to root path_k_to_root = [] current = k while current != root: path_k_to_root.append((pred[current], current)) current = pred[current] path_k_to_root.reverse() // Now from root to k path_l_to_root = [] current = l while current != root: path_l_to_root.append((pred[current], current)) current = pred[current] path_l_to_root.reverse() // From root to l // Find LCA: last common node in path_k_to_root and path_l_to_root min_len = min(len(path_k_to_root), len(path_l_to_root)) lca_index = 0 for idx in 0 to min_len-1: if path_k_to_root[idx] == path_l_to_root[idx]: lca_index = idx else: break lca = path_k_to_root[lca_index] if lca_index < len(path_k_to_root) else root // Tree path from k to l: reverse(path from lca to k) + path from lca to l (excluding lca duplicate) tree_path = reverse(path_k_to_root[lca_index+1:]) + path_l_to_root[lca_index+1:] cycle = tree_path + [entering_arc] // Close cycle // Step 2: Propagate flow along cycle for arc in cycle: if arc is forward in cycle direction: flow[arc] += θ else: flow[arc] -= θ // Update residual capacities accordingly // Step 3: Remove leaving arc and relink subtrees (using DFS for reconnection) RemoveArc(leaving_arc) // Disconnect p and q, creating two subtrees AddArc(entering_arc) // Connect k and l // Relink: Perform DFS from root to update predecessors in affected subtrees DFSRelink(root, entering_arc) // Traverse and set new pred pointers for subtrees // Step 4: Update potentials for affected subtree (add/subtract δ based on side) affected_subtree = Subtree(q) // Assuming q's subtree after removal sign = +1 if l in affected_subtree else -1 // Adjust sign based on entering head/tail location for node in affected_subtree: π[node] += sign * δ // Handle θ = 0: Skip flow changes, but still update tree and potentials if needed if θ == 0: // Proceed with Steps 3 and 4, no flow/propagation

Procedure UpdateTreeAndFlow(entering_arc = (k, l), leaving_arc = (p, q), θ, c_prime_entering): δ = -c_prime_entering // Positive adjustment amount for potentials // Step 1: Identify the cycle path using proper tree path finding // Trace path from k to root and l to root path_k_to_root = [] current = k while current != root: path_k_to_root.append((pred[current], current)) current = pred[current] path_k_to_root.reverse() // Now from root to k path_l_to_root = [] current = l while current != root: path_l_to_root.append((pred[current], current)) current = pred[current] path_l_to_root.reverse() // From root to l // Find LCA: last common node in path_k_to_root and path_l_to_root min_len = min(len(path_k_to_root), len(path_l_to_root)) lca_index = 0 for idx in 0 to min_len-1: if path_k_to_root[idx] == path_l_to_root[idx]: lca_index = idx else: break lca = path_k_to_root[lca_index] if lca_index < len(path_k_to_root) else root // Tree path from k to l: reverse(path from lca to k) + path from lca to l (excluding lca duplicate) tree_path = reverse(path_k_to_root[lca_index+1:]) + path_l_to_root[lca_index+1:] cycle = tree_path + [entering_arc] // Close cycle // Step 2: Propagate flow along cycle for arc in cycle: if arc is forward in cycle direction: flow[arc] += θ else: flow[arc] -= θ // Update residual capacities accordingly // Step 3: Remove leaving arc and relink subtrees (using DFS for reconnection) RemoveArc(leaving_arc) // Disconnect p and q, creating two subtrees AddArc(entering_arc) // Connect k and l // Relink: Perform DFS from root to update predecessors in affected subtrees DFSRelink(root, entering_arc) // Traverse and set new pred pointers for subtrees // Step 4: Update potentials for affected subtree (add/subtract δ based on side) affected_subtree = Subtree(q) // Assuming q's subtree after removal sign = +1 if l in affected_subtree else -1 // Adjust sign based on entering head/tail location for node in affected_subtree: π[node] += sign * δ // Handle θ = 0: Skip flow changes, but still update tree and potentials if needed if θ == 0: // Proceed with Steps 3 and 4, no flow/propagation

This procedure ensures the basis remains feasible and optimal conditions are checked for the next iteration.

Optimality and Analysis

Reduced Costs and Optimality

In the network simplex algorithm, reduced costs are computed relative to node potentials πi\pi_i associated with each node ii. For a basic arc (i,j)(i,j) in the spanning tree, the reduced cost cij′c'_{ij} is zero by construction, ensuring that the potentials satisfy πj−πi=cij\pi_j - \pi_i = c_{ij}. These potentials can be recovered by fixing πs=0\pi_s = 0 for a root node ss and propagating along the tree paths, yielding πj=πi+cij\pi_j = \pi_i + c_{ij} for each tree arc. For non-basic arcs (i,j)(i,j), the reduced cost is given by cij′=cij+πi−πjc'_{ij} = c_{ij} + \pi_i - \pi_j, which adjusts the original cost cijc_{ij} by the potential difference. A feasible solution is optimal if and only if cij′≥0c'_{ij} \geq 0 for all non-basic arcs in the residual network, implying the absence of negative-cost cycles that could improve the objective. This condition verifies that no augmentation along non-basic arcs would decrease the total cost. Node potentials πi\pi_i serve as dual variables in the linear programming formulation of the minimum-cost flow problem, maximizing ∑iπibi\sum_i \pi_i b_i subject to πi−πj≤cij\pi_i - \pi_j \leq c_{ij} for all , where bib_i denotes the supply or demand at node ii. The optimality condition aligns with complementary slackness: for each arc, cij′>0c'_{ij} > 0 implies zero flow (xij=0x_{ij} = 0), while cij′=0c'_{ij} = 0 holds for arcs with positive flow within capacity bounds. This primal-dual framework ensures the solution satisfies both feasibility and optimality in the network context.

Termination Criteria

The network simplex algorithm terminates upon achieving an optimal feasible solution to the minimum-cost flow problem, which requires verifying both feasibility and optimality conditions after each augmentation step. Feasibility is confirmed by ensuring that all flows satisfy capacity constraints (0 ≤ x_{ij} ≤ u_{ij} for each arc) and node balance requirements (supply/demand conservation), typically through a post-augmentation flow computation procedure that propagates values along the spanning tree. Optimality is established when reduced costs indicate no potential improvement, specifically by scanning all non-tree arcs to confirm that none have a negative reduced cost c'_{ij} < 0, as this absence ensures the current basis is optimal with no beneficial pivots available. To prevent unbounded iterations due to cycling—a phenomenon where the algorithm revisits previous bases without progress—termination is guaranteed through anti-cycling mechanisms such as cost perturbation, where small values ε^i (with ε > 0 and i increasing with iteration count) are added to arc costs to enforce a strict decrease in the objective function, or lexicographic pivot rules that prioritize in a fixed order to avoid degenerate cycles. These techniques ensure the algorithm converges in a finite number of steps for any non-degenerate problem instance, though practical implementations often monitor iteration counts as an additional safeguard. Upon termination, the algorithm outputs the optimal flow values x_{ij} for all arcs, computed via the final , along with the minimum total cost ∑ c_{ij} x_{ij}, providing a verifiable solution that satisfies all problem constraints. If no feasible solution exists, the process may detect infeasibility earlier through the absence of an initial basic feasible tree or if artificial variables remain positive in the basis after attempting to find a feasible solution.

Complexity and Variants

Time Complexity Bounds

The basic network simplex algorithm exhibits a per-iteration dominated by O(m) operations for scanning reduced costs across all edges to identify a potential entering arc, followed by O(n) operations for tracing the unique cycle in the and updating the tree structure upon pivoting. These costs arise from the network's sparsity, where m denotes the number of edges and n the number of vertices, making each iteration significantly more efficient than in the dense tableau representation of the general method. In the worst case, the overall of the basic algorithm is exponential in the input size, mirroring the behavior of the general simplex method due to the possibility of an exponential number of degenerate pivots before reaching optimality. However, polynomial-time variants exist, such as the primal network simplex algorithm with cost scaling, which achieves a total time bound of O(\min(n^2 m \log n C, n^2 m^2 \log n)), where C is the maximum absolute arc cost. Key factors influencing the complexity include the number of pivots, which can reach up to O(n m U \log C) in scaling-based implementations before termination, where U bounds the arc capacities. Capacity scaling techniques mitigate the impact of large U by processing the problem in phases with geometrically decreasing capacity thresholds, reducing the pivot count logarithmically. For network-structured problems, the network simplex algorithm is empirically 200 to 300 times faster than general linear programming solvers like the revised simplex method applied to the equivalent dense formulation, owing to the avoidance of full tableau manipulations.

Improved Implementations

Improved implementations of the network simplex algorithm have focused on enhancing pivot operations through advanced data structures and scaling techniques to achieve better practical performance and guaranteed polynomial-time execution. One key advancement involves the use of dynamic trees to maintain the spanning tree structure efficiently during pivots. By representing the tree via Euler tours and treating it as a search tree, updates such as linking and cutting edges can be performed in O(log n) time, where n is the number of vertices, leading to O(log n) time per pivot overall. This approach, introduced by Tarjan in 1997, leverages parallel graph algorithm techniques to combine vertex and edge values across subtrees rapidly. To ensure polynomial-time complexity, variants incorporating scaling mechanisms have been developed. Orlin's 1995 cost-scaling primal network simplex algorithm uses premultipliers with respect to a rooted and adjusts the root per pivot, achieving a of O(min(n²m log(nC), n²m² log n)), where m is the number of arcs and C is the maximum absolute arc cost (or 0 for non-integer costs). This method performs O(min(nm log(nC), nm² log n)) pivots, with average O(n) time per pivot using appropriate data structures, making it the first such polynomial-time version of the primal simplex for minimum cost flows. Capacity scaling variants, building on Edmonds-Karp ideas, further refine this by processing flows in phases based on capacity scales, ensuring strong polynomial time in certain cases. Practical software implementations incorporate these and other optimizations for real-world use. The LEMON C++ library provides a highly efficient NetworkSimplex class, which outperforms implementations in LEDA and MCF libraries while remaining competitive with state-of-the-art cost-scaling codes like CS2, as demonstrated in extensive benchmarks on sparse networks. Similarly, NetworkX, a Python library for graph analysis, includes a network_simplex function that implements the primal variant with the leaving arc rule to prevent , supporting directed graphs with node demands, edge capacities, and costs; it returns the minimum flow cost and edge flow dictionary. Numerical stability is a critical concern in implementations, particularly to avoid floating-point precision issues that can lead to incorrect optimality detection or . For problems with capacities and costs, exact arithmetic using s ensures solutions remain precise and optimal, as the algorithm naturally yields flows under these conditions. NetworkX documentation recommends scaling non- inputs (e.g., multiplying by 100) to s before to mitigate floating-point errors, highlighting that the algorithm is not guaranteed for direct floating-point use. Such practices maintain reliability in software libraries without relying on floating-point approximations.

History

Early Development

The network simplex algorithm originated from the adaptation of George Dantzig's general simplex method, introduced in 1947 for solving linear programming problems, to specialized network flow structures in the early 1950s. Dantzig's seminal application of the simplex method to the transportation problem appeared in 1951, where he demonstrated how the network representation of constraints—modeled as bipartite graphs with supply and demand nodes—could streamline pivot operations by maintaining a tree-structured basis, thus forming the foundational framework for the network simplex approach. In the mid-1950s, advancements in network flow theory by L. R. Ford Jr. and D. R. Fulkerson, particularly their 1956 augmenting path algorithm for maximum flow problems, underscored the computational advantages of exploiting graph-theoretic properties in flow networks, paving the way for simplex-based methods tailored to minimum-cost variants. This period marked the initial recognition that network problems, such as the , benefited from specialized implementations that avoided the full matrix manipulations of general . By the 1960s, researchers including further emphasized the special structure of transportation and assignment problems, integrating dual price adjustments and into iterations to enhance efficiency for these subclasses of network flows. The first explicit formulations of the network simplex algorithm were detailed in texts, such as those by Salah E. Elmaghraby in 1964, and it had likely been employed earlier in planning for during the post-World War II era. Like its general counterpart, the early network simplex shared a non-polynomial worst-case time complexity, prone to exponential pivots in contrived instances, yet it proved remarkably effective in practice for real-world network applications due to the sparsity and acyclicity of typical bases.

Key Contributions and Advances

In the 1980s, significant progress was made toward establishing polynomial-time guarantees for minimum-cost flow problems. Éva Tardos developed the first strongly polynomial algorithm for minimum-cost circulation in 1986, resolving whether the problem could be solved in time independent of the magnitudes of costs and capacities. Building on scaling ideas, Ahuja, Goldberg, Orlin, and Tarjan introduced a double-scaling approach in their 1988 working paper (published 1990), which combines capacity and cost scaling to solve the in polynomial time. This method iteratively reduces an error bound on costs through scaling phases, using flow augmentations to achieve ε-optimality, with a resulting complexity polynomial in the input size and addressing the exponential worst-case behavior of simplex implementations. Orlin's 1988 algorithm further improved the strongly bounds for minimum-cost flow. The 1990s saw additional theoretical refinements focused on pivot selection and enhancements to achieve tighter bounds for simplex-based methods. Orlin developed a primal network simplex algorithm in 1995 that guarantees time by selecting entering variables based on a steepest-edge criterion adapted for networks, combined with careful basis . This yields a of O(V2Elog⁡(VC))O(V^2 E \log (V C)), where VV is the number of vertices, EE the number of edges, and CC the maximum arc cost, marking a key advance in making the simplex method competitive with other algorithms for minimum-cost flows. Complementing this, Tarjan's 1997 work integrated Euler-tour representations of dynamic trees into the network simplex framework, enabling efficient updates to the spanning tree basis during pivots. The approach achieves a complexity of O(VElog⁡Vlog⁡(VC))O(V E \log V \log (V C)) for minimum-cost circulation problems, leveraging the logarithmic-time operations of the to handle path computations and evaluations. These contributions collectively transformed the network simplex from a practical but theoretically unpredictable method into a robust solver with polynomial-time , enabling its application to large-scale network optimization in fields such as and .

Applications

Transportation and Assignment

The transportation problem involves distributing goods from multiple sources to multiple destinations at minimum cost, subject to constraints. It is modeled as a where one set of nodes represents sources with given supplies aia_i, the other set represents sinks with demands bjb_j, and directed edges from sources to sinks carry costs cijc_{ij} per unit flow xijx_{ij}. The objective is to minimize ∑cijxij\sum c_{ij} x_{ij} while satisfying ∑jxij=ai\sum_j x_{ij} = a_i for sources and ∑ixij=bj\sum_i x_{ij} = b_j for sinks, with xij≥0x_{ij} \geq 0. This formulation aligns with the on a network, allowing the network simplex algorithm to solve it efficiently by exploiting the graph structure to identify improving directions via cycles in the residual network. The is a special case of the transportation problem where all supplies and demands are equal to one, reducing it to selecting nn edges in an n×nn \times n to form a of minimum total cost. The network simplex algorithm applies directly here, using a primal simplex framework adapted for networks, where the basis corresponds to a of the bipartite graph plus return arcs for supplies and demands. This approach yields a polynomial-time solution, performing O(n2log⁡n+nm)O(n^2 \log n + n m) time for sparse instances with mm edges, though for the dense complete of assignment problems, it runs in O(n3)O(n^3) time. While conceptually equivalent to the , which also solves the in O(n3)O(n^3) time, the network simplex often performs better in practice for very large instances due to its ability to leverage network data structures and avoid redundant computations in dual price updates. Consider a 3x3 transportation example with sources having supplies 45, 60, and 35 units (total 140), and original destinations with demands 50 and 60 units (total 110). To balance, add a dummy sink with demand 30 and zero costs on edges to it. The cost matrix is:
Dest 1Dest 2Dummy Dest 3
Source 1320
Source 2150
Source 3240
An initial via the northwest corner method allocates: 45 to (1,1), 5 to (2,1), 55 to (2,2), 5 to (3,2), and 30 to (3,3), with total cost 435. Computing dual prices (shadow prices uiu_i for sources and vjv_j for destinations) gives reduced costs; non-basic edges with negative reduced costs enter the basis. Pivoting adjusts flows along fundamental cycles until optimality, when all reduced costs are non-negative. The optimal solution is: 45 to (1,2), 50 to (2,1), 10 to (2,3), 15 to (3,2), and 20 to (3,3), with minimum cost 200. This trace illustrates how the network identifies improving directions and achieves optimality. A key benefit of the network simplex for transportation problems is its ability to handle unbalanced cases—where total supply ≠ total demand—by introducing a dummy source (if supply < demand) or dummy sink (if supply > demand) with zero costs on all relevant edges, effectively balancing the network without altering the original flows. This modification preserves the bipartite structure and allows the algorithm to proceed as in the balanced case, ensuring feasibility and optimality.

Broader Network Optimization

The network simplex algorithm extends to applications, such as optimizing decisions and inventory management in supply chains, where it models flows across distribution networks to minimize costs while respecting capacity constraints. In these contexts, the algorithm efficiently handles dynamic supply-demand imbalances by treating warehouses, transportation links, and retailers as nodes and arcs in a . In telecommunications, the network simplex algorithm supports traffic engineering and minimum-cost routing by solving for optimal data packet flows through network topologies, ensuring balanced load distribution and reduced latency under bandwidth limits. This application is particularly valuable for managing multiservice networks, where diverse traffic types (e.g., voice and video) compete for resources, allowing providers to minimize operational costs while meeting quality-of-service requirements. Financial applications leverage the algorithm for , modeling asset allocations as flows in supernetworks that incorporate transaction costs, diversification constraints, and risk measures to achieve equilibrium between returns and exposure. Here, nodes represent financial instruments or markets, and arcs denote paths, enabling the of cost-minimizing strategies in multi-period settings with interconnected economic variables. In bioinformatics, the network simplex algorithm underpins flux balance analysis (FBA) for pathway analysis in metabolic networks, optimizing steady-state flux distributions through enzymatic reactions to predict cellular behaviors under varying conditions. By formulating genome-scale models as linear programs, FBA uses the simplex method to maximize objectives like production, revealing insights into essentiality and nutrient utilization without kinetic data. Across these domains, the network simplex algorithm demonstrates superior performance on sparse networks, often achieving speedups of 27 times or more compared to general solvers like CPLEX, due to its exploitation of tree-based basis structures for pivoting. This efficiency scales to 100-200 times faster than standard implementations for pure network problems, making it indispensable for large-scale, real-time optimization.

References

  1. https://documentation.sas.com/doc/en/ormpug/15.2/ormpug_optlp_details09.htm
  2. https://ocw.mit.edu/courses/15-082j-network-optimization-fall-2010/4f20b0870aa42b4272f8a7b33f27f5ab_MIT15_082JF10_lec16.pdf
  3. https://people.computing.clemson.edu/~jmarty/courses/commonCourseContent/common/OR-Intro/TextsAndMaterial/networkSimplexProblem.pdf
  4. https://www.scirp.org/reference/referencespapers?referenceid=1770623
  5. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.network_simplex.html
  6. https://link.springer.com/article/10.1007/BF02614365
  7. https://jeffe.cs.illinois.edu/teaching/algorithms/notes/G-mincostflow.pdf
  8. https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/netmethod/S1_pureflow.pdf
  9. https://dspace.mit.edu/bitstream/handle/1721.1/49424/networkflows00ahuj.pdf
  10. https://www.mit.edu/~dimitrib/LNets_Chapter%202.pdf
  11. https://people.orie.cornell.edu/miketodd/or630/lec18.pdf
  12. https://www.math.washington.edu/~perkins/381AWin12/handouts/chapter8.pdf
  13. https://dspace.mit.edu/bitstream/handle/1721.1/84610/15-053-spring-2007/contents/lecture-notes/lec15.pdf
  14. https://sites.ju.edu.jo/sites/Alzalg/Documents/973/pres%20NSM.pdf
  15. https://courses.grainger.illinois.edu/cs473/sp2017/notes/I-simplex.pdf
  16. https://people.ohio.edu/melkonia/math4620/chapter9.pdf
  17. https://dspace.mit.edu/bitstream/handle/1721.1/5266/OR-315-95.pdf?sequence=1
  18. https://upcommons.upc.edu/bitstream/handle/2117/191052/nf06_minimum_cost-4967.pdf
  19. https://coral.ise.lehigh.edu/~ted/files/ie411/lectures/Lecture20.pdf
  20. https://community.wvu.edu/~krsubramani/courses/su01/combopt/qen/netsim.pdf
  21. https://evokewonder.com/research/docs/geneqflow-ijoc-final.pdf
  22. https://theory.stanford.edu/~megiddo/pdf/wcongres_4.0.a.pdf
  23. https://pubsonline.informs.org/doi/10.1287/opre.40.1.S5
  24. https://doi.org/10.1007/BF02614369
  25. https://dspace.mit.edu/bitstream/handle/1721.1/2584/SWP-3834-33338649.pdf
  26. https://personal.math.ubc.ca/~anstee/math523/StronglyPolynomialNetworkFlow.pdf
  27. https://arxiv.org/abs/1207.6381
  28. https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf
  29. https://www.sciencedirect.com/science/article/abs/pii/S0377221716309493
  30. https://epubs.siam.org/doi/10.1137/0105003
  31. https://www.cs.princeton.edu/techreports/1988/164.pdf
  32. https://link.springer.com/article/10.1007/BF02614369
  33. https://web.stanford.edu/class/msande211x/Lecture062023.pdf
  34. https://www.sciencedirect.com/science/article/pii/0166218X9390054R
  35. https://repository.bilkent.edu.tr/bitstreams/1521a77e-58b7-400e-8b48-c58309120032/download
  36. https://personal.utdallas.edu/~metin/Or6201/network.pdf
  37. https://www.sciencedirect.com/science/article/abs/pii/S0377221710006594
  38. https://pdfs.semanticscholar.org/851c/fe88991c8483351022650f7dfc4782f37b0f.pdf
  39. https://iris.unica.it/retrieve/e2f56ed8-45b7-3eaf-e053-3a05fe0a5d97/Tesi_Davide_Cherubini.pdf
  40. https://supernet.isenberg.umass.edu/articles/seesehandbook.pdf
  41. https://stanford.edu/group/SOL/multiscale/papers/15MaSaunders.pdf
  42. https://www.protocols.io/view/introduction-to-flux-balance-analysis-fba-daz22f8e
Add your contribution
Related Hubs
User Avatar
No comments yet.