6. Minimum-Cost Flows

This chapter is dedicated to another useful variation of network flows. This time, the goal is not to send the maximum amount of flow from one vertex \(s\) to another vertex \(t\) but to send a pre-specified amount of flow from a set of source vertices to a set of sink vertices, at minimum cost.

As a motivating example, consider a car manufacturer's operation. The manufacturer has a number of plants producing cars at different rates; each plant produces a certain number of cars each month. The cars are sold at car dealers with different demands for cars; each dealer sells a certain number of cars each month. Every car dealer needs to be supplied with exactly the number of cars sold and we need to decide which plants ship cars to which dealers. Since the transportation costs to a given dealer differ depending on the plant that sends the car, we want to choose the plants that supply the cars for each dealer so that the overall transportation cost is minimized and the number of cars sent to different dealers by each plant does not exceed the number of cars produced by the plant in each year. We also must not exceed the monthly transportation capacity along the routes between manufacturers and dealers imposed by the transportation network and contracts with logistics companies.

Formally, we can model the transportation network as a directed graph. Every edge \((x, y)\) has a capacity \(u_{x,y}\) and a cost \(c_{x,y}\). We are allowed to send up to \(u_{x,y}\) cars (units of flow) from \(x\) to \(y\) along this edge. The cost of sending \(f_{x,y}\) cars along the edge \((x, y)\) is \(c_{x,y} f_{x,y}\). The total cost of a flow \(f\) is then

\[cf = \sum_{(x, y) \in E} c_{x,y} f_{x,y}\]

(viewing \(c\) and \(f\) as \(m\)-element vectors with one entry per edge).

Every vertex \(x\) has an associated supply balance \(b_x\). If \(b_x\) is positive, \(x\) is a supply vertex (a manufacturer), producing \(b_x\) cars every month. If \(b_x\) is negative, \(x\) is a demand vertex (a car dealer), with demand for \(-b_x\) cars to be sold each month. If \(b_x = 0\), then \(x\) is neither a manufacturer nor a dealer and can only be used as a stop-over for cars travelling from manufacturers to dealers.

For simplicity, we assume that \(\sum_{x \in V} b_x = 0\), that is, the combined supply of all manufacturers exactly matches the demand of all dealers. Then we can formalize the minimum-cost flow problem as the following LP:

Minimum Cost Flow Problem:

\[\begin{gathered} \text{Minimize } cf\\ \begin{aligned} \text{s.t. } 0 \le f_e &\le u_e && \forall e \in E\\ \sum_{y \in V} \bigl(f_{x,y} - f_{y,x}\bigr) &= b_x && \forall x \in V. \end{aligned} \end{gathered}\tag{6.1}\]

Similarly to the maximum flow problem, we refer to the first set of constraints in (6.1) as capacity constraints, and to the second set of constraints as flow conservation constraints (the out-flow of a vertex matches its in-flow plus the flow \(b_x\) it produces).

In general, we allow edges to have infinite capacity \(u_e = \infty\).

An uncapacitated edge is an edge \(e \in E\) with \(u_e = \infty\).

A path made up of only uncapacitated edges is an uncapacitated path.

If all edges are uncapacitated, then we refer to \(G\) as an uncapacitated network.

Similar to the notion of a preflow in Chapter 5, we define:

A pseudo-flow is an edge labelling \(f : E \rightarrow \mathbb{R}^+\) that satisfies the capacity constraints:

\[0 \le f_e \le u_e \quad \forall e \in E.\]

As in Chapter 5,

A flow is an edge labelling \(f : E \rightarrow \mathbb{R}^+\) that satisfies both the capacity constraints,

\[0 \le f_e \le u_e \quad \forall e \in E.\]

and the flow conservation constraints,

\[\sum_{y \in V} \bigl(f_{x,y} - f_{y,x}\bigr) = b_x \quad \forall x \in V.\]

In other words, a flow is any feasible solution of (6.1).

A minimum-cost flow is a flow \(f : E \rightarrow \mathbb{R}^+\) of minimum cost

\[cf = \sum_{e \in E} c_e f_e.\]

Exercise 6.1: Consider a minimum-cost flow problem where the total supply exceeds the total demand, that is, \(\sum_{x \in V} b_x > 0\). In this case, the flow must satisfy all demands, must respect the capacity constraints of all edges, and must not exceed the supply of any vertex. Show how to adapt any minimum-cost flow algorithm for the case when the supply matches the demand to this more general case. In other words, take any minimum-cost flow algorithm as a black box and show how it can be used to solve this general version of the minimum-cost flow problem by providing it with a modified network as input.

In this chapter, we will explore a number of algorithms for computing minimum-cost flows:

• In Section 6.1, we discuss characterizations of minimum-cost flows, that is, conditions that a flow \(f\) satisfies if and only if it is a minimum-cost flow. These characterizations form the basis for the various algorithms we develop.

• In Section 6.2, we show how to express every flow as the sum of a set of very simple flows: path flows that send flow along a single path from a supply vertex to a demand vertex, and cycle flows that send flow along a single cycle in \(G\). This decomposition will be useful in analyzing some of the more advanced algorithms discussed later in this chapter.

• In Section 6.3, we discuss how we can transform the input network so that it satisfies certain properties and so that a solution of the minimum-cost flow problem on the original network can be readily obtained from a solution of the minimum-cost flow problem on the transformed network. Properties we may want to ensure are that there are no edges of negative cost or that the entire network is uncapacitated. This simplifies the description of some of the algorithms in this chapter.

• Section 6.4 finally introduces our first, and rather natural, algorithm for computing a minimum-cost flow, the negative cycle cancelling algorithm. This algorithm starts by constructing an arbitrary feasible flow, which we will see can be done using any maximum flow algorithm. Then we eliminate negative cycles in the residual network by sending flow along such cycles. As shown in Section 6.1.3, once no negative cycle exists, the flow is a minimum-cost flow.

• Section 6.5 introduces our second basic algorithm for computing minimum-cost flows, the successive shortest paths algorithm. This algorithms starts with the trivial pseudo-flow \(f = 0\) and then moves it towards feasibility by moving flow from supply vertices to demand vertices along shortest paths in the residual network.

There is a certain similarity between augmenting path algorithms for computing maximum \(st\)-flows and negative cycle cancelling algorithms in that both start with a feasible flow and improve the flow (by sending flow along augmenting paths or negative-cost cycles in the residual network). Similarly, preflow-push algorithms start with a preflow and move towards feasibility by eliminating excess flow from all vertices to establish flow conservation. Successive shortest paths algorithms start with a pseudo-flow and move towards feasibility by pushing flow from supply vertices to demand vertices along shortest paths in the residual network, again with the goal of establishing flow conservation. More generally, preflow-push and successive shortest paths algorithms are applications of the primal-dual schema, an important technique for designing optimization algorithms that can also be used to obtain approximation algorithms for NP-hard optimization problems.

The basic negative-cycle cancelling algorithm and the basic successive shortest paths algorithm are very simple but efficient only as long as the edge capacities and edge costs are polynomially bounded integer values. There exist numerous improvements over these algorithms, which we cannot all explore in this course. We discuss four of them:

• The first improvement is a simple capacity scaling algorithm, discussed in Section 6.6. This algorithm is important because it introduces a scaling technique to exponentially decrease the dependency of the algorithm's running time on the maximum edge capacity. This is a speed-up technique that can be applied to a wide range of optimization problems.

While capacity scaling speeds up successive shortest paths, it cannot eliminate its dependency on the edge capacities altogether. The remaining three algorithms in this chapter are true polynomial-time algorithms for computing minimum-cost flows, that is, algorithms whose running times depend polynomially on the size of the network but do not depend on the edge capacities and edge costs at all. An important consequence is that they work for arbitrary real-valued edge costs and capacities, not just for integral costs and capacities.

• The minimum-mean cycle cancelling algorithm, discussed in Section 6.7, is a version of negative cycle cancelling that is surprisingly easy to state but requires some care to analyze. It achieves a running time of \(O\bigl(n^2m^3\lg n\bigr)\). The basic idea is to choose the negative cycle along which to send flow in each iteration of the negative cycle cancelling algorithm as the one that minimizes the average (mean) cost of its edges.

• The repeated capacity scaling and enhanced capacity scaling algorithms, discussed in Sections 6.8 and 6.9, achieve significantly better running times and are based on successive shortest paths combined with particular refinements of capacity scaling.