Algo: Minimum Cost Maximum Flow

In network design, logistics, and resource allocation, you often face a dual challenge: moving as much material or data as possible while keeping expenses low. The minimum cost maximum flow algorithm solves this by finding the flow pattern that achieves the maximum possible throughput from a source to a sink at the smallest total cost. Mastering this technique is essential for optimizing everything from supply chains to communication networks, where efficiency directly impacts performance and budget.

Understanding the Minimum Cost Maximum Flow Problem

You can model a network as a directed graph where each edge has two key properties: a capacity limiting the flow it can carry and a cost per unit of flow sent across it. The minimum cost maximum flow problem asks you to determine the flow that sends the maximum possible amount from a designated source node to a sink node while minimizing the sum of all edge costs multiplied by the flow traversing them. This is inherently a linear optimization problem, but algorithms provide efficient, iterative solutions.

Formally, given a graph $G=(V,E)$ with source $s$, sink $t$, capacity function $u:E\to {\mathbb{R}}^{+}$, and cost function $c:E\to \mathbb{R}$, your goal is to find a flow $f:E\to {\mathbb{R}}^{+}$ that maximizes the total flow value $|f|$ from $s$ to $t$ and, among all maximum flows, minimizes the total cost ${\sum }_{e\in E}c(e)\cdot f(e)$. You must respect capacity constraints ($0\le f(e)\le u(e)$) and flow conservation at all nodes except $s$ and $t$. This framework directly extends maximum flow algorithms by adding an economic dimension.

The Successive Shortest Paths Algorithm: Core Mechanics

The successive shortest paths algorithm is a classic method that builds up maximum flow incrementally by always augmenting along the cheapest available path. You start with an initial flow of zero. In each iteration, you consider the residual network, which includes forward edges with remaining capacity and backward edges representing flow that can be undone. The cost of a backward edge is the negative of the original edge's cost, as sending flow back refunds cost.

To find the cheapest augmentation path, you need the shortest path from $s$ to $t$ in the residual network with respect to edge costs. However, because residual networks can contain edges with negative costs (from backward edges), you cannot immediately use Dijkstra's algorithm. Instead, you employ the Bellman-Ford algorithm for the first iteration to compute the shortest path distances from the source, which also handles negative costs and detects any negative cycles that would allow infinite, cost-decreasing flow.

Here is a step-by-step outline:

1. Initialize flow $f(e)=0$ for all edges $e$.
2. While the current flow is not maximum:

a. Construct the residual network $G_f$ with residual capacities and costs. b. Use Bellman-Ford (initially) or Dijkstra (with adjustments, discussed later) to find the shortest path $P$ from $s$ to $t$ in $G_f$ based on cost. c. Augment flow along $P$ by the maximum possible amount limited by the smallest residual capacity on $P$. d. Update the flow $f$ and the residual network.

1. The algorithm terminates when no augmenting path exists, meaning maximum flow is reached, and the sequence of cheapest paths ensures minimum total cost.

Leveraging Potentials and Reduced Costs for Efficiency

Using Bellman-Ford in every iteration is inefficient, as it runs in $O(VE)$ time. To speed this up, you introduce potentials, which are node labels $\pi (v)$ for each vertex $v$. Potentials allow you to transform edge costs into reduced costs that are non-negative, enabling the use of Dijkstra's faster $O(E\log V)$ algorithm. For any edge $(u,v)$ with original cost $c(u,v)$, the reduced cost is defined as:

$$c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)$$

A key property is that a path is shortest with respect to reduced costs if and only if it is shortest with respect to original costs, as the potential differences cancel out along any path. Initially, you compute potentials $\pi$ as the shortest path distances from $s$ using Bellman-Ford on the original graph, which ensures all reduced costs are non-negative. After each flow augmentation, you update the potentials by setting $\pi (v)=\pi (v)+d(v)$, where $d(v)$ is the shortest path distance from $s$ to $v$ in the residual network using reduced costs from the previous iteration. This maintenance keeps reduced costs non-negative for subsequent steps.

Implementing with Dijkstra: Johnson's Reweighting Technique

The process of using potentials to enable Dijkstra mirrors Johnson's reweighting technique for all-pairs shortest paths. Once you have initial potentials from Bellman-Ford, you can use Dijkstra's algorithm to find shortest paths in the residual network by operating on reduced costs. This combination is often called the successive shortest paths algorithm with potentials.

In practice, your implementation follows this workflow:

1. Run Bellman-Ford from the source $s$ on the original graph to compute initial potentials $\pi$ and ensure no negative cycles exist.
2. Initialize flow to zero.
3. While augmenting paths exist:

a. Build the residual network $G_f$. b. For each edge $(u,v)$ in $G_f$, compute its reduced cost $c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)$. c. Run Dijkstra from $s$ using these reduced costs to find shortest path distances $d(v)$ and the cheapest path $P$ to $t$. d. Augment flow along $P$. e. Update potentials: for each node $v$, set $\pi (v)=\pi (v)+d(v)$.

1. The algorithm yields the maximum flow with minimum cost.

This approach efficiently handles large networks by leveraging Dijkstra's speed while managing negative costs through careful potential updates. It assumes the network has no negative cycles reachable from $s$, as those would make the minimum cost unbounded.

Real-World Applications: Transportation and Assignment Problems

The minimum cost maximum flow model is directly applicable to classic optimization problems. In the transportation problem, you have multiple sources (e.g., warehouses) with supply limits and multiple sinks (e.g., retail stores) with demand requirements, each with per-unit shipping costs. You can transform this into a minimum cost flow network by connecting a super-source to all warehouses and a super-sink to all stores, then solving for maximum flow at minimum cost to meet all demands.

Similarly, the assignment problem—such as assigning workers to jobs to minimize total cost—can be modeled as a bipartite matching where each worker-job pair has a cost. By adding a source connected to workers and a sink connected to jobs, with all edges having capacity one, finding the minimum cost maximum flow gives the optimal assignment. These applications show how the algorithm provides a unified framework for resource allocation where both volume and economy are critical.

Common Pitfalls

1. Ignoring negative cycles in the initial setup: If the original network contains a negative cycle reachable from the source, the minimum cost is unbounded. Always use Bellman-Ford initially to detect such cycles; if found, the problem is ill-posed for minimum cost flow without additional constraints.

• Correction: Run Bellman-Ford from the source before starting flow augmentation. If a negative cycle is detected, you must address it by reformulating the problem or using cycle-canceling algorithms.

1. Failing to update potentials correctly after augmentation: After each Dijkstra run, you must add the shortest path distances to the potentials. Skipping this step or using outdated distances can cause reduced costs to become negative, breaking Dijkstra's non-negativity requirement.

• Correction: Strictly follow the update rule ${\pi }_{\text{new}}(v)={\pi }_{\text{old}}(v)+d(v)$ for all nodes $v$, where $d(v)$ is the distance from the last Dijkstra execution.

1. Misapplying Dijkstra without verifying non-negative reduced costs: Even with potentials, if you compute reduced costs incorrectly—for instance, by using original costs in residual edges—Dijkstra may produce wrong shortest paths.

• Correction: Double-check that for every residual edge $(u,v)$, you compute $c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)$. For backward edges, remember that $c(u,v)$ is the negative of the original edge's cost.

1. Overlooking capacity constraints during augmentation: When sending flow along the cheapest path, you must respect the minimum residual capacity on that path. Exceeding this can violate flow feasibility.

• Correction: Always compute the bottleneck capacity $\delta =\min \{\text{residual capacity of edges on }P\}$ and augment by exactly $\delta$.

Summary

• Minimum cost maximum flow solves the dual objective of maximizing throughput and minimizing total cost in weighted networks, with applications in logistics, scheduling, and network design.
• The successive shortest paths algorithm iteratively augments flow along the cheapest available path in the residual network, using Bellman-Ford initially to handle negative costs.
• Potentials and reduced costs transform edge costs to non-negative values, enabling efficient shortest path computation with Dijkstra's algorithm, akin to Johnson's reweighting.
• This framework naturally models transportation and assignment problems, providing optimal solutions for resource allocation with cost constraints.
• Key implementation cautions include detecting negative cycles, correctly updating potentials, and ensuring non-negative reduced costs for Dijkstra to maintain algorithm correctness and efficiency.