MIT 6.1220 — Lecture 12

Linear Programming (Part II)

Here's an example of this duality.

Maximize x1+2x2 given −3x1+2x2≤10 and x1+x2≤15 and x1,x2≥0.Minimize 10y1+15y2 given −3y1+y2≥1 and 2y1+y2≥2 and y1,y2≥0.\begin{align*}\text{Maximize } x_1 + 2x_2 \text{ given } -3x_1 + 2x_2 \leq 10 \text{ and } x_1 + x_2 \leq 15 \text{ and } x_1, x_2 \geq 0. \\ \text{Minimize } 10y_1 + 15y_2 \text{ given } -3y_1 + y_2 \geq 1 \text{ and } 2y_1 + y_2 \geq 2 \text{ and } y_1, y_2 \geq 0.\end{align*}

More generally, the dual looks like this:

Claim. If both linear programs are feasible, the following is true.

max⁡{c⊤x∣Ax≤b and x≥0}=min⁡{b⊤y∣A⊤y≥c and y≥0}\max\{ c^{\top} x \mid A x \leq b \text{ and } x \geq 0 \} = \min\{ b^{\top}y \mid A^{\top}y \geq c \text{ and } y \geq 0 \}

Proof: To show weak duality, just write c⊤x=x⊤c≤x⊤A⊤y=(Ax)⊤y≤b⊤yc^{\top}x = x^{\top}c \leq x^{\top}A^{\top}y = (Ax)^{\top}y \leq b^{\top}y.

To show strong duality, ehhhh it's like vibe-ly obvious, but proving it requires Farkas' Lemma.   ■\blacksquare

Some jargon dumping:

Remark. It is possible for both an LP and its dual to be infeasible. Try to construct one!

Example. More generally, we might want to find the dual of more complicated linear programs.

Maximize x1−x2+2x3 given −x1+3x2≤−3 and x1+3x3≥2 and x2+x3=7 and x1,x2≥0.\text{Maximize } x_1 - x_2 + 2x_3 \text{ given } -x_1 + 3x_2 \leq -3 \text{ and } x_1 + 3x_3 \geq 2 \text{ and } x_2 + x_3 = 7 \text{ and } x_1, x_2 \geq 0.

Take some time to convince yourself that the dual is the following.

Minimize −3y1+2y2+7y3 given −y1+y2≥1 and 3y1+y3≥−1 and 3y2+y3=2 and y1≥0,y2≤0.\text{Minimize } -3y_1 + 2y_2 + 7y_3 \text{ given } -y_1 + y_2 \geq 1 \text{ and } 3y_1 + y_3 \geq -1 \text{ and } 3y_2 + y_3 = 2 \text{ and } y_1 \geq 0, y_2 \leq 0.

Be very careful about the choices of {≥,≤,=}\{\geq, \leq, =\}.

Remark. Given an optimal solution to the primal, we can find an optimal solution to the dual. We do this by identifying the constraints in the primal that are slacked, ignoring those, and setting everything else to be tight. This is DCW-Equality.

We can use LP to solve the MST problem. Give indicator variables xex_e for all edges with xe≥0x_e \geq 0.

Minimize ∑e∈Ew(e)xe  given  ∑e crosses Πxe≥∣Π∣−1 for all partitions Π of V and xe≥0.\text{Minimize } \sum_{e \in E} w(e) x_e ~ \text{ given } ~ \sum_{e \text{ crosses } \Pi} x_e \geq |\Pi| - 1 \text{ for all partitions } \Pi \text{ of } V \text{ and } x_e \geq 0.

The optimal value is at most the weight of an MST. The hope is that the optimal solution uses xe∈{0,1}x_e \in \{0, 1\}, in which case the optimal solution is an MST. Note that the dual of this problem looks like:

Maximize ∑partitions Π(∣Π∣−1)yΠ  given  ∑Π : e crosses ΠyΠ≤w(e) for all e∈E and yΠ≥0.\text{Maximize } \sum_{\text{partitions } \Pi} (|\Pi| - 1)y_{\Pi} ~ \text{ given } ~ \sum_{\Pi \, : \, e \text{ crosses } \Pi} y_{\Pi} \leq w(e) \text{ for all } e \in E \text{ and } y_{\Pi} \geq 0.

(We did not finish this example in lecture.)