CS 4301 — Special Topics in Computer Science: Optimization, Homework 3
| Primal | Dual | Primal | Dual |
|---|---|---|---|
| — | — | ||
| — | — | ||
Let be a directed graph, and let and be set of lower and upper bounds on the arcs. A circulation in is a flow that satisfies conservation at all vertices, i.e., it is a function such that for all vertices . A circulation is called feasible for and if for all arcs . In other words, a feasible circulation is a point in the polyhedron where is the vertex-arc incidence matrix of the graph . Hoffman proved that a feasible circulation exists if and only if
- for all arcs and
- for all subsets , where is the set of arcs entering from outside and is the set of arcs leaving to the outside.
Use LP duality and the fact that M is totally unimodualar to prove Hoffman’s theorem.
Hint: Start by writing a primal LP that seeks a min-cost feasible circulation according to an arbitrary objective .
First start by writing down the LP. This is neither a maximization nor minimization problem, so assume an arbitrary objective
We are already given the polyhedron for this LP. This is totally unimodular.
If , this polyhedron is empty, proving the first part of Hoffman’s statement.
For each arc we must subtract (the dual variable associated with the lower bound for that arc) and add (the dual variable associated with the upper bound for that arc). We must also add the dual variable corresponding to the vertex which the arc is directed into, and subtract the dual variable corresponding to the vertex which the arc is directed from. Writing this more formally:
Assume for contradiction that there is a feasible circulation where there exists a subset of vertices with . W.l.o.g. take a minimal such subset . We must show that the LP is infeasible.
This LP is unbounded. For all vertices , you can set without violating a constraint by using the linear independence of . Because will be positive (by assumption), arbitrarily large values for can be chosen. This is a contradiction, since we assumed that the circulation was feasible. (In contrast, if the inequality were not true, then you would have to decrease for some arc in order to increase the value of the LP, which would be in the bounded direction. )
An easy proof for the second statement is as follows: For the subset of vertices , the flow cannot conserved if such a subset exists. Otherwise, if no such subset exists, then setting the value of the circulation to be the lower bound will result in a feasible circulation (since we know that this value will not cause any subsets where flow is not conserved to exist).
Use the existence and properties of Gomory-Hu trees to prove the following:
For any undirected graph with non-negative edge capacities , there is a pair of distinct vertices and an -minimum cut with one side consisting of a singleton vertex (either or ). (Such a pair of vertices is called a pendant pair.)
Consider the last two vertices contracted by the recursive phase of the computaion of the Gomory-Hu tree. Call these (the penultimate) and (the final). Because the cut seperating from the graph does not cross the -cut, in the next recursive step and is contracted with the rest of the graph, the set containing consists only of , i.e. that it is a singleton vertex. Thus, is a pendent pair.
Let be a graph such that for all vertices . There exists a pair of distinct vertices such that
Consider a pendant pair in . Assume w.l.o.g. that is the singleton vertex. For , since it is a singleton vertex, all of it’s adjacent edges must be removed in order to seperate it from the . Note here, that edges are by definition edge-disjoint paths (since it is not a multigraph). Thus, since , at least edges must be removed to disconnect from for that vertex (i.e. that ).
Consider the (primal) LP
The polyhedron described by the above LP has three vertices. What are they?
What is the optimal solution vector for the above LP?
. We can compute this manually easily by simply checking the sum of elements of each of the vertices.
Write the dual LP. Any system of (in)equalities equivalent to the “standard” form of the dual will be considered correct.
Let be your solution to part (b) and let
These are the optimal solutions, since