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 (π,σ) ∈ IR^m+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.)

2. Suppose we are given the extreme points and extreme rays of a pointed polyhedron P ⊆ IRⁿ. Let ∈ IRⁿ. Construct a linear programming problem whose solution provides us with an inequality g^T x > g^T 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.)
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?
4. Suppose (P) has been solved using Dantzig-Wolfe decomposition. How would you find the optimal dual solution to the original problem (P)?
5. Consider the standard form polyhedron P = {x ∈ IRⁿ : Ax = b,x ≥ 0} where b ∈ IR^m and A ∈ IR^m×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{c^T x,d^T x} over P, where c,d ∈ IRⁿ. If this problem has an optimal solution, it has an optimal solution that is an extreme point of P.
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.