CS 4301 — Special Topics in Computer Science: Optimization, Homework 2
| Primal | Dual | Primal | Dual |
|---|---|---|---|
| — | — | ||
| — | — | ||
1. Let and . In class, we saw that the primal LP instance
has as its dual
Hint: Write an equivalent instance to the dual LP that it looks like the primal’s standard form. To do so, add pairs of inequalities that together form the equality constraints and multiply the objective by −1 so it becomes a maximization. Then, verify the dual of your rewritten instance is equivalent to the primal LP.
First start with the dual LP. In the dual
To turn the inequalities into equalities simply convert each into and . For the objective, minimizing is the same as maximizing (i.e ).
Dualizing this, we get
which can be rewritten as
which is a standard form for the primal LP (i.e. they are equivalent)
Let be a bipartite graph with no isolated (degree-0) vertices. An edge cover of G is a number of edges such that each vertex in is incident to at least one edge of C. The following integer programming instance captures the minimum cardinality edge cover problem in .
Recall from our discussion on bipartite matching that constraint matrix above is a TUM and therefore an optimal solution to the above integer program is also an optimal solution to the following linear programming instance.
Using the chart on the first page, derive the dual of the linear programming instance above
3
for vertex-incidence matrix M we want
since each column of M represents an edge of the graph, and
since you must have 0 or more of each vertex.
An independent set in G is a subset of vertices such that no two vertices in share an edge. What problem does an integral solution to the dual LP solve? (Again, the constraint matrix is a TUM, so there will always be some optimal solution that is integral.)
The dual LP finds the maximum independent set for the graph. This is because we are maximizing the number of vertices selected, each of the endpoints of each edge can only be used once (i.e. there are no adjacent vertices).
Use strong duality and the above observations to explain the relationship between edge cover sizes and independent set sizes in bipartite graphs.
By strong duality, the solution to the edge cover size (i.e. the number of edges taken in the minimum edge cover) and the independent set size (the number of vertices in the maximal independent set) are the same. According to strong duality, these two objective values should be the same (and as expected, these are our objectives).
So far, we have assumed has no isolated vertices. Unfortunately, the strong duality argument above no longer applies if there is even a single isolated vertex, because neither the primal nor dual LP have a finite optimal solution. Concisely explain why the primal LP has no finite optimal solution by referencing only the primal LP. Similarly, explain why the dual LP has no finite optimal solution by referencing only the dual LP.
Primal
For the primal, if there are any isolated vertices then we must argue that the LP is empty. Because for that vertex , the Integer Programming instance , which violates the second set of constraints. This means that no solution to the LP contains the optimal solution, which implies that the LP does not contain a finite optimal solution.
Dual
For the dual, if there are any isolated vertices, then can be increased indefinitely for an isolated vertex , since it is not involved in the second inequality. This implies that the LP has no finite optimal solution, since it is unbounded.