[go: up one dir, main page]
Scribd
Upload
29 views1 page

Exercise 10

The document outlines exercises related to linear and integer programming for a course at Technische Universität Berlin. It includes problems on maximizing a given objective function under specific constraints, exploring the convex hull of feasible sets, and demonstrating the importance of rational polyhedra. Additionally, it discusses the construction of polyhedra with varying Chvátal ranks.

Uploaded by

drbspacemusic
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views1 page

Exercise 10

The document outlines exercises related to linear and integer programming for a course at Technische Universität Berlin. It includes problems on maximizing a given objective function under specific constraints, exploring the convex hull of feasible sets, and demonstrating the importance of rational polyhedra. Additionally, it discusses the construction of polyhedra with varying Chvátal ranks.

Uploaded by

drbspacemusic
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Technische Universität Berlin ADM II – Linear and Integer Programming

Institut für Mathematik Winter Term 2010/2011

Prof. Dr. Rolf H. Möhring Christoph Hansknecht


Dr. Sebastian Stiller

10. Exercise
Due: Friday, 20.1.2012, 10.00h sharp before the first lecture.

Exercise 30 10 points

Consider the integer programming problem

maximize x1 + 2x2
subject to −3x1 + 4x2 ≤ 4
3x1 + 2x2 ≤ 11
2x1 − x2 ≤ 5
x1 , x2 ≥0
x1 , x2 integer

Sketch the feasible set and use the figure to answer the following questions:
1. What is the optimal cost of the linear programming relaxation? What is the optimal cost of
the integer programming problem and how large is the gap between the two values?

2. What is the convex hull of the feasible set of the integer program. Give the inequalities that
forms the polyhedra.
3. Compute and illustrate the first Chvátal closure in this example. What is the optimal solution
of the new linear program?

Exercise 31 5 points

In this exercise you will show that dealing with rational polyhedra is a very important assumption
for the theorems in the section 7.5.
√
(a) Let P := {(x1 , x2 ) ∈ R2 : x2 ≤ 2x1 }. Show that PI i.e. the convex hull of the all the integral
points in P does not describe a polyhedron.
√
(b) Let P := {(x1 , x2 ) ∈ R2 : x2 ≤ 2x1 , x1 ≥ 0}. Prove that P (t) = P 6= PI .

Exercise 32 5 points

The following claim provides an easy construction guidance for polyhedra with an arbitrarily
large Chvátal rank: Let P be the convex hull of three points in R2 , namely (0, 0), (0, 1) and (k, 21 ).
Prove that P (2k−1) 6= PI = P (2k) .

You might also like