7.4 Duality

7.4 Duality

We have seen that in networks, flows are smaller than cuts, but the maximum flow and minimum cut exactly coincide and each is therefore a certificate of the other’s optimality. Remarkable as this phenomenon is, we now generalize it from maximum flow to any problem that can be solved by linear programming! It turns out that every linear maximization problem has a dual minimization problem, and they relate to each other in much the same way as flows and cuts.

To understand what duality is about, recall our introductory LP with the two types of chocolate:

c max x _ 1 + 6 x _ 2 x _ 1 ≤ 2 0 0 x _ 2 ≤ 3 0 0 x _ 1 + x _ 2 ≤ 4 0 0 x _ 1, x _ 2 ≥ 0$$\begin{array}{c}\max x_1+6x_2\\ x_1\le 200\\ x_2\le 300\\ x_1+x_2\le 400\\ x_1,x_2\ge 0\end{array}$$

Simplex declares the optimum solution to be $(x_1,x_2)=(100,300)$ , with objective value 1900. Can this answer be checked somehow? Let’s see: suppose we take the first inequality and add it to six times the second inequality. We get

x _ 1 + 6 x _ 2 ≤ 2 0 0 0.$$x_1+6x_2\le 2000.$$

This is interesting, because it tells us that it is impossible to achieve a profit of more than 2000. Can we add together some other combination of the LP constraints and bring this upper bound even closer to 1900? After a little experimentation, we find that multiplying the three inequalities by 0, 5, and 1, respectively, and adding them up yields

x _ 1 + 6 x _ 2 ≤ 1 9 0 0.$$x_1+6x_2\le 1900.$$

So 1900 must indeed be the best possible value! The multipliers (0, 5, 1) magically constitute a certificate of optimality! It is remarkable that such a certificate exists for this LP—and even if we knew there were one, how would we systematically go about finding it?

Let’s investigate the issue by describing what we expect of these three multipliers, call them y₁, $y$₂, $y$₃.

Multiplier	Inequality
$y_1$	$x_1$	$\le 200$
$y_2$		$x_2\le 300$
$y_3$	$x_1+x_2$	$\le 400$

	Primal feasible	Primal opt	Dual opt	Dual feasible	Objective value
	This duality gap is zero

Figure 7.9 By design, dual feasible values primal feasible values. The duality theorem tells us that moreover their optima coincide.

To start with, these $y_i\vec{\mathbf{s}}$ must be nonnegative, for otherwise they are unqualified to multiply inequalities (multiplying an inequality by a negative number would flip the to ). After the multiplication and addition steps, we get the bound:

(y _ 1 + y _ 3) x _ 1 + (y _ 2 + y _ 3) x _ 2 ≤ 2 0 0 y _ 1 + 3 0 0 y _ 2 + 4 0 0 y _ 3.$$(y_1+y_3)x_1+(y_2+y_3)x_2\le 200y_1+300y_2+400y_3.$$

We want the left-hand side to look like our objective function $x_1+6x_2$ so that the right-hand side is an upper bound on the optimum solution. For this we need $y_1+y_3$ to be 1 and $y_2+y_3$ to be 6. Come to think of it, it would be fine if $y_1+y_3$ were larger than 1—the resulting certificate would be all the more convincing. Thus, we get an upper bound

x _ 1 + 6 x _ 2 ≤ 2 0 0 y _ 1 + 3 0 0 y _ 2 + 4 0 0 y _ 3 text if { l y _ 1, y _ 2, y _ 3 ≥ 0 y _ 1 + y _ 3 ≥ 1 y _ 2 + y _ 3 ≥ 6 }.$$x_1+6x_2\le 200y_1+300y_2+400y_3\text{ if }\left\{\begin{array}{l}{y}_1,y_2,y_3\ge 0\\ y_1+y_3\ge 1\\ y_2+y_3\ge 6\end{array}\right\}.$$

We can easily find $y\bar{\mathbf{s}}$ that satisfy the inequalities on the right by simply making them large enough, for example $(y_1,y_2,y_3)=(5,3,6)$ . But these particular multipliers would tell us that the optimum solution of the LP is at most $200\cdot 5+300\cdot 3+400\cdot 6=4300$ , a bound that is far too loose to be of interest. What we want is a bound that is as tight as possible, so we should minimize $200y_1+300y_2+400y_3$ subject to the preceding inequalities. And this is a new linear program!

Therefore, finding the set of multipliers that gives the best upper bound on our original LP is tantamount to solving a new LP:

c min 2 0 0 y _ 1 + 3 0 0 y _ 2 + 4 0 0 y _ 3 y _ 1 + y _ 3 ≥ 1 y _ 2 + y _ 3 ≥ 6 y _ 1, y _ 2, y _ 3 ≥ 0$$\begin{array}{c}\min 200y_1+300y_2+400y_3\\ y_1+y_3\ge 1\\ y_2+y_3\ge 6\\ y_1,y_2,y_3\ge 0\end{array}$$

By design, any feasible value of this dual LP is an upper bound on the original primal LP. So if we somehow find a pair of primal and dual feasible values that are equal, then they must both be optimal. Here is just such a pair:

text Primal : (x _ 1, x _ 2) = (1 0 0, 3 0 0); text Dual : (y _ 1, y _ 2, y _ 3) = (0, 5, 1).$$\text{ Primal }:(x_1,x_2)=(100,300);\text{ Dual }:(y_1,y_2,y_3)=(0,5,1).$$

They both have value 1900, and therefore they certify each other’s optimality (Figure 7.9).

Figure 7.10 A generic primal LP in matrix-vector form, and its dual.
Primal LP:	Dual LP:
	$\max c^{T}x$	$\min y^{T}b$
	$Ax\le b$	$y^{T}A\ge c^T$
	$x\ge 0$	$y\ge 0$

Figure 7.11In the most general case of linear programming, we have a set I of inequalities and a set E of equalities (a total of $m = |I| + |E|$ constraints) over n variables, of which a subset N are constrained to be nonnegative. The dual has $m = |I| + |E|$ variables, of which only those corresponding to I have nonnegativity constraints.

Primal LP: $\max c_1{x}_1+\cdots +c_n{x}_n$ $a_{i1}{x}_1+\cdots +a_{in}{x}_n\le b_i$ for $i\in I$ $a_{i1}{x}_1+\cdots +a_{in}{x}_n=b_i$ for $i\in E$ $x_j\ge 0$ for $j\in N$

Dual LP: $\min b_1{y}_1+\cdots +b_m{y}_m$ $a_{1j}{y}_1+\cdots +a_{mj}{y}_m\ge c_j$ for $j\in N$ $a_{1j}{y}_1+\cdots +a_{mj}{y}_m=c_j$ for $jotinN$ $y_i\ge 0$ for $i\in I$

Amazingly, this is not just a lucky example, but a general phenomenon. To start with, the preceding construction—creating a multiplier for each primal constraint; writing a constraint in the dual for every variable of the primal, in which the sum is required to be above the objective coefficient of the corresponding primal variable; and optimizing the sum of the mul tipliers weighted by the primal right-hand sides—can be carried out for any LP, as shown in Figure 7.10, and in even greater generality in Figure 7.11. The second figure has one noteworthy addition: if the primal has an equality constraint, then the corresponding multiplier (or dual variable) need not be nonnegative, because the validity of equations is preserved when multiplied by negative numbers. So, the multipliers of equations are unrestricted variables. Notice also the simple symmetry between the two LPs, in that the matrix $A=\left(a_{ij}\right)$ defines one primal constraint with each of its rows, and one dual constraint with each of its columns.

By construction, any feasible solution of the dual is an upper bound on any feasible solution of the primal. But moreover, their optima coincide!

Duality theorem If a linear program has a bounded optimum then so does its dual and the two optimum values coincide.

When the primal is the LP that expresses the max-flow problem, it is possible to assign interpretations to the dual variables that show the dual to be none other than the minimumcut problem (Exercise7.25). The relation between flows and cuts is therefore just a specific instance of the duality theorem. And in fact, the proof of this theorem falls out of the simplex algorithm, in much the same way as the max-flow min-cut theorem fell out of the analysis of the max-flow algorithm.

Box: Visualizing duality

One can solve the shortest-path problem by the following “analog” device: Given a weighted undirected graph, build a physical model of it in which each edge is a string of length equal to the edge’s weight, and each node is a knot at which the appropriate endpoints of strings are tied together. Then to find the shortest path from s to $t,$ just pull s away from t until the gadget is taut. It is intuitively clear that this finds the shortest path from s to t.

There is nothing remarkable or surprising about all this until we notice the following: the shortest-path problem is a minimization problem, right? Then why are we pulling s away from t, an act whose purpose is, obviously, maximization? Answer: By pulling s away from t we solve the dual of the shortest-path problem! This dual has a very simple form (Exercise7.28), with one variable $x_u$ for each node u:

c max x _ S - x _ T | x _ u - x _ v | ≤ w _ u v text for all edges {u, v }$$\begin{array}{c}\max x_S-x_T\\ |x_u-x_v|\le w_{uv}\text{ for all edges }\{u,v\}\end{array}$$

In words, the dual problem is to stretch s and t as far apart as possible, subject to the constraint that the endpoints of any edge $\{u,v\}$ are separated by a distance of at most $w_{uv}.$