6.6 The cycle-canceling algorithm¶
Part 3 · Flows · Chapter 6 · Chapter 6: Minimum cost flow · Lecture notes, volume 3 (PDF) · Exercises: Minimum cost flow
- Theorem 6.7 suggests an algorithm due to Klein: while \(G(\vet{x})\) has a negative cycle, augment along it. Augmenting by \(r(W)\) saturates an arc of \(W\), which leaves \(G(\vet{x})\): the cycle is canceled.
6.6.1 Finding a negative cycle¶
- A negative cycle of \(G(\vet{x})\) need not be reachable from a given node. We run the Bellman–Ford algorithm of Chapter 3 from a new node \(r\) joined to every node by an arc of cost \(0\); its first pass gives label \(0\) to every node, and we write the table from there.
Proposition 6.13: Bellman–Ford on the residual network
Let \(d^0(j)=0\) for every \(j \in N\) and, for \(k \ge 1\),
-
(a) \(d^k(j)\) is the minimum cost of a walk of \(G(\vet{x})\) with at most \(k\) arcs that ends at \(j\), the walk without arcs having cost \(0\).
-
(b) \(G(\vet{x})\) has a negative cycle if and only if \(d^n \neq d^{n-1}\). In that case, if \(d^n(j)<d^{n-1}(j)\), the predecessors read backwards from \(j\), one row per pass from row \(n\) to row \(1\), give a walk of \(G(\vet{x})\) with \(n\) arcs, ending at \(j\), that contains a negative cycle.
-
(c) If \(d^k=d^{k-1}\) for some \(k \le n\), the potentials \(\pi_i=-d^k(i)\) satisfy \(c^x_{ij}-\pi_i+\pi_j \ge 0\) on every arc of \(G(\vet{x})\).
Proof
Let \(H\) be \(G(\vet{x})\) plus the node \(r\) and the arcs \((r,i)\) of cost \(0\), and let \(D^k\) be the labels of Bellman–Ford from \(r\) in \(H\): \(D^1(i)=0\) for every \(i \in N\), and \(D^k(r)=0\) for every \(k\).
-
By induction on \(k\), \(D^{k+1}(j)=d^k(j)\) for \(j \in N\): the recursions coincide, and the arc \((r,j)\) offers \(D^k(r)+0=0\), which never lowers the minimum since \(d^{k-1}(j) \le d^0(j)=0\). A walk from \(r\) with \(k+1\) arcs is an arc \((r,i)\) followed by a walk of \(G(\vet{x})\) with \(k\) arcs from \(i\): this proves (a).
-
In \(H\) every node is reachable from \(r\), and the cycles are those of \(G(\vet{x})\). By Theorem «detection of a negative cycle» of Chapter 3, applied to the \(n+1\) nodes of \(H\), a negative cycle exists if and only if \(D^{n+1} \neq D^{n}\), that is \(d^n \neq d^{n-1}\). The walk from \(r\) with \(n+1\) arcs read in rows \(n+1,\dots,2\) of \(H\), which are our rows \(n,\dots,1\), contains a negative cycle; without its first arc \((r,\cdot)\) it is a walk of \(G(\vet{x})\) with \(n\) arcs, and the cycle does not contain \(r\). This proves (b).
-
If \(d^k=d^{k-1}\), the next pass repeats the labels: \(d^k(j) \le d^k(i)+c^x_{ij}\) for every arc \((i,j)\) of \(G(\vet{x})\), which is (c) with \(\pi=-d^k\). □
-
Rules of this chapter. The arcs of \(G(\vet{x})\) are scanned in lexicographic order; as in Chapter 3, ties in the minimum go to the smallest tail and a predecessor changes only when the label strictly decreases. If \(d^n \neq d^{n-1}\), \(j\) is the smallest node with \(d^n(j)<d^{n-1}(j)\), and the cycle is the piece of the walk between the two occurrences of the first node met twice, reading the walk from its first node.
-
At the stop the potentials \(\pi_i=-d^k(i)\) are shifted so that \(\pi_n=0\).
6.6.2 The algorithm¶
Algorithm: Cycle-canceling algorithm
STOP: unbounded.STOP: infeasible.STOP: \(\vet{x}\) is optimal, with \(\vet{\pi}=-d^k\).-
The test of Step 0 is Proposition 6.13 applied to the graph of the arcs with \(u_{ij}=+\infty\) and their costs. When it fails, every negative cycle of \(G(\vet{x})\) has an arc of finite residual capacity (proof of Proposition 6.8), so \(r(W)<+\infty\) in Step 2.
-
Any feasible flow can be used in Step 0; the maximum flow is one way to find it.
Theorem 6.14: correctness of cycle canceling
Let the balances, the capacities and the costs be integer, with capacities possibly \(+\infty\), and let the algorithm pass Step 0 with an integer feasible flow \(\vet{x}^0\). Then every flow of the algorithm is integer and feasible, every iteration lowers the cost by at least \(1\), and the algorithm stops after at most \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\) iterations with an optimal flow.
Proof
By Proposition 6.8 the model is bounded, so it has an optimal value \(z(\mathrm{MCF})\).
-
If \(\vet{x}\) is integer, the residual capacities are positive integers or \(+\infty\), and \(r(W)\) is a positive integer, since \(r(W)<+\infty\). By Proposition 6.3 the new flow is feasible and integer.
-
The cost changes by \(r(W)\,c(W)\), where \(r(W) \ge 1\) and \(c(W) \le -1\) are integers: it decreases by at least \(1\).
-
The cost starts at \(\vet{c}'\vet{x}^0\) and never goes below \(z(\mathrm{MCF})\), so there are at most \(\vet{c}'\vet{x}^0-z(\mathrm{MCF})\) iterations. At the stop \(G(\vet{x})\) has no negative cycle (Proposition 6.13), and \(\vet{x}\) is optimal by Theorem 6.7. □
-
Running time. \(G(\vet{x})\) has at most \(2m\) arcs, so Step 1 takes \(O(n\,m)\) time. With finite capacities, \(U=\max u_{ij}\) and \(K=\max |c_{ij}|\), every flow costs between \(-mKU\) and \(mKU\): at most \(2mKU\) iterations, and \(O(n\,m^2 K U)\) time.
-
The bound depends on the size of the numbers \(K\) and \(U\), not only on \(n\) and \(m\): it is a pseudo-polynomial bound.
6.6.3 Cycle canceling on the reference network¶
-
On the reference network Step 0 returns \(\tilde{\vet{x}}\) (Example 6.5), and the algorithm stops at the first Bellman–Ford run. To see it at work, we start from the most expensive flow \(\vet{x}^0\) of Example 6.1, of cost \(80\).
-
In the tables each row is a pass \(k\); next to a label that decreased, its new predecessor in brackets. The entries read backwards to find the walk are in bold.
Example 6.6: cycle canceling from the most expensive flow
Iteration 1
\(G(\vet{x}^0)\) is the residual network of Example 6.1. Bellman–Ford gives:
All the labels decrease in pass \(6\), so \(j=1\). Reading backwards: row \(6\) gives \(2\), row \(5\) for node \(2\) gives \(4\), then \(3\), \(5\), \(4\), \(6\). The walk \(6,4,5,3,4,2,1\) meets node \(4\) twice: \(W=4,5,3,4\), with \(c(W)=-11\) and \(r(W)=1\). The new flow is \(\vet{x}^1=(1,4,4,1,3,0,3,2,1)\), of cost \(69\).
Iteration 2
The arcs of \(W\) change: \((4,5)\) and \((5,3)\) lose one unit, \((3,4)\) disappears, and the forward arcs \((3,5)\), \((5,4)\) appear. \(G(\vet{x}^1)\) is:
| arc \((i,j)\) | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(x^1_{ij}\) | \(1\) | \(4\) | \(4\) | \(1\) | \(3\) | \(0\) | \(3\) | \(2\) | \(1\) |
| forward \((i,j)\): \(r,c\) | \(3,2\) | – | – | \(1,2\) | \(1,3\) | \(3,3\) | \(2,5\) | \(1,5\) | \(1,3\) |
| backward \((j,i)\): \(r,c\) | \(1,-2\) | \(4,-2\) | \(4,-5\) | \(1,-2\) | \(3,-3\) | – | \(3,-5\) | \(2,-5\) | \(1,-3\) |
Again \(j=1\), and the walk is \(6,4,5,6,4,2,1\): \(W=6,4,5,6\), made of the backward arcs of \((4,6)\) and \((5,4)\) and of the forward arc \((5,6)\), with \(c(W)=-5-5+3=-7\) and \(r(W)=\min\{3,2,1\}=1\). The new flow is \(\vet{x}^2=(1,4,4,1,3,0,2,1,2)\), of cost \(62\).
Iteration 3
In \(G(\vet{x}^2)\) the arc \((5,6)\) is saturated: only its backward arc \((6,5)\) remains, with \(r=2\), and the arcs \((6,4)\), \((4,5)\) have residual capacities \(2\) and \(1\), the forward arcs \((4,6)\), \((5,4)\) residual capacities \(3\) and \(2\). Bellman–Ford gives:
Only node \(3\) decreases in pass \(6\): \(j=3\), and the walk is \(6,4,5,3,1,2,3\). Node \(3\) is met twice: \(W=3,1,2,3\), made of the backward arc of \((1,3)\), the forward arc \((1,2)\) and the backward arc of \((3,2)\), with \(c(W)=-2+2-2=-2\) and \(r(W)=\min\{4,3,1\}=1\). The new flow is \(\vet{x}^3=(2,3,4,0,3,0,2,1,2)=\tilde{\vet{x}}\), of cost \(60\).
Iteration 4
Bellman–Ford on \(G(\tilde{\vet{x}})\) repeats the rows \(0\)–\(5\) of iteration \(3\), and in pass \(6\) no label decreases: \(d^6=d^5=(-15,-13,-13,-5,-10,0)\). The algorithm stops with \(\tilde{\vet{x}}\), certified by \(\vet{\pi}=-d^6=(15,13,13,5,10,0)\), already normalized with \(\pi_6=0\): the potentials of Chapter 4.
-
In summary:
iteration cost of \(\vet{x}\) \(j\) cycle \(W\) \(c(W)\) \(r(W)\) \(1\) \(80\) \(1\) \(4,5,3,4\) \(-11\) \(1\) \(2\) \(69\) \(1\) \(6,4,5,6\) \(-7\) \(1\) \(3\) \(62\) \(3\) \(3,1,2,3\) \(-2\) \(1\) \(4\) \(60\) – no negative cycle – – -
The bound of Theorem 6.14 allows \(80-60=20\) iterations; three are enough. The three cycles are the cycles of the decomposition of Example 6.2, found in a different order.
The cycle-canceling algorithm starts from a feasible flow and cancels negative cycles of \(G(\vet{x})\), found by Bellman–Ford from labels all equal to \(0\). With integer data every cancellation lowers the cost by at least \(1\); at the stop the labels give the potentials that certify the optimal flow.