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 (π,σ) ∈ IR^{m+1} is the current dual solution to the Master Problem. Questions 3 and 4
concern Dantzig-Wolfe decomposition.

- 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

x _{1}- y _{1}- 2y _{2}- 2z _{1}- z _{2}= 0 (1a) x _{2}- 3y _{1}- y _{2}- z _{1}- z _{2}= 0 (1b) y _{1}+ y _{2}= 1 (1c) y _{1}≥ 0 (1d) y _{2}≥ 0 (1e) z _{1}≥ 0 (1f) z _{2}≥ 0 (1g) Eliminating z

_{2}by taking (1b)-(1a) and (1g)+(1a) gives the system- x _{1}+ x _{2}- 2y _{1}+ y _{2}+ z _{1}= 0 (2a) y _{1}+ y _{2}= 1 (2b) y _{1}≥ 0 (2c) y _{2}≥ 0 (2d) z _{1}≥ 0 (2e) x _{1}- y _{1}- 2y _{2}- 2z _{1}≥ 0 (2f) Eliminating z

_{1}by taking (2e)-(2a) and (2f)+2(2a) gives the systemy _{1}+ y _{2}= 1 (3a) y _{1}≥ 0 (3b) y _{2}≥ 0 (3c) x _{1}- x _{2}+ 2y _{1}- y _{2}≥ 0 (3d) - x _{1}+ 2x _{2}- 5y _{1}- ≥ 0 (3e) Eliminating y

_{2}by taking (3c)-(3a) and (3d)+(3a) gives the systemy _{1}≥ 0 (4a) - y _{1}≥ - 1 (4b) x _{1}- x _{2}+ 3y _{1}≥ 1 (4c) - x _{1}+ 2x _{2}- 5y _{1}≥ 0 (4d) The variable y

_{1}only appears in inequalities, and with a mixture of signs, so we need to take combinations of inequalities:(4a), (4b) : 1 ≥ y _{1}≥ 0 1 ≥ 0 (5a) (4a), (4d) : - x _{1}+ x _{2}≥ y _{1}≥ 0 - x _{1}+ 2x _{2}≥ 0 (5b) (4b), (4c) : 1 ≥ y _{1}≥ -x _{1}+ x _{2}+ x _{1}- x _{2}≥ - 2 (5c) (4c), (4d) : - x _{1}+ x _{2}≥ y _{1}≥ -x _{1}+ x _{2}+ 2x _{1}+ x _{2}≥ 5 (5d) Thus,

- Suppose we are given the extreme points and extreme rays of a pointed polyhedron
P ⊆ IR
^{n}. Let ∈ IR^{n}. 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.)Solution:

Let the extreme points of P be {x

^{j}: j ∈ J}. Let the extreme rays of P be {d^{k}: k ∈ K}. The LP isNote 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 (, ) with > 0 gives 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 .

- When using Dantzig-Wolfe decomposition, assume the current subproblem has an optimal
solution 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 h

^{T }t = v from strong duality. We get a feasible solution to (D) by setting w = π, z = t, with value b^{T }π + h^{T }t = b^{T }π + v. Thus, we have the valid lower bound b^{T }π + v.If the current dual solution (π,σ) to the master problem is dual feasible then v = σ and the lower bound becomes the optimal value b

^{T }π + σ. - 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 b

^{T }π + σ. - Consider the standard form polyhedron P = {x ∈ IR
^{n}: 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:- If n = m + 1 then P has at most two basic feasible solutions.
- Consider the problem of minimizing max{c
^{T }x,d^{T }x} over P, where c,d ∈ IR^{n}. If this problem has an optimal solution, it has an optimal solution that is an extreme point of P.

Solution:

- True: The dimension of the affine space {x ∈ IR
^{n}: Ax = b} is n - m = 1, so P is a line segment, so it has at most two extreme points. - False: Consider the problem
The unique optimal solution to this problem is x

^{*}= (1, 1), which is not a BFS.

- 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 |