|
Linear and Integer Programming
(ADM II) |
German
|
|
Winter Term 2009/2010 |
|
LV-Nr.: 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 (Fourier-Motzkin, 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&LP-methods 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 |
84185-210 |
groetschelzib.de |
Assistant (1st half of semester): |
Axel Werner |
Wed 15-18 |
MA 308 |
84185-356 |
wernerzib.de |
Assistant (2nd half of semester): |
Kati Wolter |
by appointment |
MA 308 |
84185-283 |
wolterzib.de |
Tutor: |
Jens Schulz |
by appointment |
MA 503 |
314-78796 |
jschulzmath.tu-berlin.de |
Secretary (TU): |
Claudia Ewel |
by appointment |
MA 310 |
314-28478 |
ewelmath.tu-berlin.de |
Secretary (ZIB): |
Bettina Kasse |
by appointment |
3025 |
84185-209 |
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 e-chalk 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