Linear Programming
Spring 2020

TakeHome Midterm Exam, Thursday, March 26, 2020.
Due: Noon, Monday, March 30, 2020.
Scan in a pdf version of your solutions and upload to LMS.

Please do all four problems. Show all work. You may use any result from class, the homeworks, or the texts, except where stated.

Scan in a pdf version of your solutions and upload to LMS. You can alternatively write your solutions in LaTeX. Include your name in the name of any file you submit.

I will have WebEx office hours on Thursday from 1-2pm and on Friday from 11am-1pm.

Q1       /20

Q2       /20

Q3       /20

Q4       /40

Total      /100
  1. (20 points; each point is worth 5 points) Let g n, h m, and H m×n. Assume rank(H) = m. We look at the LP
    minz ∈ℝn    gTz

subject to  Hz   =   h
              z      free

    1. Is the LP feasible?
    2. Express the LP in an equivalent form min{cT x : Ax = b,x 0}. Show that if this problem has a finite optimal value then it has an unbounded set of optimal solutions.
    3. The dual problem is then max{bT y : AT y c}. Does there exist a feasible dual solution y with (AT y) i < ci for some component i?
    4. What must g, h, and H satisfy for (1) to have a finite optimal value? What can you say about the set of optimal solutions to (1) in this case?


    1. Yes, since H has full row rank, so the system of equations Hx = h is consistent.
    2.                [     ]T
minx ∈ℝ2n          g    x
                 - g
            [          ]
subject to    H   - H   x  =   h
                        x  ≥   0

      Assume x* is optimal. Let

                     [   ]
         *       e
x(λ) := x  + λ   e

      where e is the vector of ones in n. Then x(λ) is feasible in the modified LP for any λ 0, and cT x(λ) = cT x*. So the modified problem has an unbounded set of optimal solutions.

    3. Dual problem:
maxy ∈ℝm      b  y
subject to   HT  y  ≤  g
            - HT y  ≤  - g

      The dual constraints imply HT y = g, so NO, no dual feasible solution satisfying the given condition exists.

    4. The primal problem is always feasible. So either it is unbounded or has a finite optimal value. It has a finite optimal value if and only if the dual is feasible, that is, if and only if there exists y with HT y = g, that is, if and only if g is in the row space of H. In this case, every feasible solution has exactly the same value.
  2. (20 points) The stochastic program
    minx        cTx  +   E ξ [Q(x, ξ)]
subject to   Ax  =   b
              x  ≥   0

    has second stage cost

    Q(x,ξ ) = min         qT y
          subject to  W  y  =  h (ξ ) - T (ξ)x
                         y  ≥  0

    Assume all matrices and vectors are dimensioned appropriately. In class, we discussed solving (2) using the L-shaped decomposition method. In class, we only considered the case where the problem has complete recourse, so the second stage problem (3) is feasible for any x feasible in (2).

    How can the method be modified if the assumption of complete recourse does not hold? (Assume the dual LP to the subproblem (3) is feasible.)


    In the L-shaped method, we choose a first stage decision x then solve the dual of the second stage problem in each scenario to find πs, and then add the constraint

            ∑S                                  ( ∑S              )T
Q (x ) ≥     p (h(ξs) - T (ξs)x)Tπs = Q (x) -     p (T (ξs)T πs)   (x - x).
             s                                    s
        s=1                                   s=1

    If the first stage decision is infeasible then there exists a scenario ξs where the dual is unbounded. The dual is

    max         (h(ξs) - T(ξs)x)T π
    π                       T
subject to                W   π  ≤   q
                              π      free

    Hence there exists a dual ray π with WT π 0 and     s       s
(h(ξ ) - T(ξ )x) T π > 0. This π is always a ray, and the dual subproblem will be unbounded for any x satisfying (h(ξs) - T(ξs)x) T π > 0. In other words, any x satisfying (h(ξs) - T(ξs)x) T π > 0 will be infeasible in scenario ξs. Thus, if we determine that x is infeasible in some scenario ξs with dual ray π, we add the constraint

        s       s   T
(h (ξ ) - T (ξ )x) π ≤ 0

    to the Master Problem. Equivalently,

      T   s         s
π  T (ξ )x ≥  h(ξ ).

  3. (20 points) The ampl model file midterm20q3.mod and run file generate a random feasible linear program of the form
    minx ∈ℝn    cTx

subject to  Ax   ≥   b
              x  ≥   0

    with m = 10 and n = 30. The seed is contained in the data file, so choose a random seed and generate an LP. Note that cj = 1 for all j, and bi = j=1n(A ij - 1) for all i. We consider the robust LP model

    minx        cTx
subject to  ∑n    aijxj -  ∑     ˆaijxj ≥  bi ∀ |Si| ≤ Γ i,∀i
              j=1           j∈Si
            x ≥ 0

    where ij = 1 for all i, j, and Γi = 15 for all i = 1,, 10. Solve (5). In addition to your optimal x and optimal value, submit your seed, and also submit a data file containing A.

    Note: You don’t need to use AMPL to solve the robust problem, you’re welcome to use a different LP solver. You will need to run AMPL to generate the data file using the command

    ampl: model;

    This command will display the A matrix, which you could copy and paste into another solver. The run command also generates a data file containing A, which you can email to me: please put your name in the title of the file.

    (If you don’t even want to use AMPL to generate the data, ensure you generate an instance in the same way, and submit your A matrix using exactly the formatting indicated in the run file.)


    Solve the LP

minx,y,w    ∑n                  ∑n    c x
subject to     j=1 aijxj - Γ iyi -   j=1wij  ≥   bi for i = 1,...,m
                         ˆaijxj - yi - wij ≤   0  for i = 1,...,m, j = 1,...,n

                                  x,y,w   ≥   0

    where each ij = 1. The optimal value is probably in the mid-20s. The non-robust version probably has an optimal value in the high teens. The ampl model and run files can be found on LMS and the course webpage.

  4. (40 points. Parts (a)–(f) are worth 5 points each, part (g) is worth 10 points.) Consider the standard form linear program
                n     T
z :=   minx∈ℝ     c  x
      subject to  Ax   =  b
                    x  ≥  0

    where A m×n and rank(A) = m, and b and c are dimensioned appropriately and c has at least one nonzero component. For any nonnegative scalar parameters μ and ν, we can set up a relaxation of (6):

                                 μ                      ν∑ n
z(μ, ν) = minnf (x) := cT x +--(Ax  - b)T(Ax  - b) + --   (min {xi,0})2
          x∈ℝ                2                      2 i=1

    1. Show that the optimal value of (7) provides a lower bound for the optimal value of (6).
    2. Let ˆx be an optimal solution to (7). Show that cT xˆ < z, the optimal value for (6).
    3. The function f(x) is convex and differentiable with gradient
∇f (x) = c + μA  (Ax -  b) + νt


        0  if xi ≥ 0
ti =   xi  if xi ≤ 0   for i = 1,...,n.

      Any minimizer of f(x) must satisfy f(x) = 0. Show that if x is a minimizer of f(x) then x is infeasible in (6).

    4. Let x satisfy f(x) = 0. Construct a dual feasible solution y to (6), and hence find a lower bound z(y) on the optimal value of (6).
    5. Let x be a solution to (6). Express z(μ,ν) in terms of cT x and z(y) from part 4d.
    6. Let x minimize f(x). We have constructed three lower bounds on the optimal value of 6, namely cT x, f(x), and z(y). Which one of these is largest?
    7. Solve 7 for the LP
      minx ∈ℝ2    2x1  +    x2
subject to   x1  +  2x2   =  4
                  x1, x2  ≥  0

      for a generic μ > 0, ν > 0. What is the dual solution you obtain using the construction of part 4d? (Hint: the optimal solution has x1 < 0, x2 > 0.)


    1. We have three cases:
      • (6) is infeasible: Then z = +, so z(μ,nu) must be a lower bound.
      • (6) is unbounded: Then there exists a ray d with Ad = 0, d 0, and cT d < 0, and a feasible point x. Then for any α 0, we have
f (x + αd) = c (x + αd ) →  - ∞

        as α →∞. Hence, we get z(μ,ν) = -∞ for any μν 0.

      • (6) has an optimal solution x: Then
        z(μ,ν) ≤ f(x ) = cT x = z,

        as required.

    2. We have
cT ˆx  ≤  cT ˆx + μ(A ˆx - b)T(Aˆx - b) + ν   n  (min {ˆxi,0})2
                2                     2   i=1
                    since μ,ν ≥ 0
      =  f (ˆx)      from the de finition of f(x)

      =  z (μ, ν)    since ˆx solves (7)
      ≤  z          from part (a).

      We need to show this is a strict inequality. We assume it is an equality and derive a contradiction.

      Note that we have equality in the first inequality only if Aˆx = b and ˆx 0. Pick a component j with cj0. Let ej denote the jth unit vector and let aj denote the jth column of A. Define

      x (ϵ) = ˆx - ϵc e
             j j

      for ϵ 0. Note that

                            2   μϵ22     2   ν               2
f (x(ϵ)) =   f(ˆx) - ϵcj + -2-cj||aj||2 + 2 (min {xj(ϵ),0})
                      2   μϵ22     2   νϵ2-2
         ≤   f(ˆx) - ϵcj +  2(cj||aj||2 +  2 cj )
         =   f(ˆx) - ϵc2j + ϵ2 μc2j||aj||22 + νc2j
                             2           2
         <   f(ˆx)   for small positive ϵ.

      Hence xˆ does not minimize (7), a contradiction.

    3. Let x be a minimizer of (7). Assume x is feasible in (6), so Ax = b and x 0. Then f(x) = c0, so x is not a minimizer.
    4. Let y = μ(b - AT x). Since f(x) = 0, we have dual slacks
      c - AT y = c + μAT (A x - b) = ∇f (x) - νt = -  νt ≥ 0

      from the definition of t. Hence, the constructed y is dual feasible. We get a lower bound of

      z(y) = bTy =  μbT(b - Ax).

    5. We have
z(μ,ν ) =   cTx + μ (Ax - b)T(A x - b) + ν   ni=1 (min{ xi,0 })2
            1      21   (    μ           2)    μ              ν∑n               2
        =   2cTx+  2xT  c + 2AT (Ax- b)  -  2bT(A x - b) + 2  i=1 (min {xi,0} )
            1 T     1 T                 μ T            ν∑       2
        =   2c x+  2x∑ (∇f (x) - νt) + 2b (b∑ - A x) + 2   xi<0 xi
        =   12cTx-  12ν   x<0 x2i + 12bTy +  12ν   x<0 x2i
            1 T     1     i                    i
        =   2c x+  2z(y).

    6. From the proof of part (b), we have cT x z(μ,ν). Thus we have
      cTx ≤ z(μ, ν) ≤ z(y).

    7. The point x solves (7) if and only if f(x) = 0. From the hint and from (8), we must have
      [   ]             [                                  ]
  0                 2  +   μ (x1 + 2x2 - 4)  +   νx1
  0   = ∇f  (x) =   1  +   2μ(x  + 2x  - 4)
                               1      2

      From the second line, we have

      x +  2x -  4 = -  -1-
 1     2          2μ

      and so from the first line we have

x1 =  -  --.

      It follows from (10) that

                1     3
x2 = 2 - --- + ---.
         4μ    4ν

      It follows from (10) that

      y = μ(b - Ax) = 1.

      Note that the dual problem is

      maxy ∈ℝ    4y
subject to    y  ≤  2
           2y   ≤  1

      which has optimal solution y = 1