29.4 Duality

29.4-1

Formulate the dual of the linear program given in Exercise 29.3-5.

By just transposing $A$, swapping $b$ and $c$, and switching the maximization to a minimization, we want to minimize $20y_1 + 12y_2 + 16y_3$ subject to the constrain

$$ \begin{aligned} y_1 + y_2 & \ge 18 \\ y_1 + y_3 & \ge 12.5 \\ y_1, y_2, y_3 & \ge 0 \end{aligned} $$

29.4-2

Suppose that we have a linear program that is not in standard form. We could produce the dual by first converting it to standard form, and then taking the dual. It would be more convenient, however, to be able to produce the dual directly. Explain how we can directly take the dual of an arbitrary linear program.

By working through each aspect of putting a general linear program into standard form, as outlined on page 852, we can show how to deal with transforming each into the dual individually. If the problem is a minimization instead of a maximization, replace $c_j$ by $−c_j$ in $\text{(29.84)}$. If there is a lack of nonnegativity constraint on $x_j$ we duplicate the $j$th column of $A$, which corresponds to duplicating the $j$th row of $A^{\text T}$. If there is an equality constraint for $b_i$, we convert it to two inequalities by duplicating then negating the $i$th column of $A^{\text T}$, duplicating then negating the $i$th entry of $b$, and adding an extra $y_i$ variable. We handle the greater-than-or-equal-to sign $\sum_{i = 1}^n a_{ij}x_j \ge b_i$ by negating $i$th column of $A^{\text T}$ and negating $b_i$. Then we solve the dual problem of minimizing $b^{\text T}y$ subject to $A^{\text T}y$ and $y \ge 0$.

29.4-3

Write down the dual of the maximum-flow linear program, as given in lines $\text{(29.47)}$–$\text{(29.50)}$ on page 860. Explain how to interpret this formulation as a minimum-cut problem.

First, we'll convert the linear program for maximum flow described in equation $\text{(29.47)}$-$\text{(29.50)}$ into standard form. The objective function says that $c$ is a vector indexed by a pair of vertices, and it is positive one if $s$ is the first index and negative one if $s$ is the second index (zero if it is both). Next, we'll modify the constraints by switching the equalities over into inequalities to get

$$ \begin{array}{rcll} f_{uv} & \le & c(u, v) & \text{ for each } u, v \in V \\ \sum_{u \in V} f_{vu} & \le & \sum_{u \in V} f_{uv} & \text{ for each } v \in V - \{s, t\} \\ \sum_{u \in V} f_{vu} & \ge & \sum_{u \in V} f_{uv} & \text{ for each } v \in V - \{s, t\} \\ f_{uv} & \ge & 0 & \text{ for each } u, v \in V \end{array} $$

Then, we'll convert all but the last set of the inequalities to be $\le$ by multiplying the third line by $-1$.

$$ \begin{array}{rcll} f_{uv} & \le & c(u, v) & \text{ for each } u, v \in V \\ \sum_{u \in V} f_{vu} & \le & \sum_{u \in V} f_{uv} & \text{ for each } v \in V - \{s, t\} \\ \sum_{u \in V} -f_{vu} & \le & \sum_{u \in V} -f_{uv} & \text{ for each } v \in V - \{s, t\} \\ f_{uv} & \ge & 0 & \text{ for each } u, v \in V \end{array} $$

Finally, we'll bring all the variables over to the left to get

$$ \begin{array}{rcll} f_{uv} & \le & c(u, v) & \text{ for each } u, v \in V \\ \sum_{u \in V} f_{vu} - \sum_{u \in V} f_{uv} & \le & 0 & \text{ for each } v \in V - \{s, t\} \\ \sum_{u \in V} -f_{vu} - \sum_{u \in V} -f_{uv} & \le & 0 & \text{ for each } v \in V - \{s, t\} \\ f_{uv} & \ge & 0 & \text{ for each } u, v \in V \end{array} $$

Now, we can finally write down our $A$ and $b$. $A$ will be a $|V|^2 \times |V|^2 + 2|V| − 4$ matrix built from smaller matrices $A_1$ and $A_2$ which correspond to the three types of constraints that we have (of course, not counting the non-negativity constraints). We will let $g(u, v)$ be any bijective mapping from $V \times V$ to $[|V|^2]$. We'll also let $h$ be any bijection from $V - \{s, t\}$ to $[|V| - 2]$.

$$ A = \begin{pmatrix} A_1 \\ A_2 \\ -A_2 \end{pmatrix}, $$

where $A_1$ is defined as having its row $g(u, v)$ be all zeroes except for having the value $1$ at at the $g(u, v)$th entry. We define $A_2$ to have it's row $h(u)$ be equal to $1$ at all columns $j$ for which $j = g(v, u)$ for some $v$ and equal to $-1$ at all columns $j$ for which $j = g(u, v)$ for some $v$. Lastly, we mention that $b$ is defined as having it's $j$th entry be equal to $c(u, v)$ if $j = g(u, v)$ and zero if $j > |V|^2$.

Now that we have placed the linear program in standard form, we can take its dual. We want to minimize $\sum_{i = 1}^{|V|^2 + 2|V| - 2} b_iy_i$ given the constraints that all the $y$ values are non-negative, and $A^{\text T} y \ge c$.

29.4-4

Write down the dual of the minimum-cost-flow linear program, as given in lines $\text{(29.51)}$–$\text{(29.52)}$ on page 862. Explain how to interpret this problem in terms of graphs and flows.

First we need to put the linear programming problem into standard form, as follows:

$$ \begin{array}{lrcrl} \text{maximize} & \sum_{(u, v) \in E} -a(u, v) f_{uv} \\ \text{subject to} & \\ & f_{uv} & \le & c(u, v) & \text{ for each } u, v \in V \\ & \sum_{v \in V} f_{vu} - \sum_{v \in V} f_{uv} & \le & 0 & \text{ for each } u \in V - \{s, t\} \\ & \sum_{v \in V} f_{uv} - \sum_{v \in V} f_{vu} & \le & 0 & \text{ for each } u \in V - \{s, t\} \\ & \sum_{v \in V} f_{sv} - \sum_{v \in V} f_{vs} & \le & d \\ & \sum_{v \in V} f_{vs} - \sum_{v \in V} f_{sv} & \le & -d \\ & f_{uv} & \ge & 0 & . \end{array} $$

We now formulate the dual problem. Let the vertices be denoted $v_1, v_2, \dots, v_n, s, t$ and the edges be $e_1, e_2, \dots, e_k$. Then we have $b_i = c(e_i)$ for $1 \le i \le k$, $b_i = 0$ for $k + 1 \le i \le k + 2n$, $b_{k + 2n + 1} = d$, and $b_{k + 2n + 2} = −d$. We also have $c_i = −a(e_i)$ for $1 \le i \le k$. For notation, let $j.left$ denote the tail of edge $e_j$ and $j.right$ denote the head. Let $\chi_s(e_j) = 1$ if $e_j$ enters $s$, set it equal to $-1$ if $e_j$ leaves $s$, and set it equal to $0$ if $e_j$ is not incident with $s$. The dual problem is:

$$ \begin{array}{ll} \text{minimize} & \sum_{i = 1}^k c(e_j)y_i + dy_{k + 2n + 1} - dy_{k + 2n + 2} \\ \text{subject to} & \\ & y_j + y_{k + e_j.right} - y_{k + j.left} - y_{k + n + e_j.right} + y_{k + n + e_j.left} - \chi_s(e_j) y_{k + 2n + 1} + \chi_s(e_j) y_{k + 2n + 2} \ge -a(e_j), \end{array} $$

where $j$ runs between $1$ and $k$. There is one constraint equation for each edge $e_j$.

29.4-5

Show that the dual of the dual of a linear program is the primal linear program.

Suppose that our original linear program is in standard form for some $A$, $b$, $c$. Then, the dual of this is to minimize $\sum_{i = 1}^m b_iy_i$ subject to $A^{\text T} y \ge c$ This can be rewritten as wanting to maximize $\sum_{i = 1}^m (−b_i)y_i$ subject to $(−A)^{\text T} y \le −c$. Since this is a standard form, we can take its dual easily, it is minimize $\sum_{j = 1}^n (−c_j)x_j$ subject to $(−A)x \ge −b$. This is the same as minimizing $\sum_{j = 1}^n c_jx_j$ subject to $Ax \le b$, which was the original linear program.

29.4-6

Which result from Chapter 26 can be interpreted as weak duality for the maximum-flow problem?

Corollary 26.5 from Chapter 26 can be interpreted as weak duality.