MCMF

Minimum-cost maximum-flow (MCMF) is a class of optimization problems in network flow theory that seek to send as much flow as possible from a designated source to a designated sink while minimizing the total cost of the transported flow. Each edge in the network has a capacity limiting how much flow can pass through it and a cost per unit of flow; the total cost is the sum over edges of the flow on the edge multiplied by its cost.

Mathematically, given a directed graph G = (V, E) with edge capacities c: E → R+ and edge costs w: E → R, a feasible flow f : E → R+ satisfies 0 ≤ f_e ≤ c_e for all edges e and flow conservation at all vertices except the source s and sink t. The objective is to maximize the value of the s–t flow |f|, or, equivalently, to minimize the total cost of the s–t flow among all maximum flows. In many formulations, a fixed required amount of flow is specified and the goal is to find the cheapest way to achieve it.

Computationally, a common approach is the successive shortest augmenting path algorithm: repeatedly find a cheapest s–t path in the residual graph with respect to edge costs and augment flow along that path. To handle potential negative costs, algorithms use potentials (Johnson’s trick) and often Dijkstra’s algorithm with reduced costs. Typical complexity is O(F E log V), where F is the maximum flow. Other methods include cycle-canceling, capacity scaling, and primal-dual algorithms.

Applications include assignment, transportation, scheduling, network routing, and various resource allocation problems. The problem is closely related to the minimum-cost circulation problem and can be used to model a wide range of optimization tasks.