MinCostFlow

Minimum cost flow problem (Min-Cost Flow) is a fundamental optimization problem in network flow theory. Given a directed graph with edge capacities and per-unit costs, and a set of node supplies and/or demands, the objective is to push flow through the network so that all capacity constraints are respected and the net production/consumption at every node is satisfied while the total cost of the flow is minimized.

Formally, each edge e has a capacity u_e and a cost c_e per unit of flow. A feasible flow f must satisfy 0 ≤ f_e ≤ u_e for all edges and, for each node v, the flow conservation condition that the net outflow equals the node’s supply b_v (positive for supply, negative for demand). The problem requires that the total supply equals the total demand (sum b_v = 0) and seeks to minimize the objective sum_e f_e c_e.

Common approaches include the successive shortest augmenting path method, often implemented with Dijkstra’s algorithm and node potentials to handle negative costs, yielding a time complexity roughly proportional to the total flow times the cost of a shortest path. Other methods are the cycle-canceling algorithm, the primal-dual (network simplex) method, and cost-scaling techniques. Variants handle lower bounds on edges, negative costs with no negative-cost cycles, and conversions to a min-cost circulation problem using super sources or sinks.

Min-cost flow generalizes several classic problems, including the max-flow problem, the transportation problem, and the assignment problem. Applications span logistics, production planning, energy and telecommunications networks, and economic modeling, where one seeks cheapest feasible transport of units subject to capacity and demand constraints.