Research Group Lattice Polytopes

(1) There are now lecture notes for part of the course. login and password have been anounced in class and may be obtained from me.
If you use the notes it would be nice if you tell me about any errors and inconsitencies that you find in the text (no matter how trivial).

(2) This course will be followed by a course on Integer Polyhedra in the next semester.

(3) The exam will be written on Wed, Feb 11, at 14:30
in room 130, A3
Bring a pen (not red, not pencil). You may also bring a ruler if you want to.
The sheet will be in English, but answers can be given in German or English.

The plan is to cover in this course classical duality results in graph theory and discrete geometry and their applications, e.g.

• polytopes and polyhedra,
• linear programming and the Simplex algorithm,
• integer programming,
• flows and networks,
• matchings,
• min-max-theorems.

Optimization problems for graphs can often naturally be formulated as linear or integer programs, that is, as a system of linear equations and an objective function such that the objective function values of corresponding solutions are equally valuated. To any linear program we can associate a dual linear program. It turns out, that this dual program can often again be interpreted as some other graph problem.
A prominent example of this is the following: Let G be a bipartite graph, i.e. a graph whose vertex set falls into two classes such that no edge connects vertices in the same class. The minimum vertex cover problem asks for the minimal number of vertices one has to choose so that each edge is adjacent to at least one of them, and the maximum matching problem asks for the maximal number of edges one can choose so that no two share a vertex. Formulated as linear programs, these problems are dual to each other, hence, the numbers coincide, which proves König's Theorem.
In this class, we will discuss graph theoretical aspects as well as linear programming aspects (and their geometric interpretation) and will show connections between these topics.

• Class (Andreas Paffenholz):
  • Tuesday 10 - 12, SR 25/26 (Arnimallee 6)
  • Tuesday 14 - 16, SR055 (Takustr. 9)
• Tutorial (Matthias Grüninger):
  • Wednesday 10 - 12, SR 025/026 (Arnimallee 6)
    

If you want to experiment with cones and polyhedra, there are several good software packages avaiable that can convert between interior and exterior descriptions and compute many other properties of polyhedra. Two (Berlin based) choices are

• polymake is a package for computations with polytopes. It can convert representations, compute (numbers of) faces and determine lots of combinatorial properties of polytopes. For the conversion of the representation it uses either cdd or lrs
• PORTA: is a collection of programs that convert representations and can do Fourier-Motzkin elimination.

Of these, only polymake is installed here at the math depertment. Contact me if you encounter problems using it.

There are also lots of nice (and free) packages that can deal with linear programming problems. However, there is non installed here. Some choices are

• SoPlex
• SCIP
• lp_solve
• AMPL

class date	Contents	Notes	last modified
10/14	Motivation Types of mathematical optimization convex optimization, linear and integer optimization example of linear optimization in 2D graphical solution weak duality Assigments, linear programming formulation
	Basics of linear programming standard and canonocal form transformation rules
10/21	transformation rules basic (feasible) solutions of systems in standard form
	Farkas Lemma Definition of cones, affine, linear, convex sets polyehdral, finitely generated cones Fourier-Motzkin-elimination Farkas Lemma Minkowski-Weyl-Duality for cones
10/28	Polyhedra and Polytopes polyhedra affine Weyl-Minkowski duality H- and V-description recession coneand lineality space dimension
	Duality in Linear Programming weak duality theorem
11/04	Duality in Linear Programming constructing the dual linear program duality theorem complementary slackness theorem
	Faces of Polyhedra definitions faces are intersections of hyperplanes geometric interpretation of duality and slack redundancy and facets
11/11	facets correspond to irredundant inequalities minimal faces refined affine Minkowski theorem edges and extremal rays minimal proper faces generating sets of cones minimal generating sets of polyhedra characterizations of vertices connection to linear programming
11/18	minimal proper faces extremal rays of cones description of polyhedra as convex hull and cone minimality and uniqueness of interior description characterization of pointedness optimal solutions of linear programs are vertices
	Matching Polytopes graphs, matchings, perfect matchings characteristic vectors definition of the (perfect) matching polytope as convecx hull exterior description of the (perfect) matching polytope for bipartite graphs
11/25	characterization ofperfect matching polytopes of general graphs (Edmonds) characterization of the matching polytope
12/02	Complexity and Sizes of Rational Polyhedra binary encoding of numbers algorithms decision and optimization problems running time fuctions P, NP, coNP, well-characterized problems sizes of solutions of systems of linear equations and inequalities bound on the size of interior in the exterior description, and vice versa linear programming is well-characterized
12/09	The Simplex Method I primal simplex method: phase II simplex tableau
12/16	The Simplex Method II simplex method: phase I cycling row and column selection rules dual simplex method
12/22	Christmas Break
01/06	dual simplex method continued reduced tableaus primal-dual methods sensitivity
	Integer Polyhedra definitions integer hull of a polyhedron
01/13	integer hull is a polyhedron characterizations Hilbert bases
	Unimodularity definitions characterizations polyhedra defined by unimodular matrices
01/20	more on unimodular matrices Theorem of Ghouila-Houri
	Applications of Unimodularity undirected graphs matchings and vertex covers König's Theorem weighted versions
01/27	directed graphs MaxFlow-MinCut-Theorem algorithm of Ford-Fulkerson
	Total Dual Integrality unimodular transformations Hermite normal form lattice preserving transformations Integral alternative theorem
02/03	totally dual integrable systems TDI and integral polyhedra faces of TDI systems are TDI Hilbert bases of normal cones minimally TDI systems
	Chvatal-Gomory Cuts elementary closures cutting planes elementary closure of TDI systems
03/10	computing integer hulls bounds on the Chvatal rank
10/15	Graphs
	References

The starred exercises are optional.

Sheet 1	deadline: 08/10/21
Sheet 2	deadline: 08/10/28
Sheet 3	deadline: 08/11/04
Sheet 4	deadline: 08/11/11
Sheet 5	deadline: 08/11/18
Sheet 6	deadline: 08/11/25
Sheet 7	deadline: 08/12/02
Sheet 8	deadline: 08/12/09
Sheet 9	deadline: 08/12/16
Sheet 10	deadline: 09/01/06
Sheet 11	deadline: 09/01/13
Sheet 12	deadline: 09/01/20
Sheet 13	deadline: 09/01/27
Sheet 14	deadline: 09/02/03

From October on I have reserved some books in the library. They can be found in the shelf next to the door leading to the journal room (turn right after the front desk).

• Barvinok, A Course in Convexity, AMS
• Chvatal, Linear Programming, Freeman
• Korte, Vygen, Combinatorial Optimization, Springer
• Matousek, Gärtner, Understanding and Using Linear Progamming, Springer
• Shrijver, Combinatorial Optimization -- Polyhedra and Efficiency, Springer
• Shrijver, Linear and Integer Programming, Wiley
• Ziegler, Lectures on Polytopes, Springer

Formally, this course is a continuation of Discrete Mathematics I, however, the course is clearly accessible also to students that have not attended this course.

I will assume knowledge in linear algebra and some basic graph theory (basics, bipartite graphs, tree). If needed, I will offer an extra lecture on basic graph theory to those that haven't attended Discrete Math I or something similar at the beginning of the semester.

Mail me if you have any questions about this.

To get the 10 ECTS points it is necessary to

• regulary attend the tutorial (this usually means to miss at most two)
• hand in essentialy correct solutions to at least 50% of the assigned homework. You should be able to present your solution in the tutorial.
• pass the exam at the end of the semester.
Your final mark depends only on your result in the exam.