Combinatorial Algorithms
Spring 2015
MP Johnson

Problem Set 2
Due by email, 11:59pm, Saturday, May 2nd

You're free to work with a partner, but the solutions you submit must be written "in your own words."
  1. Facts about duality:
    1. Verify that the dual of the dual of an LP is the original LP.
    2. Verify that an LP being feasible and unbounded implies its dual is infeasible.

  2. When constructing the dual of an LP, we don't treat nonnegativity constraints ($x_j\ge0$) the way we treat other constraints. Why not? Or, what if we did treat them that way--introducing dual variables corresponding to them, etc.? (It couldn't hurt, could it?) Do this explicitly with a generic standard form LP ($\min \{cx : Ax \ge b, x \ge 0\}$, showing how the resulting "dual" compares to the normal dual, and explain why we don't do this.

  3. Here is an LP for the minimum edge cover problem, where the goal is to choose a minimum number of edges so that every node is covered (by at least one edge):

    $\min \sum x_{uv}$
    s.t.
    $\sum_u x_{uv} \ge 1 \quad \forall v$
    $x_{uv} \ge 0$

    1. Give the dual of this LP.
    2. What does this dual LP mean, assuming that in both the primal and dual problems the variables are "intended" to be 0/1? Try to figure out and describe in your own words what problem the dual LP is solving. (In order to see what's going on, it might help to draw a small example graph with, say, five nodes and a few edges and seeing what feasible solutions would look like, and what sort of solutions the objective is preferring.)

  4. Given is a standard-form LP $\min \{cx : Ax = b, x \ge 0\}$. The simplex method (see these figures: 1,2,3,4,5) invokes the optimality conditions that every reduced cost is nonnegative, i.e., $\bar c_j = c_j-z_j \ge 0$ for all non-basic $j$, where $z_j = c_B B^{-1}A_j = c_B \Lambda_j$ and the values of the tableau are transformed from $A$ to $\Lambda = B^{-1}A$ when we're at basis $B$. (In class I used $X$ and $x_{ij}$ for $\Lambda$ and $\lambda_{ij}$.) (Recall that column $\Lambda_j=B^{-1}A_j$ consists of weights by which column $A_j$ can be written as a linear combination of the basis columns, i.e., $A_j = \Lambda_j \cdot B = \sum_i \lambda_{ij} B_i$, and that $\bar c_j$ is the net change in the minimization objective resulting from increasing $x_j$ by 1 and the compensating decreases in the basic variables $x_i$.)
    1. Verify that we always have $\bar c_i=0$ for $i \in B$.
    2. Give an intuitive geometric interpretation of $\bar c_j<0$ as a statement about the change in objective as you move from the current vertex in a certain direction.
    3. Argue in terms of the geometry and linearity for why $\bar c \ge 0$ therefore implies optimality.

  5. Recall that we can also write $z_j = c_B B^{-1}A_j = \pi A_j$, where $\pi$ is the tableau's solution to the corresponding dual LP $\max \{b \pi : A^{T}\pi \le c\}$.
    1. Show that if $A_j=e_j$ (i.e., the column vector this is all 0s except for a 1 in component $j$, or column $j$ of an identity matrix), then $\bar c_j=c_j - \pi_j$.
    2. What does the condition $\bar c \ge 0$ have to do with the feasibility of $\pi$?
    3. Give the one-line proof of weak duality.
    4. Recall that the primal solution given by the tableau is $x_B = B^{-1}b$ (where $x_B$ is $x$ restricted to the columns $B$). What are the values, in terms of their respective objective functions, of the primal and dual solutions?
    5. Argue that therefore $x$ and $\pi$ are both optimal (thus proving strong duality).