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

Exercise 12

The document outlines exercises for a linear and integer programming course at Technische Universität Berlin, focusing on polyhedra and matching polytopes. It includes specific problems related to decomposing a polyhedron, determining the existence of an optimum for a given linear program, and proving inequalities for a 2-matching polytope. Additionally, it discusses the conditions for a polyhedron to be full-dimensional and provides equivalences related to its properties.

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
24 views1 page

Exercise 12

The document outlines exercises for a linear and integer programming course at Technische Universität Berlin, focusing on polyhedra and matching polytopes. It includes specific problems related to decomposing a polyhedron, determining the existence of an optimum for a given linear program, and proving inequalities for a 2-matching polytope. Additionally, it discusses the conditions for a polyhedron to be full-dimensional and provides equivalences related to its properties.

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

12. Exercise
Due: Friday, 3.2.2012, 10.00h sharp before the first lecture.

Exercise 36 5 points

(a) Consider the polyhedron P (A, b) with


   
1 −2 1 1
 2 0 −2   3 
A =   −1 −2
 and b =  
3   1 
0 −1 1 0

Decompose P (A, b) into P (A, b) = conv(V ) + cone(E) + lin(L) with finite sets V, E, L, such
that conv(V ) + cone(E) is pointed.
(b) Does there exist a finite optimum for the problem max c> x, x ∈ P (A, b) with c = (3, −2, −1)> ?
Find the optimal value or an argument why it does not exist.

Exercise 37 7 points

Show that the following inequalities for the 2-matching polytope of an undirected graph G =
(V, E) are valid:
X |F | − 1
xe ≤ |X| + X ⊆ V, F ⊆ δ(X), |F | odd.
2
e∈X×X∪F

Notice that the equations above are just a different formulation of (8.4) from the lecture — if the
condition that F is a matching is omitted.

Exercise 38 8 points

A polyhedron P = {x ∈ Rn |Ax ≥ b} is defined to be full-dimensional if it has positive volume.


Assume that P is bounded and all rows of A are nonzero. Show that the following statements are
equivalent:
(a) P is full-dimensional
(b) There exists a point x ∈ P such that Ax > b
(c) There are n + 1 extreme points of P that do not lie on a common hyperplane

You might also like