6.4 Optimality conditions with potentials¶
Part 3 · Flows · Chapter 6 · Chapter 6: Minimum cost flow · Lecture notes, volume 3 (PDF) · Exercises: Minimum cost flow
-
Given potentials \(\vet{\pi} \in \R^n\), the reduced cost of an arc \((i,j)\) of \(G(\vet{x})\) is \(c^x_{ij}-\pi_i+ \pi_j\). For a forward arc it is \(\bar{c}_{ij}=c_{ij}-\pi_i+\pi_j\), the reduced cost of Chapter 4; for the backward arc \((j,i)\) of \((i,j)\) it is \(-c_{ij}-\pi_j+\pi_i=-\bar{c}_{ij}\).
-
Along a cycle \(W\) of \(G(\vet{x})\) the potentials telescope, as in Chapter 3:
\[ c(W)=\sum_{(i,j) \in W}\big(c^x_{ij}-\pi_i+\pi_j\big). \]
Theorem 6.9: reduced cost optimality
A feasible flow \(\vet{x}\) is optimal if and only if there are potentials \(\vet{\pi} \in \R^n\) such that
Proof
If. By the telescoping formula every cycle of \(G(\vet{x})\) has \(c(W) \ge 0\), and \(\vet{x}\) is optimal by Theorem 6.7.
Only if. Let \(\vet{x}\) be optimal: by Theorem 6.7, \(G(\vet{x})\) has no negative cycle.
-
Add a node \(r\) and an arc \((r,i)\) of cost \(0\) for every \(i \in N\). In the new graph every node is reachable from \(r\), and the cycles are those of \(G(\vet{x})\), since no arc enters \(r\): none is negative.
-
By Theorem «Bellman's equations» of Chapter 3, the distances \(d(i)\) from \(r\) are finite and \(d(j) \le d(i)+c^x_{ij}\) for every arc \((i,j)\) of \(G(\vet{x})\).
-
With \(\pi_i=-d(i)\) we get \(c^x_{ij}-\pi_i+\pi_j=c^x_{ij}+d(i)-d(j) \ge 0\). □
Corollary 6.10: complementary slackness
Let \(\vet{x}\) be a feasible flow and \(\vet{\pi} \in \R^n\). The condition of Theorem 6.9 holds if and only if, for every arc \((i,j) \in A\),
In particular, \(l_{ij}<x_{ij}<u_{ij}\) implies \(\bar{c}_{ij}=0\).
Proof
The arc \((i,j) \in A\) gives the forward arc, of reduced cost \(\bar{c}_{ij}\), when \(x_{ij}<u_{ij}\), and the backward arc, of reduced cost \(-\bar{c}_{ij}\), when \(x_{ij}>l_{ij}\). So the condition on the arcs coming from \((i,j)\) reads
Since \(l_{ij} \le x_{ij} \le u_{ij}\), the first implication is equivalent to \(\bar{c}_{ij}<0 \Rightarrow x_{ij}=u_{ij}\), and the second to \(\bar{c}_{ij}>0 \Rightarrow x_{ij}=l_{ij}\). If \(l_{ij}<x_{ij}<u_{ij}\), both implications apply and \(\bar{c}_{ij}=0\). □
-
With \(\vet{l}=\vet{0}\) these are the conditions of Corollary «reduced cost certificate» of Chapter 4. There they were proved sufficient with LP duality; Theorem 6.9 shows that every optimal flow has such potentials, which with \(\alpha_{ij}=\max\{0,-\bar{c}_{ij}\}\) form an optimal dual solution.
-
The potentials of the proof are \(\pi_i=-d(i)\), minus the distances from \(r\), as \(\pi_i=-\tilde{d}(i)\) in Chapter 3. They can be shifted by a constant; we normalize them with \(\pi_n=0\).
Example 6.4: the certificate of the optimal flow
We take \(\tilde{\vet{x}}\) and the potentials \(\vet{\pi}=(15,13,13,5,10,0)\) of Chapter 4. The reduced costs of the arcs of \(G(\tilde{\vet{x}})\) are \(\bar{c}_{ij}\) on the forward arcs and \(-\bar{c}_{ij}\) on the backward arcs:
| arc \((i,j)\) | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\tilde{x}_{ij}\) | \(2\) | \(3\) | \(4\) | \(0\) | \(3\) | \(0\) | \(2\) | \(1\) | \(2\) |
| \(\bar{c}_{ij}\) | \(0\) | \(0\) | \(-3\) | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | \(-7\) |
| forward \((i,j)\) | \(0\) | \(0\) | – | \(2\) | \(0\) | \(11\) | \(0\) | \(0\) | – |
| backward \((j,i)\) | \(0\) | \(0\) | \(3\) | – | \(0\) | – | \(0\) | \(0\) | \(7\) |
-
All the \(14\) arcs of \(G(\tilde{\vet{x}})\) have non-negative reduced cost: by Theorem 6.9, \(\tilde{\vet{x}}\) is optimal. In the form of Corollary 6.10: \((3,2)\) and \((4,3)\) are empty, \((2,4)\) and \((5,6)\) are saturated.
-
The potentials are minus the costs of the cheapest walks of \(G(\tilde{\vet{x}})\) ending at each node. For example, the walk \(6,4,5,3,1\) uses four backward arcs and costs \(-5-5-3-2=-15=-\pi_1\): in \(G\) it is the path \(1,3,5,4,6\) of the spanning tree of Chapter 4.
A feasible flow is optimal if and only if some potentials give non-negative reduced costs on all the arcs of \(G(\vet{x})\): positive \(\bar{c}_{ij}\) only on arcs at the lower bound, negative only on saturated arcs. Such potentials are minus the distances in \(G(\vet{x})\) from a node joined to all the others.