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

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

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

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

(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) : - x1 + x2 ≥ y1 ≥ 0 - x1 + 2x2 ≥ 0 (5b) (4b), (4c) : 1 ≥ y1 ≥ -x1 + x2 + x1 - x2 ≥ - 2 (5c) (4c), (4d) : - x1 + x2 ≥ y1 ≥ -x1 + x2 + 2x1 + x2 ≥ 5 (5d)

Thus,

2. Suppose we are given the extreme points and extreme rays of a pointed polyhedron P IRn. Let IRn. Construct a linear programming problem whose solution provides us with an inequality gT x > gT that is satisfied by all x P and violated by , 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 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

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

The first constraint in (D) can be written as

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 .

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

The dual to the subproblem (SP(π) is

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

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:
• a topic arising in your research that fits well with the topics covered in the course. You would work on your own on such a project.
• another project you suggest or I suggest. You can work in groups of up to three people on such a project. All group members should contribute equally to the project. Each individual should turn in a one-page description of their contribution to the project along with the group report.
 John Mitchell Amos Eaton 325 x6915. mitchj at rpi dot edu Office hours: Thursday 11am–1pm., on webex https://rensselaer.webex.com/meet/mitchj