6.1.1. Complementary Slackness

Complementary slackness is not used directly as the basis for any of the algorithms discussed in this chapter. However, the two optimality criteria that are used in these algorithms are based on complementary slackness. Thus, we start by characterizing a minimum-cost flow using the dual of (6.1) and the corresponding complementary slackness conditions.

For reference, here is (6.1) again, slightly rewritten to split the capacity constraints into upper bound constraints and non-negativity constraints:

\[\begin{gathered} \text{Minimize } cf\\ \begin{aligned} \text{s.t. } 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\\ f_e &\ge 0 && \forall e \in E. \end{aligned} \end{gathered}\tag{6.2}\]

The dual of (6.2) is

\[\begin{gathered} \text{Maximize } \sum_{x \in V} b_x\pi_x - \sum_{(x, y) \in E_b} u_{x,y}s_{x,y}\\ \begin{aligned} \text{s.t. } \pi_x - \pi_y - s_{x,y} &\le c_{x,y} && \forall (x, y) \in E_b\\ \pi_x - \pi_y &\le c_{x,y} && \forall (x, y) \in E_u\\ s_{x,y} &\ge 0 && \forall (x, y) \in E_b, \end{aligned} \end{gathered}\tag{6.3}\]

where \(E_b\) is the set of all edges with finite (bounded) capacity, \(E_u = E \setminus E_b\) is the set of all edges with infinite (unbounded) capacity, \(\pi_x\) is the dual variable associated with the flow conservation constraint of vertex \(x\), and \(s_{x,y}\) is the dual variable associated with the capacity constraint of the edge \((x, y) \in E_b\).

There are no dual variables \(s_{x,y}\) associated with the edge \((x, y) \in E_u\) because the corresponding primal constraint is \(f_{x,y} \le \infty\) and can be omitted (any real number is no greater than infinity).

From here on, we refer to the function \(\pi : V \rightarrow \mathbb{R}\) as a potential function.

Given a cost function \(c : E \rightarrow \mathbb{R}\) and a potential function \(\pi : V \rightarrow \mathbb{R}\), the reduced cost function \(c^\pi\) with respect to \(c\) and \(\pi\) is defined as

\[c^\pi_{x,y} = c_{x,y} - \pi_x + \pi_v \quad \forall x, y \in V.\]

We call a potential function \(\pi\) feasible if there exists a labelling \(s : E_b \rightarrow \mathbb{R}\) such that \((\pi, s)\) is a feasible solution of (6.3).

We call \(\pi\) an optimal potential function if there exists such a feasible solution \((\pi, s)\) of (6.3) that is an optimal solution.

Lemma 6.1: Let \(f\) be a flow in \(G\) and let \(\pi\) be a potential function. Then \(f\) is a minimum-cost flow and \(\pi\) is an optimal potential function for \(G\) if and only if

• \(f_{x,y} = 0\) for every edge \((x, y)\) that satisfies \(c^\pi_{x,y} > 0\) and
• \(f_{x,y} = u_{x,y}\) for every edge \((x, y)\) that satisfies \(c^\pi_{x,y} < 0\).

Note how this lemma captures our intuition about a minimum-cost flow: An edge with positive (reduced) cost should not be used by an optimal flow because this can only increase the cost. An edge with negative (reduced) cost should be used to its maximum capacity because this decreases the cost of the flow.

Proof: For any feasible potential function \(\pi\), let \(s^\pi\) be a labelling of the edges in \(E_b\) such that \(\bigl(\pi, s^\pi\bigr)\) is a feasible solution of (6.3) and there is no feasible solution \((\pi, s)\) that achieves a greater objective function value. In other words, \(\bigl(\pi, s^\pi\bigr)\) is the best solution of (6.3) that satisfies the condition that \(\pi\) is part of this solution.

Observe that every edge \((x, y) \in E_b\) satisfies

\[s^\pi_{x,y} = -c^\pi_{x,y} \text{ or } u_{x,y} = 0.\tag{6.4}\]

Indeed,

\[\pi_x - \pi_y - s^\pi_{x,y} \le c_{x,y},\]

so

\[-s^\pi_{x,y} \le c^\pi_{x,y},\]

that is,

\[s^\pi_{x,y} \ge -c^\pi_{x,y}.\]

Thus, if \(s^\pi_{x,y} \ne -c^\pi_{x,y}\), then \(s^\pi_{x,y} > -c^\pi_{x,y}\). Setting \(s^\pi_{x,y} = -c^\pi_{x,y}\) decreases \(s^\pi_{x,y}\) in this case while still satisfying the constraint that \(\pi_x - \pi_y - s^\pi_{x,y} \le c_{x,y}\).

If \(u_{x,y} > 0\), then decreasing \(s^\pi_{x,y}\) increases the objective function value of \(\bigl(\pi, s^\pi\bigr)\) in (6.3), contradicting the choice of \(s^\pi\). Thus, we can have \(s^\pi_{x,y} > -c^\pi_{x,y}\) only if \(u_{x,y} = 0\).

Now, if \(f\) is a minimum-cost flow and \(\pi\) is an optimal potential function, then \(\pi\) is a feasible potential function, so an edge labelling \(s^\pi\) as above exists. Moreover, since \(\pi\) is an optimal potential function, \(\bigl(\pi, s^\pi\bigr)\) is an optimal solution of (6.3). Thus, by Theorem 4.5,

• Dual complementary slackness: \(f_{x,y} = u_{x,y}\) or \(s^\pi_{x,y} = 0\) for every edge \((x, y) \in E_b\),

• Primal complementary slackness for capacitated edges: \(\pi_x - \pi_y - s^\pi_{x,y} = c_{x,y}\) or \(f_{x,y} = 0\) for every edge \((x, y) \in E_b\), and

• Primal complementary slackness for uncapacitated edges: \(\pi_x - \pi_y = c_{x,y}\) or \(f_{x,y} = 0\) for every edge \((x, y) \in E_u\).

The flow conservation constraints are equality constraints and thus do not introduce any complementary slackness conditions.

To prove that \(f_{x,y} = 0\) for every edge \((x, y)\) that satisfies \(c_{x,y}^\pi > 0\), consider any such edge \((x, y)\). Then \(c_{x,y} >\pi_x - \pi_y\).

If \((x, y) \in E_u\), then primal complementary slackness for uncapacitated edges shows that \(f_{x,y} = 0\).

If \((x, y) \in E_b\), then \(\pi_x - \pi_y \ge \pi_x - \pi_y - s^\pi_{x,y}\) because \(s^\pi_{x,y} \ge 0\), so \(c_{x,y} > \pi_x - \pi_y - s^\pi_{x,y}\). Thus, primal complementary slackness for capacitated edges shows that \(f_{x,y} = 0\).

This proves that \(f_{x,y} = 0\) for every edge \((x, y)\) that satisfies \(c_{x,y}^\pi > 0\).

To prove that \(f_{x,y} = u_{x,y}\) for every edge \((x, y)\) that satisfies \(c^\pi_{x,y} < 0\), consider any such edge \((x, y)\). Then \(c_{x,y} < \pi_x - \pi_y\).

Since \(c_{x,y} \ge \pi_x - \pi_y\) for all \((x, y) \in E_u\), this implies that \((x, y) \in E_b\).

Since \(c_{x,y} \ge \pi_x - \pi_y - s^\pi_{x,y}\) for every edge \((x, y) \in E_b\), we furthermore have that \(s^\pi_{x,y} > 0\). Thus, dual complementary slackness, \(f_{x,y} = u_{x,y}\).

This proves that \(f_{x,y} = u_{x,y}\) for every edge \((x, y)\) that satisfies \(c^\pi_{x,y} < 0\).

We have shown that a minimum-cost flow \(f\) and an optimal potential function \(\pi\) satisfy the conditions of the lemma.

Now assume that \(f\) and \(\pi\) satisfy the conditions of the lemma. We need to prove that \(f\) is a minimum-cost flow and that \(\pi\) is an optimal potential function. By Theorem 4.5, this is the case if \(f\) and \(\bigl(\pi, s^\pi\bigr)\) satisfy the complementary slackness conditions above.

First observe that \(\pi\) is a feasible potential function, so an edge labelling \(s^\pi\) as above exists. Indeed, if \(s\) is the edge labelling defined as

\[s_{x,y} = \begin{cases} 0 & \text{if } c^\pi_{x,y} \ge 0\\ -c^\pi_{x,y} & \text{if } c^\pi_{x,y} < 0, \end{cases}\]

then \((\pi, s)\) is a feasible solution of (6.3): Clearly, \(s_{x,y} \ge 0\) for all \((x, y) \in E_b\). If \((x, y) \in E_u\), then \(f_{x,y} < u_{x,y}\) because \(f_{x,y}\) is finite. Thus, by the second condition of the lemma, \(c^\pi_{x,y} \ge 0\), that is, \(\pi_x - \pi_y \le c_{x,y}\). If \((x, y) \in E_b\), then the choice of \(s_{x,y}\) ensures that \(s_{x,y} \ge -c^\pi_{x,y}\). Thus, \(\pi_x - \pi_y - s_{x,y} \le \pi_x - \pi_y + c^\pi_{x,y} = c_{x,y}\).

Now, to prove that the dual complementary slackness condition holds, consider any edge \((x, y) \in E_b\) such that \(s^\pi_{x,y} > 0\). Then, by (6.4), either \(c^\pi_{x,y} = -s^\pi_{x,y} < 0\) or \(u_{x,y} = 0\). In the former case, \(f_{x,y} = u_{x,y}\), by the second condition of the lemma. In the latter case, \(0 \le f_{x,y} \le u_{x,y} = 0\) because \(f\) is a flow. Thus, again, \(f_{x,y} = u_{x,y}\). This proves that the dual complementary slackness condition holds.

To prove that the primal complementary slackness conditions hold, consider any edge \((x, y)\) such that \(f_{x,y} > 0\). By the first condition of the lemma, this implies that \(c^\pi_{x,y} \le 0\), that is, \(c_{x,y} \le \pi_x - \pi_y\).

If \((x, y) \in E_u\), we have \(c_{x,y} \ge \pi_x - \pi_x\) because \(\pi\) is a feasible potential function. Thus, \(c_{x,y} = \pi_x - \pi_y\). This proves the primal complementary slackness condition for uncapacitated edges.

If \((x, y) \in E_b\), then observe that \(f_{x,y} \le u_{x,y}\). Thus, since \(f_{x,y} > 0\), we have \(u_{x,y} > 0\) and, therefore, \(s^\pi_{x,y} = -c^\pi_{x,y}\), again by (6.4). This implies that \(\pi_x - \pi_y - s^\pi_{x,y} = \pi_x - \pi_y + c_{x,y} - \pi_x - \pi_y = c_{x,y}\). This proves the primal complementary slackness condition for capacitated edges. ▨