
Linear and Integer Programming
(ADM II) 
German


Winter Term 2009/2010 

LVNr.: 3236 L 236
This is a course of the Berlin Mathematical School held in English.
News
Remaining Scheine are now at MA 310.
Photos taken at the Umtrunk are available (as .zip) in
umtrunk/
Content
This course gives an introduction into theory and practice of linear and integer programming. Important algorithms (FourierMotzkin, simplex, ellipsoid, and interior point method; cutting planes and branch&bound), numerical aspects of these methods, as well as the theoretical background (Farkas Lemma, LP duality and optimality criteria, polyhedral theory, polyhedral combinatorics) will be described and elucidated. Moreover, application areas will be mentioned and modelling issues discussed.
The development of linear programming is – in my opinion – the most important contribution of the mathematics of the 20th century to the solution of practical problems arising in industry and commerce. The subsequent progress in the applicability of integer and combinatorial optimization begins, at present, to even surpass this impact. Today, the utilization of linear and integer programming abounds. Almost every product available on the market has some linear or integer programming “inside”. Solutions obtained by IP&LPmethods impact our daily life.
Prerequisites
Linear algebra, basics of analysis, graph and network algorithms.
Preferable: programming in Java or C/C++
Times
Lecture: 
Mon 
12:15  13:45 
MA 041 
Prof. Dr. Dr. h.c. mult. Martin Grötschel 
Mon 
16:15  17:45 
MA 042 
Exercise Course: 
Wed 
12:15  13:45 
MA 042 
Axel Werner/Kati Wolter 
Tutorials: 
Fri 
12:15  13:45 
MA 850 
Jens Schulz 
Fri 
14:15  15:45 
MA 850 
Contacts


Office hours

Room 
Phone 
Email 
Lecturer: 
Prof. Dr. Martin Grötschel 
by appointment 
MA 302 
84185210 
groetschelzib.de 
Assistant (1st half of semester): 
Axel Werner 
Wed 1518 
MA 308 
84185356 
wernerzib.de 
Assistant (2nd half of semester): 
Kati Wolter 
by appointment 
MA 308 
84185283 
wolterzib.de 
Tutor: 
Jens Schulz 
by appointment 
MA 503 
31478796 
jschulzmath.tuberlin.de 
Secretary (TU): 
Claudia Ewel 
by appointment 
MA 310 
31428478 
ewelmath.tuberlin.de 
Secretary (ZIB): 
Bettina Kasse 
by appointment 
3025 
84185209 
kassezib.de 
Exercise sheets
 1st Exercise sheet [pdf]

Deadline: 21 Oct 2009
 2nd Exercise sheet [pdf]
including Programming Exercise 1

Deadline: 28 Oct 2009
Test data for the programming exercise:
[data1]
[data2]
[data3]
 3rd Exercise sheet [pdf]
including Programming Exercise 2

Deadline: 4 Nov 2009 (Programming exercise: 11 Nov 2009)
Test data for the programming exercise
 4th Exercise sheet [pdf]

Deadline: 11 Nov 2009
 5th Exercise sheet [pdf]

Deadline: 18 Nov 2009
 6th Exercise sheet [pdf]
including Programming Exercise 3

Deadline: 25 Nov 2009 (Programming exercise: 2 Dec 2009)
Data for Exercise 16:
[allocation.data]
[expenditure.data]
 7th Exercise sheet [pdf]

Deadline: 2 Dec 2009
Data for Exercise 19:
[Sudoku1.data]
[Sudoku2.data]
[Sudoku3.data]
[Sudoku4.data]
 8th Exercise sheet [pdf]

Deadline: 9 Dec 2009
 9th Exercise sheet [pdf]
including Programming Exercise 4

Deadline: 16 Dec 2009 (Programming exercise: 11 Jan 2010)
 10th Exercise sheet [pdf]

Deadline: 6 Jan 2010
 11th Exercise sheet [pdf]

Deadline: 13 Jan 2010
 12th Exercise sheet [pdf]

Deadline: 20 Jan 2010
 13th Exercise sheet [pdf]

Deadline: 27 Jan 2010
 14th Exercise sheet [pdf]

Deadline: 3 Feb 2010
 very last Exercise sheet [pdf]

Deadline: 10 Feb 2010
Course Material
 Exercise session 14 Oct 09 [pdf]
 Exercise session 21 Oct 09
ZIMPL example files:
ZIMPL documentation: [pdf]
 Exercise session 28 Oct 09 [pdf]
and a slightly fancier picture.
Information about PORTA
 Exercise session 4 Nov 09 [pdf]
 Exercise session 11 Nov 09 [pdf]
 Exercise session 18 Nov 09 [pdf]
 Exercise session 25 Nov 09 [pdf]
 Exercise session 2 Dec 09 [pdf]
 Exercise session 9 Dec 09 [no pdf due to echalk error]
example: phaseI.pdf
 Exercise session 16 Dec 09 [pdf]
example: cycling.pdf
 Exercise session 6 Jan 10 [pdf]
 Exercise session 13 Jan 10 [pdf]
 Exercise session 27 Jan 10 [pdf]
 Exercise session 3 Feb 10 [pdf]
 Exercise session 10 Feb 10 [pdf]
Literature
 D. Bertsimas, R. Weismantel,
Optimization over Integers, Dynamic Ideas, Belmont, Massachusetts, 2005.
 V. Chvátal,
Linear Programming, Freeman, New York, 1983.
 G.B. Dantzig,
Linear Programming and Extensions, Princeton University Press, Princeton, 1963.
 G. B. Dantzig and M. N. Thapa,
Linear programming. I: Introduction, Springer (1997).
 G. B. Dantzig and M. N. Thapa,
Linear programming. II: Theory and extensions, Springer (2003).
 B. Korte, J. Vygen,
Combinatorial Optimization, Theory and Algorithms, Springer, Berlin, 2000, 4th edition 2008,
 M. Padberg,
Linear Optimization and Extensions, Springer, Berlin, 1995.
 A. Schrijver,
Theory of Linear and Integer Programming, Wiley, Chichester, 1986.
 R. J. Vanderbei,
Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, Dordrecht, 1998.
 L. A. Wolsey,
Integer Programming, Wiley, New York, 1998.
Script
Can be found here.
Available software
Requirements for passing
Requirements for passing the course are:
 50% of all points on exercise sheets in the first half of semester
 50% of all points on exercise sheets in the second half of semester
 successful solution of all programming exercises
This page was last modified 11:08, 13 July 2009