MATP6640/DSES6770 Linear Programming, Homework 3.
Solutions

Due: 11.59pm on Friday, February 18, 2022 on LMS.
10% penalty for each day late.

Dantzig-Wolfe decomposition solves the linear programming problem

min   cTx
s.t.  Ax   =   b                                          (P )
        x  ∈   X := {x  ∈ IRn : Hx =  h,x ≥ 0 }

where X is a polyhedron and A is m × n. The procedure solves subproblems of the form

        T    T
min   (c  - π  A)x
s.t.        x       ∈   X            (SP (π))

where (π,σ) IRm+1 is the current dual solution to the Master Problem. Questions 3 and 4 concern Dantzig-Wolfe decomposition.

  1. Let Q be the polyhedron
                          [   ]      [   ]     [   ]      [   ]
Q  :=  {x ∈ IR2 :  x =   1   y1 +   2  y2 +   2   z1 +   1   z2,
                        3          1         1          1

                  y1 ≥ 0,y2 ≥ 0,z1 ≥ 0,z2 ≥ 0,y1 + y2 = 1}.

    Use the proof of the affine Weyl theorem (so use Fourier-Motzkin elimination explicitly) to construct constraints Ax b such that

                 2
Q =  {x ∈ IR  : Ax ≥  b}.

    (Note that the y variables correspond to the extreme points and the z variables correspond to the rays.)

    Solution:

    The initial system of linear equalities and inequalities is

    x1 - y1 - 2y2 - 2z1 - z2 = 0 (1a)
    x2 - 3y1 - y2 - z1 - z2 = 0 (1b)
    y1 + y2 = 1 (1c)
    y1 0 (1d)
    y2 0 (1e)
    z1 0 (1f)
    z2 0 (1g)

    Eliminating z2 by taking (1b)-(1a) and (1g)+(1a) gives the system

    - x1 + x2 - 2y1 + y2 + z1 = 0 (2a)
    y1 + y2 = 1 (2b)
    y1 0 (2c)
    y2 0 (2d)
    z1 0 (2e)
    x1 - y1 - 2y2 - 2z1 0 (2f)

    Eliminating z1 by taking (2e)-(2a) and (2f)+2(2a) gives the system

    y1 + y2 = 1 (3a)
    y1 0 (3b)
    y2 0 (3c)
    x1 - x2 + 2y1 - y2 0 (3d)
    - x1 + 2x2 - 5y1 - 0 (3e)

    Eliminating y2 by taking (3c)-(3a) and (3d)+(3a) gives the system

    y1 0 (4a)
    - y1 - 1 (4b)
    x1 - x2 + 3y1 1 (4c)
    - x1 + 2x2 - 5y1 0 (4d)

    The variable y1 only appears in inequalities, and with a mixture of signs, so we need to take combinations of inequalities:

    (4a), (4b) : 1 y1 0                                                                                                                        = ⇒ 1 0 (5a)
    (4a), (4d) : - 1-
5x1 + 2-
5x2 y1 0                                                                                                                        = ⇒ - x1 + 2x2 0 (5b)
    (4b), (4c) : 1 y1 -                                                      1
                                                      --
                                                      3x1 +                                                                                 1
                                                                                --
                                                                                3x2 +                                                                                                            1
                                                                                                           --
                                                                                                           3                                                                                                                        = ⇒ x1 - x2 - 2 (5c)
    (4c), (4d) : - 1-
5x1 + 2-
5x2 y1 -                                                      1-
                                                      3x1 +                                                                                 1-
                                                                                3x2 +                                                                                                            1-
                                                                                                           3                                                                                                                        = ⇒ 2x1 + x2 5 (5d)

    Thus,

    Q = {x ∈  IR2 : - x + 2x  ≥ 0, x - x  ≥  - 2, 2x + x ≥  5}.
                  1     2       1    2         1    2

  2. Suppose we are given the extreme points and extreme rays of a pointed polyhedron P IRn. Let ˆx IRn. Construct a linear programming problem whose solution provides us with an inequality gT x > gT xˆ that is satisfied by all x P and violated by xˆ, or allows us to conclude that no such inequality exists. What is the dual of your LP? Give an interpretation of the dual LP. (Such an inequality defines a separating hyperplane that separates ˆx from P. Note that the variables in the LP will include g.)

    Solution:

    Let the extreme points of P be {xj : j J}. Let the extreme rays of P be {dk : k K}. The LP is

    maxg ∈IRn,t∈IR                    t
subject to      - gT (xj - ˆx) +  t  ≤   0  ∀j ∈ J        (P )
                     - gT dk        ≤   0  ∀k ∈ K

    Note that g = 0, t = 0 is always feasible in (P). If the optimal value is strictly positive then it is unbounded, because this is a conic LP: all the right hand side terms are zero. If the optimal value is unbounded then any ray (g,t) with t > 0 gives g that defines a separating hyperplane.

    The dual problem is

    maxy,w        ∑        j    0      ∑         k
subject to  -    j∈J yj(x∑ - ˆx)  -     k∈K wkd    =  0       (D )
                        j∈J yj                  =  1
                           y,               w   ≥  0

    The first constraint in (D) can be written as

    ∑         ∑           ∑
    y xj +    w  dk =     y ˆx = ˆx,
     j          k          j
j∈J       k∈K          j∈J

    from the second constraint in (D). Thus, the dual problem searches for a convex combination of the extreme points and a nonnegative combination of the extreme rays that gives the point ˆx.

  3. When using Dantzig-Wolfe decomposition, assume the current subproblem has an optimal solution x with value v. Can you give a lower bound on the optimal value of (P)? What does your lower bound become if the current dual solution (π,σ) to the master problem is dual feasible?

    Solution: The dual to (P) is

    maxw,z       bTw   +   hT z
subject to  AT w   +  HT  z  ≤  c         (D )

              w,          z     free

    The dual to the subproblem (SP(π) is

    maxt         hTt
subject to  HT t  ≤   c - AT π      (DSP  (π))
               t      free

    which has optimal value hT t = v from strong duality. We get a feasible solution to (D) by setting w = π, z = t, with value bT π + hT t = bT π + v. Thus, we have the valid lower bound bT π + v.

    If the current dual solution (π,σ) to the master problem is dual feasible then v = σ and the lower bound becomes the optimal value bT π + σ.

  4. Suppose (P) has been solved using Dantzig-Wolfe decomposition. How would you find the optimal dual solution to the original problem (P)?

    Solution: We look again at the problems (D) and (DSP(π)) from the solution to Question 3. If (π,σ) is optimal for the dual of the Master Problem then the dual solution given in Question 3 is optimal for (D): it is feasible from the argument in Question 3 and it has value equal to the optimal value bT π + σ.

  5. Consider the standard form polyhedron P = {x IRn : Ax = b,x 0} where b IRm and A IRm×n of rank m. Prove or give counterexamples to the following two statements:
    1. If n = m + 1 then P has at most two basic feasible solutions.
    2. Consider the problem of minimizing max{cT x,dT x} over P, where c,d IRn. If this problem has an optimal solution, it has an optimal solution that is an extreme point of P.

    Solution:

    1. True: The dimension of the affine space {x IRn : Ax = b} is n - m = 1, so P is a line segment, so it has at most two extreme points.
    2. False: Consider the problem
      minx ∈IR2   max {x1,x2}
subject to  x1  +    x2  =   2
            x1,      x2  ≥   0

      The unique optimal solution to this problem is x* = (1, 1), which is not a BFS.

  6. The Project:
    Along with your solutions to this homework, hand in a brief description of what you would like to do for the project part of this course. Your project can be one of the following:
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj