Graphs, Geometry, and Optimization
Winter Semester 2008/ 2009
News
(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.
Topics
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.
Times
  • 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)
Office Hours
during term: Tue 16 - 17, otherwise by appointment
(Room 103, Arnimallee 3).

Matthias Grüninger
Wed, 9-10
(Room 112, Arnimallee 3).

Software
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
Course Contents
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
Exercises
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
Literature
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
Prerequisites
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.
Examinations
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.