Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Minimum-cost flow problem.
Nothing was collected or created yet.
Minimum-cost flow problem
View on Wikipediafrom Wikipedia
The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.
Definition
[edit]A flow network is a directed graph with a source vertex and a sink vertex , where each edge has capacity , flow and cost , with most minimum-cost flow algorithms supporting edges with negative costs. The cost of sending this flow along an edge is . The problem requires an amount of flow to be sent from source to sink .
The definition of the problem is to minimize the total cost of the flow over all edges:
with the constraints
Capacity constraints: Skew symmetry: Flow conservation: Required flow:
Relation to other problems
[edit]A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximum flow solutions. This could be called a minimum-cost maximum-flow problem and is useful for finding minimum cost maximum matchings.
With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, one can find the maximum flow by performing a binary search on .
A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. The minimum cost circulation problem has no source and sink; instead it has costs and lower and upper bounds on each edge, and seeks flow amounts within the given bounds that balance the flow at each vertex and minimize the sum over edges of cost times flow. Any minimum-cost flow instance can be converted into a minimum cost circulation instance by setting the lower bound on all edges to zero, and then making an extra edge from the sink to the source , with capacity and lower bound , forcing the total flow from to to also be .
The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn):[1]
- Shortest path problem (single-source). Require that a feasible solution to the minimum cost flow problem sends one unit of flow from a designated source to a designated sink . Give all edges infinite capacity.
- Maximum flow problem. Choose a large demand (large enough to exceed the maximum flow; for instance, the sum of capacities out of the source vertex) Set the costs of all edges in the maximum flow instance to zero, and introduce a new edge from source to sink with unit cost and capacity .
- Assignment problem. Suppose that each partite set in the bipartition has vertices, and denote the bipartition by . Give each supply and give each demand . Each edge is to have unit capacity.
Solutions
[edit]The minimum cost flow problem can be solved by linear programming, since we optimize a linear function, and all constraints are linear.
Apart from that, many combinatorial algorithms exist.[1] Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.
Well-known fundamental algorithms (they have many variations):
- Cycle canceling: a general primal method.[2]
- Cut canceling: a general dual method.[3][4]
- Minimum mean cycle canceling: a simple strongly polynomial algorithm.[5]
- Successive shortest path and capacity scaling: dual methods, which can be viewed as the generalization of the Ford–Fulkerson algorithm.[6]
- Cost scaling: a primal-dual approach, which can be viewed as the generalization of the push-relabel algorithm.[7]
- Network simplex algorithm: a specialized version of the linear programming simplex method.[8]
- Out-of-kilter algorithm by D. R. Fulkerson
Cycle canceling algorithms
[edit]These algorithms are iterative and like the Ford–Fulkerson algorithm they define a residual graph. If there is flow on arc , then its residual capacity is defined to be and its residual cost is . The reverse arc (which has negative flow value) has a negative cost . The algorithms then start with an arbitrary feasible flow and iteratively improve the cost of the solution by pushing flow around negative-cost cycles. In the Minimum mean cycle canceling, the algorithm selects a cycle that has minimum mean cost (the ratio of the total cycle cost to the number of arcs). Such a cycle can be found in polynomial time (by binary search using the Bellman-Ford algorithm) and the total number of iterations has been proven to be polynomial[5].
Application
[edit]Minimum weight bipartite matching
[edit]
Given a bipartite graph G = (A ∪ B, E), the goal is to find the maximum cardinality matching in G that has minimum cost. Let w: E → R be a weight function on the edges of E. The minimum weight bipartite matching problem or assignment problem is to find a perfect matching M ⊆ E whose total weight is minimized. The idea is to reduce this problem to a network flow problem.
Let G′ = (V′ = A ∪ B, E′ = E). Assign the capacity of all the edges in E′ to 1. Add a source vertex s and connect it to all the vertices in A′ and add a sink vertex t and connect all vertices inside group B′ to this vertex. The capacity of all the new edges is 1 and their costs is 0. It is proved that there is minimum weight perfect bipartite matching in G if and only if there a minimum cost flow in G′.[1]
See also
[edit]References
[edit]- ^ a b c Ravindra K. Ahuja; Thomas L. Magnanti & James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
- ^ Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science. 14 (3): 205–220. CiteSeerX 10.1.1.228.7696. doi:10.1287/mnsc.14.3.205.
- ^ Refael Hassin (1983). "The minimum cost flow problem: A unifying approach to existing algorithms and a new tree search algorithm". Mathematical Programming. 25: 228–239. doi:10.1007/bf02591772.
- ^ Thomas R. Ervolina & S. Thomas McCormick (1993). "Two strongly polynomial cut cancelling algorithms for minimum cost network flow". Discrete Applied Mathematics. 4 (2): 133–165. doi:10.1016/0166-218x(93)90025-j.
- ^ a b Andrew V. Goldberg & Robert E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM. 36 (4): 873–886. doi:10.1145/76359.76368.
- ^ Jack Edmonds & Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699.
- ^ Goldberg, Andrew V. & Tarjan, Robert E. (1990). "Finding minimum-cost circulations by successive approximation". Mathematics of Operations Research. 15 (3): 430–466. doi:10.1287/moor.15.3.430.
- ^ James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming. 78 (2): 109–129. doi:10.1007/bf02614365. hdl:1721.1/2584.
External links
[edit]Minimum-cost flow problem
View on Grokipediafrom Grokipedia
Mathematical Formulation
Network Model
The minimum-cost flow problem is formulated on a directed graph , where is the finite set of vertices representing nodes and is the set of directed arcs connecting pairs of nodes.[7] Each node may represent a supply point, demand point, or transshipment point, while each arc models a possible pathway for flow transmission between nodes.[7] This graph-theoretic structure captures the topological and directional constraints inherent in flow networks, such as transportation or communication systems.[8] For each arc , the model specifies a lower bound on the flow amount, an upper bound or capacity limiting the maximum flow, and a cost representing the expense per unit of flow along that arc.[7] These parameters ensure that flows respect physical or operational limits, such as pipeline capacities or budget constraints, while the costs quantify the economic or resource implications of routing flow through specific paths.[1] Lower bounds are often zero in basic formulations but allow for mandatory minimum flows in more general cases.[7] Each node is associated with a supply/demand value , where indicates net supply available at , denotes net demand to be satisfied at , and signifies a transshipment node with no net inflow or outflow requirement.[7] For the problem to be feasible, the total supply must equal the total demand across all nodes, i.e., .[7] This conservation condition ensures that the network can be balanced without excess or deficit accumulation.[9] A simple illustrative network might consist of four nodes: sources and with , ; sinks and with , ; and a transshipment node with . Arcs could include with capacity 5 and cost 2, with capacity 3 and cost 1, with capacity 4 and cost 3, and with capacity 4 and cost 1, demonstrating how flows originate at sources, route through intermediate nodes, and terminate at sinks.[2] Such a diagram highlights the directional flow from supplies to demands via interconnected arcs.[1] Networks are classified as balanced if , allowing direct feasibility, or unbalanced otherwise, where the imbalance implies infeasibility without modification.[7] To address imbalance, a common technique introduces a dummy node connected by additional arcs to absorb the excess supply or fulfill the unmet demand, effectively restoring balance while adjusting capacities and costs accordingly.[7] For instance, if total supply exceeds demand, arcs from the dummy node to excess supply nodes can be added with infinite capacity and zero cost.[9]Objective Function and Constraints
The minimum-cost flow problem is defined on a directed graph with nodes and arcs , where each arc has a cost , lower bound , and upper bound on the flow it can carry, and each node has a supply/demand .[10] The goal is to determine a feasible flow that minimizes the total transportation cost while respecting arc capacities and nodal requirements.[10] The objective function is to minimize the total cost: This linear objective captures the aggregate cost of sending flow along each arc at unit cost .[10] The constraints consist of capacity bounds and flow balance equations. For each arc , ensuring that the flow on every arc lies within its specified limits; typically, and flows are non-negative, though general lower bounds allow for bidirectional or required flows.[10] For each node , where is the set of arcs leaving and is the set entering ; here, indicates net supply at , indicates net demand (with as the demand amount), and for transshipment nodes.[10] Together, these form the complete linear programming formulation: [10] A feasible solution to this program requires that the total supply equals the total demand across all nodes, i.e., ; this balance condition is necessary for the existence of any flow satisfying the conservation equations, as it ensures no net imbalance in the network.[11] Without this, the problem is infeasible, as excess supply or unmet demand cannot be resolved within the given structure.[10] The flow conservation constraints derive from the mass balance principle in network flows, analogous to the steady-state conservation of mass in physical systems: for any node , the net inflow must equal the external supply or demand , preventing accumulation or depletion at intermediate points and ensuring that flow is preserved along paths from sources to sinks.[10] This principle translates directly into the balance equation, where positive represents injection of flow (outflow exceeds inflow by ) and negative represents extraction (inflow exceeds outflow by ).[11]Connections to Other Problems
Relation to Maximum Flow
The minimum-cost flow problem generalizes the maximum flow problem by extending the objective beyond merely maximizing the net flow from a source to a sink; instead, it seeks to satisfy supply and demand constraints while minimizing the total transportation cost across capacitated edges.[1] In this framework, the maximum flow problem emerges as a special case when all edge costs are set to zero, reducing the optimization to finding the largest feasible flow value without regard to cost.[12] This relationship highlights how minimum-cost flow incorporates cost minimization as a natural extension, allowing for more nuanced modeling of real-world networks where efficiency in resource allocation involves both capacity and expense.[13] When demands are fixed—such as requiring exactly units of flow from source to sink—and all edge costs are uniform (e.g., zero or constant), the minimum-cost flow problem simplifies to verifying feasibility or achieving the maximum possible flow under those constraints, effectively reverting to the maximum flow formulation.[14] The core algorithmic insight connecting the two lies in the augmenting path concept: the Ford-Fulkerson method for maximum flow iteratively augments along any residual path to increase total flow, whereas minimum-cost flow adapts this by selecting the cheapest augmenting path in the residual graph with respect to edge costs, ensuring cost efficiency at each step.[1] This cost-aware variant preserves the augmenting structure while optimizing the objective, enabling algorithms like successive shortest paths to solve minimum-cost instances.[9] Historically, the Ford-Fulkerson algorithm, published in 1956, provided the foundational augmenting path paradigm that directly influenced subsequent developments in minimum-cost flow algorithms, which build upon it to handle costs. For instance, a maximum flow instance can be transformed into a minimum-cost flow problem by setting the supply at the source node to and the demand at the sink to (where is the target flow value), with all edge costs at zero; the resulting solution achieves the desired flow at minimal (zero) cost if feasible, or reveals infeasibility otherwise.[14] This reduction demonstrates the versatility of minimum-cost flow as a unifying framework for flow-based optimizations.[15]Relation to Minimum-Cost Circulation
The minimum-cost circulation problem is a special case of the minimum-cost flow problem where the supply/demand function for all nodes , requiring the identification of a feasible circulation —a flow that conserves flow at every node and respects arc capacities—that minimizes the total cost .[16][1] Any instance of the minimum-cost flow problem can be transformed into an equivalent minimum-cost circulation problem by introducing additional arcs to balance the supplies and demands; specifically, add a super-source connected to all nodes with positive supply via arcs of capacity equal to the supply and cost zero, and a super-sink connected from all nodes with negative demand (i.e., positive demand) via arcs of capacity equal to the absolute demand and cost zero, ensuring the overall network admits a circulation that satisfies the original balances.[17] This equivalence preserves the optimal cost and allows algorithms for one problem to solve the other, with the circulation formulation often simplifying analysis in balanced networks.[17] In both formulations, optimality relies on the residual network , constructed from a feasible flow by including forward arcs with residual capacity at cost and backward arcs with capacity at cost ; a flow is optimal if and only if contains no negative-cost directed cycles, as augmenting along such a cycle would reduce the total cost while maintaining feasibility.[18][19] For the circulation problem, these conditions align with the Karush-Kuhn-Tucker (KKT) optimality criteria of the associated linear program, where dual multipliers (node potentials) ensure complementary slackness: for each arc , the reduced cost if , if , and equality holds when the arc is partially used, with no negative reduced-cost cycles in the residual graph.[20][21] As an illustrative example, consider a minimum-cost flow instance with a single source supplying value and sink demanding ; this can be converted to a circulation by adding a return arc from to with lower and upper capacity and cost 0, forcing exactly units to circulate back and ensuring the minimum-cost solution matches the original flow.[22][17]Algorithms
Successive Shortest Path Algorithm
The successive shortest path algorithm is a primal algorithm for solving the minimum-cost flow problem in capacitated networks with supplies and demands. It initializes the flow to zero (or any feasible pseudoflow) and repeatedly identifies a shortest path in the residual graph from a node with excess supply to a node with excess demand, using reduced costs to account for node potentials, then augments the flow along this path by the minimum residual capacity or unmet demand until all supplies and demands are balanced.[1] This approach ensures that each augmentation increases the total flow while maintaining minimum cost at each step, leveraging the fact that the residual graph encodes possible flow adjustments. The algorithm was originally proposed by Ford and Fulkerson in the mid-1950s and independently rediscovered by Jewell in 1958.[1][23] To implement the algorithm efficiently, node potentials are maintained for each vertex , initially set to zero or computed as shortest-path distances in the initial residual graph. These potentials transform the original arc costs into reduced costs , ensuring non-negative reduced costs in the residual graph and allowing the use of Dijkstra's algorithm for shortest-path computations after the first iteration.[1] After each augmentation, the potentials are updated by adding the shortest-path distances from the current computation to the existing potentials, preserving non-negativity. The following pseudocode outlines the process, assuming a network with vertex supplies/demands (positive for supply, negative for demand), capacities , and costs ; tracks the total unmet demand:SuccessiveShortestPath(G = (V, A), b, c, u):
f(e) ← 0 for all e ∈ A // Initialize zero flow
π(v) ← 0 for all v ∈ [V](/page/V.) // Initialize node potentials
B ← ∑_{v: b(v)>0} b(v) // Total supply to satisfy
while B > 0:
Construct residual graph G_f with reduced costs c_π
Let s be a supply node with positive residual supply
Let t be a demand node with positive residual demand
Compute shortest path P from s to t in G_f using c_π (via Bellman-Ford or Dijkstra)
if no such path exists: return "Infeasible"
δ ← min{ residual capacity along P, residual supply at s, residual demand at t }
Augment f along P by δ
Update B ← B - δ
Update potentials: π(v) ← π(v) + dist_π(s, v) for all v
return f
SuccessiveShortestPath(G = (V, A), b, c, u):
f(e) ← 0 for all e ∈ A // Initialize zero flow
π(v) ← 0 for all v ∈ [V](/page/V.) // Initialize node potentials
B ← ∑_{v: b(v)>0} b(v) // Total supply to satisfy
while B > 0:
Construct residual graph G_f with reduced costs c_π
Let s be a supply node with positive residual supply
Let t be a demand node with positive residual demand
Compute shortest path P from s to t in G_f using c_π (via Bellman-Ford or Dijkstra)
if no such path exists: return "Infeasible"
δ ← min{ residual capacity along P, residual supply at s, residual demand at t }
Augment f along P by δ
Update B ← B - δ
Update potentials: π(v) ← π(v) + dist_π(s, v) for all v
return f
Cycle Canceling Algorithms
Cycle canceling algorithms solve the minimum-cost flow problem by starting with a feasible flow and iteratively improving it until optimality is reached. These methods maintain feasibility throughout the process, unlike primal-dual approaches that may temporarily violate constraints. The core idea is to identify and augment flow along negative-cost cycles in the residual graph, which reduces the total cost without altering the net flow at nodes.[24] To initiate the algorithm, an initial feasible flow is computed, often by solving a maximum flow problem on the network while ignoring costs, ensuring the flow satisfies capacity and conservation constraints.[1] Then, while a negative-cost cycle exists in the residual graph, the algorithm detects it and augments the flow along the cycle by the minimum residual capacity on that cycle, thereby decreasing the total cost. Cycle detection typically employs the Bellman-Ford algorithm applied to the reduced costs in the residual graph, where reduced costs are defined using node potentials to preserve cycle costs while potentially eliminating negative edges.[25] The process terminates when no negative-cost cycles remain, at which point the flow is optimal because any further improvement would require augmenting along a negative cycle, which does not exist.[24] Klein's algorithm, introduced in 1967, is the seminal cycle canceling method, which guarantees convergence but may require exponentially many iterations in the worst case.[24] Polynomial-time variants address this limitation; for instance, the minimum mean cycle canceling algorithm selects the cycle with the smallest mean cost (total cost divided by the number of edges) at each step, ensuring the number of iterations is bounded by a polynomial in the number of nodes and edges. This variant, developed by Goldberg and Tarjan in 1989, runs in strongly polynomial time using an efficient implementation of minimum mean cycle detection.[25]Example
Consider a simple network with three nodes , , and , and directed edges with capacity 5 and cost 2, with capacity 5 and cost 3, and with capacity 5 and cost -6. Suppose the initial feasible flow is zero everywhere, satisfying conservation for a circulation problem. In the residual graph, the cycle has total cost and minimum residual capacity 5.| Edge | Capacity | Cost | Initial Flow |
|---|---|---|---|
| 5 | 2 | 0 | |
| 5 | 3 | 0 | |
| 5 | -6 | 0 |
Capacity Scaling Algorithms
Capacity scaling algorithms address the minimum-cost flow problem by decomposing the solution process into phases that progressively refine the flow using a scaling parameter , which starts at the largest power of 2 not exceeding the maximum arc capacity and is halved in each subsequent phase. This approach, introduced by Ahuja and Orlin, ensures a logarithmic number of phases, where is the maximum capacity, making the method efficient for networks with large capacities. In each phase, the algorithm computes an -optimal flow for a scaled subproblem, where and is the maximum arc cost, by performing successive shortest path augmentations in the residual graph using reduced costs to account for current flow potentials. Augmentations are restricted to residual arcs with capacity at least , and shortest paths are efficiently computed via Dijkstra's algorithm with node potentials to maintain non-negative reduced costs. The integration of these shortest path steps, potentially augmented by cycle canceling to resolve residual imbalances, guarantees progress toward optimality while preserving polynomial time per phase. For instances with unit arc costs, the Ahuja-Orlin algorithm achieves a time complexity of , where is the number of arcs and is the number of vertices; this bound is strongly polynomial, independent of capacity and cost magnitudes. Lower bounds on arc flows are handled via circulation reduction, transforming the original problem into an equivalent minimum-cost circulation by first computing a feasible circulation in a modified network, often using a maximum flow subroutine, before applying the scaling phases. These algorithms outperform non-scaling approaches on large-scale instances with substantial capacities, as the logarithmic dependence on avoids the potentially exponential iterations tied to total flow value in methods like basic successive shortest paths.Applications
Transportation and Transshipment Problems
The transportation problem is a classic application of the minimum-cost flow problem, modeling the distribution of goods from multiple suppliers to multiple demanders while minimizing total shipping costs. In this setup, the network is represented as a bipartite directed graph, with supplier nodes serving as sources and demander nodes as sinks. Arcs connect each supplier to each demander, each with an associated unit transportation cost and capacity limit (often unbounded in the basic formulation). The goal is to determine shipment quantities along these arcs that satisfy all supply and demand requirements at minimum cost.[2] The transshipment problem extends the transportation problem by incorporating intermediate nodes, such as distribution hubs or transshipment points, allowing flows to route through these nodes before reaching final demanders. These intermediate nodes have no net supply or demand, enabling more flexible logistics networks that reflect real-world supply chains with consolidation or rerouting. The graph structure includes arcs from suppliers to intermediates, between intermediates, and from intermediates to demanders, all with respective costs and capacities. This generalization maintains the core minimum-cost flow structure while accommodating multi-stage distribution.[14] Within the minimum-cost flow framework, both problems are formulated by assigning node balances : for each supplier with supply , for each demander with demand , and for any transshipment nodes, ensuring total supply equals total demand (). Flows on arcs must satisfy conservation at each node and capacity bounds, with the objective to minimize over arc costs and flows .[6] The transportation problem was first formally introduced by Hitchcock in 1941 as a method for optimal product distribution across multiple sources and localities. Subsequently, Dantzig in 1951 adapted the simplex method specifically for solving transportation problems, demonstrating its efficiency for large-scale instances and influencing early computational approaches in operations research.[26] Consider a representative transportation problem with two suppliers (S1 with supply 300 units, S2 with supply 400 units) and three demanders (D1 requiring 200 units, D2 requiring 300 units, D3 requiring 200 units). The unit shipping costs are given in the following table:| D1 | D2 | D3 | |
|---|---|---|---|
| S1 | 4 | 3 | 5 |
| S2 | 6 | 2 | 3 |
Bipartite Matching and Assignment Problems
The minimum-weight perfect matching problem in a bipartite graph arises in scenarios where entities from two disjoint sets must be paired optimally based on associated costs. Consider a bipartite graph with partitions and , and directed arcs from each to each with costs . A perfect matching assigns each to exactly one such that no two assignments share a vertex, minimizing the total cost over permutations .[7] This problem, known as the assignment problem when , can be solved as a minimum-cost flow problem by constructing a flow network on the bipartite graph. Set the capacity of each arc to and lower bound , with costs unchanged. Assign node supplies and demands such that (supply of 1) for each and (demand of 1) for each , with for all other nodes (if any). The minimum-cost flow of value then corresponds to a minimum-weight perfect matching, as the unit capacities enforce at most one unit of flow per arc, and the supplies/demands ensure each vertex is incident to exactly one unit of flow.[7] An equivalent formulation adds a source and sink : connect to each with capacity 1 and cost 0, and each to with capacity 1 and cost 0. Set supply and demand , with all other nodes balanced at 0. The minimum-cost flow from to of value yields the same optimal assignment. This unit-capacity structure distinguishes the assignment problem from more general transportation problems, which allow higher capacities on arcs.[7] The Kuhn-Munkres algorithm, also known as the Hungarian algorithm, provides a specialized primal-dual method for solving the assignment problem in time, which can be interpreted as optimizing the dual of the corresponding minimum-cost flow linear program on the bipartite network.[28][29] While the Hungarian algorithm operates directly on the cost matrix via augmenting paths and potential adjustments, minimum-cost flow algorithms like successive shortest paths can solve the same instance by finding augmenting paths in the residual network, offering a unified framework for generalizations beyond unit capacities.[7] Illustrative ExampleConsider assigning three jobs to three machines with the following cost matrix, where entries represent the cost of assigning job to machine :
| Job \ Machine | X | Y | Z |
|---|---|---|---|
| A | 19 | 28 | 31 |
| B | 11 | 17 | 16 |
| C | 12 | 15 | 13 |
Economic Interpretations
The minimum-cost flow problem finds natural economic interpretations in settings where resources must be allocated across interconnected stages or agents to minimize total expenses while satisfying supply and demand constraints. In this framework, nodes represent economic entities such as production stages, markets, or facilities, while arcs denote transformation processes, transportation routes, or transactions, each with associated unit costs and capacities. The dual formulation provides particularly insightful economic meaning: node potentials act as prices or shadow values for commodities at each location, and reduced costs on arcs reflect net profits or losses from routing one unit of flow from origin to destination after accounting for buy-sell price differences.[31][32] In production planning, the minimum-cost flow model captures multi-stage manufacturing or inventory management by modeling nodes as temporal or sequential phases—from raw materials to finished goods—and arcs as production processes or storage options with associated costs. For instance, in seasonal goods production like ice cream, nodes correspond to periods (e.g., quarters), arcs from a source to each period represent production with costs based on variable expenses and capacities limited by facility output, while inter-period arcs model inventory carryover with holding costs and warehouse limits; demand arcs to a sink enforce sales requirements, ensuring minimal total production and storage expenses. This setup optimizes resource timing and allocation, preventing shortages or excess buildup.[33][32] Arbitrage detection in financial networks leverages the model's sensitivity to negative cycles, where such cycles signal profitable, riskless opportunities by indicating paths where the total reduced cost is negative, allowing unlimited gains through repeated transactions like currency exchanges or security trades. In a circulation-based network, nodes represent assets or markets, and arcs denote trades with costs as negative returns (e.g., interest rate differentials); solving for minimum-cost circulation identifies these cycles, quantifying exploitable deviations from equilibrium, such as covered interest parity violations in foreign exchange markets. At optimality, the absence of negative cycles ensures no further arbitrage exists, aligning flows with market efficiency.[32][34] Extensions to multi-commodity flows adapt the single-commodity model for scenarios involving distinct goods sharing network capacities, such as diverse products in supply chains, but retain the core economic focus on cost minimization under shared constraints.[35] A practical application appears in airline crew scheduling, where the problem minimizes operational costs by assigning crews to flight legs as flows through a time-space network: nodes are duty periods or airports, arcs connect feasible pairings with costs for salaries, per diems, and overtime, subject to coverage demands and regulatory limits on hours.[36] Policy implications arise from shadow prices, interpreted as the dual variables on supply-demand constraints, which quantify the marginal economic value or cost of adjusting resource availability at each node—guiding decisions on subsidies, taxes, or capacity investments by revealing how small changes in balances affect total system costs.[31][32]Implementation Considerations
Complexity Analysis
The successive shortest path algorithm for the minimum-cost flow problem has a worst-case time complexity of , where is the number of vertices, is the number of arcs, and is the maximum arc cost magnitude; this bound assumes the use of reduced costs, node potentials to ensure non-negative reduced costs, and Dijkstra's algorithm implemented with Fibonacci heaps for finding augmenting paths.[7] Scaling variants of this algorithm, such as capacity scaling combined with successive shortest paths, achieve improved bounds like under general capacities, by processing phases that halve the residual capacities iteratively and augmenting along multiple paths in parallel where possible.[7] Strongly polynomial algorithms, which run in time polynomial in the input size regardless of the magnitudes of costs or capacities, represent a key advancement for the minimum-cost flow problem. The Goldberg-Tarjan algorithm from 1988, based on a push-relabel framework with node potentials and cost scaling, achieves a time complexity of for finding a minimum-cost circulation, which can be adapted to the general flow problem; this bound relies on dynamic tree data structures for efficient shortest-path computations in the residual graph.[37] More recent progress includes Orlin's 1993 algorithm, which solves the minimum-cost flow problem in time, offering a simpler and faster strongly polynomial solution through a refinement of the Edmonds-Karp capacity scaling technique that avoids dependence on cost magnitudes.[38] Even more recent theoretical advancements, as of 2022–2023, have introduced almost-linear time algorithms for minimum-cost flow on directed graphs with polynomially bounded integral demands and costs, achieving running times of , where . These algorithms, such as those by Chen et al. (2023), use interior-point methods combined with dynamic data structures for solving sequences of undirected min-ratio cycle problems. While highly efficient in theory, partial implementations were available as of 2024, but full practical integrations into standard libraries remain under development.[39][40] The following table compares the time complexities of major minimum-cost flow algorithms under different assumptions:| Algorithm | General Capacities | Unit Capacities |
|---|---|---|
| Successive Shortest Path | $O( | V |
| Capacity Scaling | $O( | A |
| Goldberg-Tarjan Cost Scaling | $O( | V |
| Orlin's Algorithm | $O( | A |
Practical Software Tools
Several open-source libraries provide implementations for solving minimum-cost flow problems, enabling researchers and practitioners to model and compute solutions efficiently in various programming environments. NetworkX, a Python library for graph analysis, includes themin_cost_flow function, which computes a minimum-cost flow satisfying node demands while respecting edge capacities and costs using successive shortest path algorithms.[42] Similarly, the LEMON graph template library in C++ offers high-performance algorithms for minimum-cost flows, including cost-scaling and network simplex methods, optimized for large-scale networks through efficient data structures and sparse representations.[43]
Commercial solvers integrate minimum-cost flow capabilities as specialized subroutines within broader linear programming frameworks, often outperforming general-purpose methods on network-structured problems. Gurobi Optimizer supports minimum-cost flow modeling via its Python interface, leveraging barrier and simplex algorithms with automatic detection of network structures for faster solves.[44] IBM CPLEX provides a dedicated network optimizer in its callable library, which exploits flow conservation constraints to reduce problem size and accelerate solutions using primal-dual simplex variants.[45]
For practical usage, Google's OR-Tools library offers an accessible Python interface with the SimpleMinCostFlow class, suitable for prototyping small to medium networks. The following code snippet demonstrates solving a basic minimum-cost flow problem with five nodes and nine arcs, where node 0 supplies 20 units, node 3 demands 5 units, and node 4 demands 15 units:
python
from ortools.graph import pywrapgraph
smcf = pywrapgraph.SimpleMinCostFlow()
# Define arcs: start_nodes, end_nodes, capacities, unit_costs
start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]
for i in range(len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i],
capacities[i], unit_costs[i])
# Set supplies/demands
supplies = [20, 0, 0, -5, -15]
for i in range(len(supplies)):
smcf.set_node_supply(i, supplies[i])
if smcf.solve() == smcf.OPTIMAL:
print('Minimum cost:', smcf.optimal_cost())
for arc in range(smcf.num_arcs()):
print('Flow:', smcf.flow(arc), 'on arc', smcf.tail(arc), '->',
smcf.head(arc), 'with capacity', smcf.capacity(arc),
'and unit cost', smcf.unit_cost(arc))
from ortools.graph import pywrapgraph
smcf = pywrapgraph.SimpleMinCostFlow()
# Define arcs: start_nodes, end_nodes, capacities, unit_costs
start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]
for i in range(len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(start_nodes[i], end_nodes[i],
capacities[i], unit_costs[i])
# Set supplies/demands
supplies = [20, 0, 0, -5, -15]
for i in range(len(supplies)):
smcf.set_node_supply(i, supplies[i])
if smcf.solve() == smcf.OPTIMAL:
print('Minimum cost:', smcf.optimal_cost())
for arc in range(smcf.num_arcs()):
print('Flow:', smcf.flow(arc), 'on arc', smcf.tail(arc), '->',
smcf.head(arc), 'with capacity', smcf.capacity(arc),
'and unit cost', smcf.unit_cost(arc))