Midterm Exam, Friday, April 8, 2016.
Please do all three problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.
Show the following:
is infeasible, where e denotes the vector of ones.
This problem is feasible (take x = 0), so it is unbounded. So there exists a nonzero x in the given set.
An initial basic feasible solution can be obtained by taking xsu, xut, and xtv to be basic, and xst, xuv to be nonbasic.
From complementary slackness, need y to satisfy
One solution is yv = 0, yt = 3, yu = 8, ys = 13. This violates the second and fourth dual constraints, each by one unit.
Largest possible value of Δ = 2, and edge (u,t) leaves the basis. Get new bfs as indicated in the figure:
From complementary slackness, need y to satisfy:
One solution is yv = 0, yt = 3, ys = 12, yu = 7, which is dual feasible. Therefore, the new bfs is primal optimal, and the given dual solution is dual optimal.
For a price, we can reinforce an edge so that its probability of failure drops to zero. We want to ensure that a path exists between s and t with high probability. More precisely, we want to ensure that, for each cutset,
A cutset consists of all edges leading from P to Q, where P and Q form a partition of the vertices with s ∈ P and t ∈ Q, so
Two possible partitions are:
We introduce variables
In order to ensure the solution x satisfies the constraint (1) for the cutset given by P1 and Q1, we can impose the constraint
Similarly, we can impose the constraint
corresponding to the other cutset. For a general graph, there may be a large number of possible cutsets, so we add the corresponding constraints as needed. The initial LP relaxation is as follows, where the objective function coefficients correspond to the costs of reinforcing a particular edge:
The product of the probabilities of failure of the three edges in the cutset is
so we must reinforce at least one edge in this cutset in order to satisfy constraint (1). This gives the valid constraint
which is violated by the solution given in part (a).
and the given solution is feasible in this LP, with value 6.
From complementary slackness, we need
This system has multiple solutions, including y = (2, 3, 1) and (1, 3, 2), both of which are feasible in the dual problem. Since we have primal and dual feasibility as well as complementary slackness, we are optimal.
The general set of dual optimal solutions has the form y = (1 + z, 3, 2 - z) for 0 ≤ z ≤ 1.