Linear Programming
Spring 2016

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.

Q1       /30

Q2       /35

Q3       /35

Total      /100
  1. (30 points; each part is worth 10 points)
    Let A be an n × n matrix satisfying:

    Show the following:

    1. Let y n. Assume the smallest component of y is y k, so yk yi for i = 1,,n. Show i=1na ikyi 0.
    2. Show the linear program
      maxy           0
subject to  AT y  ≤  - e
               y  ∈  ℝn

      is infeasible, where e denotes the vector of ones.

    3. What can you say about the set {x n : Ax = 0,x 0}?
  2. (35 points)
    In the single commodity network flow problem in the figure, nodes s and t are supply nodes and nodes u and v are demand nodes. The supplies available are bs = 3 and bt = 2. The demands are du = 1 and dv = 4. The unit shipping costs for each edge are indicated in the figure.

    An initial basic feasible solution can be obtained by taking xsu, xut, and xtv to be basic, and xst, xuv to be nonbasic.

    1. (5 points) What is the initial basic feasible solution?
    2. (15 points) What are the primal and dual linear programs? Find a dual solution that satisfies complementary slackness. Show your dual solution is not dual feasible.
    3. (15 points) Make a simplex pivot to improve your primal solution. What is the updated dual solution? Is the new solution optimal?
  3. (35 points)
    The numbers on the edges in the following graph represent the probability of failure of an edge. Edges fail independently of one another.

    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,

    Probability {every edge in cutset fails} ≤ 0.01.

    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

    P ∪ Q  = {s,t,u,v,w },  P  ∩ Q =  ∅,  s ∈ P,   t ∈ Q.

    Two possible partitions are:

    We introduce variables

         {  1  if edge e is reinforced
xe =
        0  otherwise.

    In order to ensure the solution x satisfies the constraint (1) for the cutset given by P1 and Q1, we can impose the constraint

    xsu + xsv ≥ 1.

    Similarly, we can impose the constraint

    xvt + xwt ≥ 1

    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:

    minx ∈ℝ7    3xsu  +   2xsv  +  7xuv   +  6xuw   +  7xvw   +   5xvt +   3xwt
subject to   xsu  +    xsv                                                   ≥   1
                                                               xvt +    xwt  ≥   1
              xe  ≥      0  for all edges e

    1. (5 points) Show that the solution to the initial relaxation is xsv = xwt = 1, with all other xe = 0.
    2. (10 points) Find a cutset that leads to a valid inequality that is violated by the solution in part 3a.
    3. (5 points) Show that xsu = xwt = 1 with all other xe = 0 is feasible after the new valid inequality is added to (4).
    4. (15 points) Construct the dual LP to the new problem obtained by adding the constraint to (4). Find a dual solution that satisfies complementary slackness. Is your solution optimal?