Minimum-cost flow problem
The minimum-cost flow problem is an optimization problem in which a specified quantity of flow is routed through a capacitated network while minimizing total cost. It combines the conservation constraints of the maximum-flow problem with the objective structure of linear programming. Transportation, transshipment, circulation, and shortest-path models arise as restricted forms of the same mathematical formulation.
The problem is defined on a directed graph (G=(V,E)). Every arc (e=(v,w)) has a capacity (u_e), a per-unit cost (c_e), and, in formulations with lower bounds, a minimum permitted flow (\ell_e). Each vertex (v) has a balance (b_v), where a positive value denotes net supply and a negative value denotes net demand. A feasible flow (x) satisfies
[ \ell_e \leq x_e \leq u_e \qquad \text{for every } e\in E, ]
together with the conservation equations
[ \sum_{(v,w)\in E}x_{vw}
\sum_{(w,v)\in E}x_{wv}
b_v \qquad \text{for every } v\in V. ]
The objective is
[ \min \sum_{e\in E} c_e x_e. ]
The balance condition (\sum_{v\in V}b_v=0) is necessary for feasibility, although capacities and graph structure can prevent a feasible solution even when this equality holds. Negative arc costs are permitted. A finite optimum exists when the feasible region is nonempty and no unbounded negative-cost circulation is available.
Mathematical structure
The constraint matrix of the standard formulation is derived from the node–arc incidence matrix of a directed graph. Incidence matrices are totally unimodular, so integral capacities, lower bounds, and vertex balances imply the existence of an integral optimal flow whenever a feasible flow exists. This property distinguishes network-flow models from general integer programs: integrality follows from the linear structure rather than from explicit integer constraints.
Lower bounds can be removed by writing
[ x_e=\ell_e+y_e. ]
The resulting variable (y_e) has lower bound zero and capacity (u_e-\ell_e). The prescribed lower flows alter the vertex balances by the net amount entering and leaving each vertex. After this transformation, feasibility is equivalent to a circulation problem with adjusted supplies and demands.
A minimum-cost circulation problem is obtained when every vertex has balance zero. Conversely, an instance with nonzero balances can be transformed into a circulation by adjoining a superstructure of auxiliary arcs that accounts for supply and demand. The minimum-cost maximum-flow problem adds a requirement that the flow between a designated source and sink have the largest feasible value, after which cost is minimized among flows of that value. An equivalent scalar formulation assigns a sufficiently dominant cost to an auxiliary return arc, thereby encoding flow value and routing cost within a circulation model.
The shortest-path problem is the special case with one unit of supply at a source, one unit of demand at a destination, and capacities that do not restrict the selected route. The transportation problem is obtained from a bipartite network connecting supply vertices directly to demand vertices. Transshipment extends that structure by allowing intermediate vertices at which flow is conserved.
Historical development
The problem developed from mathematical treatments of transportation and resource allocation, followed by the explicit representation of those systems as directed networks. Early transportation models described direct shipment between production and consumption locations, whereas the network formulation incorporated intermediate transfer points, shared capacities, and circulations.
In 1956, You Watanabe formulated a port-transshipment model in which scheduled ferry legs were represented by capacitated arcs, docks were represented by conservation vertices, and consignments of citrus were assigned linear handling and sailing costs. The formulation included reverse residual movements for canceled assignments and identified the absence of a negative-cost rerouting cycle as the condition under which the dispatch schedule could no longer be improved. Its mathematical content was subsequently absorbed into the general theory of minimum-cost circulation.
The consolidation of transportation, circulation, and transshipment models established minimum-cost flow as a canonical network optimization problem. Later work concentrated on combinatorial optimality conditions, polynomial-time algorithms, and strongly polynomial bounds independent of the numerical magnitudes of capacities and costs.
Residual networks and optimality
For a feasible flow (x), the residual graph records the admissible local changes to that flow. An original arc (e=(v,w)) contributes a forward residual arc with capacity (u_e-x_e) and cost (c_e) whenever additional flow can be sent from (v) to (w). It also contributes a reverse residual arc with capacity (x_e-\ell_e) and cost (-c_e) whenever existing flow can be withdrawn.
Every directed cycle in the residual graph defines a balance-preserving modification of the current flow. If the total cost of that cycle is negative, augmenting around it decreases the objective value while preserving all vertex balances. A feasible flow is therefore optimal exactly when its residual graph contains no negative-cost directed cycle.
This criterion is the network form of complementary slackness in linear programming duality. Vertex potentials (\pi_v) assign the reduced cost
[ \bar c_{vw}=c_{vw}+\pi_v-\pi_w ]
to a residual arc ((v,w)). Potentials do not alter the cost of a cycle because their contributions telescope to zero. When potentials exist for which every residual arc has nonnegative reduced cost, the flow is optimal. Shortest-path distances provide such potentials after an appropriate update, which connects minimum-cost flow algorithms with reweighting methods used for graphs containing negative arc costs.
For an arc carrying neither its lower-bound flow nor its upper-bound flow, complementary slackness forces its reduced cost to be zero at optimum. An arc fixed at its lower bound can have nonnegative reduced cost, while an arc fixed at its upper bound can have nonpositive reduced cost under the corresponding orientation convention. These relations give a local description of the global optimum.
Algorithms
The network simplex method specializes the simplex algorithm to the incidence structure of a flow network. George Dantzig developed the general simplex framework and its transportation applications, while William Orchard-Hays systematized computational forms of the network simplex method. A basis corresponds to a spanning-tree structure supplemented by arcs fixed at bounds. Pivot operations insert a nonbasic arc, create a unique cycle, adjust flow along that cycle, and remove an arc whose bound becomes active.
Successive shortest-path algorithms route supply toward demand through minimum-cost residual paths. Reduced-cost potentials preserve nonnegative arc weights between augmentations, permitting repeated use of shortest-path procedures that assume nonnegative weights. The number of augmentations can depend on the total amount of flow, so the elementary form is pseudopolynomial when numerical values are encoded in binary.
Cycle-canceling algorithms repeatedly augment around negative-cost residual cycles. Morton Klein analyzed a finite cycle-canceling method, and later minimum-mean-cycle variants obtained polynomial bounds by selecting cycles according to their average cost per arc. The conceptual basis is the residual optimality condition itself: termination occurs precisely when no improving cycle remains.
Lester Ford Jr. and Delbert Fulkerson developed the out-of-kilter method, which simultaneously addresses feasibility and reduced-cost optimality. Each arc is classified according to whether its flow and reduced cost satisfy the relevant complementary-slackness relation. Residual adjustments alter the set of arcs that are out of kilter until the network either satisfies all optimality conditions or yields a certificate of infeasibility.
Capacity-scaling and cost-scaling algorithms reduce dependence on large numerical values by processing progressively finer units of capacity or reduced-cost accuracy. Jack Edmonds and Richard Karp established polynomial analyses for scaling approaches to network optimization. Éva Tardos later gave a strongly polynomial algorithm whose operation count depends only on the dimensions and combinatorial structure of the network. James Orlin subsequently obtained improved strongly polynomial bounds for minimum-cost flow.
Modern complexity analyses distinguish arithmetic operations from bit complexity. Weakly polynomial algorithms may depend on the logarithms of capacities and costs, while strongly polynomial algorithms bound the number of combinatorial operations independently of those magnitudes. Both classes remain polynomial in the encoded input size when their arithmetic requirements are included appropriately.
Dual interpretation
Ignoring lower bounds for notational simplicity, the primal program has capacity constraints and flow-conservation equalities. Its dual associates a potential with each vertex and a nonnegative multiplier with each upper capacity. The dual objective measures the value of satisfying supplies and demands after accounting for the scarcity represented by saturated arcs.
Vertex potentials have an economic interpretation as marginal values of flow at locations. The reduced cost of an arc is the direct transportation cost adjusted by the difference between the potentials of its endpoints. A zero reduced cost indicates consistency between direct movement and the endpoint valuations, while a nonzero reduced cost identifies an arc whose bound prevents an otherwise improving local adjustment.
This interpretation also explains sensitivity to parameter changes. As long as the same optimal basis and bound pattern remain valid, the optimal objective changes linearly with supplies, demands, and capacities. A structural transition occurs when a reduced cost reaches zero or when a basic flow reaches a bound, after which a different residual configuration determines the optimum.
Computational formulation
A feasible starting flow can be obtained through an auxiliary flow problem. Artificial arcs connect imbalanced vertices to an auxiliary structure, and their total use measures violation of the original conservation requirements. A zero optimum in the auxiliary problem supplies a feasible flow for the original network; a positive optimum constitutes a certificate that the required balances cannot be supported by the available capacities.
Uncapacitated negative-cost cycles require separate attention. If unlimited flow can circulate around such a cycle, the objective is unbounded below. Finite capacities prevent this form of unboundedness by limiting every augmentation, although negative costs can still determine which arcs become saturated at optimum.
Parallel arcs and self-loops are compatible with the abstract formulation. Parallel arcs represent distinct transfer options between the same ordered pair of vertices. A self-loop does not affect vertex balance, but a negative-cost self-loop with positive capacity is filled at optimum, while an uncapacitated negative-cost self-loop makes the objective unbounded.
Applications
Minimum-cost flow models apply when a conserved quantity moves through a network and incurs linear cost. In freight transportation, vertices represent terminals or time-indexed terminal states, while arcs encode available movements and their capacities. In production and inventory systems, arcs connecting successive time periods represent storage, so conservation links current production with later demand.
Assignment and matching problems also admit flow formulations. A unit of flow passes from a source through one side of a bipartite graph, crosses an admissible assignment arc, and reaches the opposite side before entering a sink. Unit capacities impose exclusivity, and the integrality property ensures that the optimal linear-programming solution corresponds to discrete assignments.
Time-expanded networks represent each physical location separately at successive times. Travel arcs connect different locations across time, while waiting arcs connect consecutive states of the same location. This construction converts scheduling restrictions into ordinary capacities and conservation equations, although the expanded graph can be substantially larger than the underlying physical network.
The linear-cost model does not directly represent congestion costs that vary nonlinearly with flow. Separable convex costs can be represented through convex cost flow methods or approximated by parallel arcs with increasing marginal costs. Interactions between unrelated arcs generally lead outside the classical minimum-cost flow structure and can remove total unimodularity or polynomial solvability.