|
Linear and Integer Programming
(ADM II) |
|
|
Winter Term 2006 |
|
LV-Nr.: 0230 L 236
This is a course of the
Berlin
Mathematical School held in English.
Content
This course gives an introduction into theory and practice of linear and
integer programming. Important algorithms (simplex, ellipsoid, and
interior point method; cutting planes and branch&bound), numerical
aspects of these methods, as well as
the theoretical background (polyhedral theory, LP duality,
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.
Further courses
Requirements
Linear algebra, basics of analysis, graph and network algorithms.
Literature
D. Bertsimas and R. Weismantel, "Optimization over Integers", Belmont, Massachusetts, 2005.
V. Chv�tal, "Linear Programming", Freeman, New York, 1983.
G.B. Dantzig, "Linear Programming and Extentions", Princeton
University Press, Princeton, 1963.
B. Korte and J. Vygen, "Combinatorial Optimization. Theory and
Algortihms", Springer, Berlin, 2000 (Third edition 2006 extended).
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
Extentions", Kluwer Academic Publishers, Dordrecht, 1998.
L.A. Wolsey, "Integer Programming", Wiley, New York, 1998.
Script :
can be found
here.
Contacts
|
|
Office hours
|
Room |
Phone |
Email |
Lecturer: |
Prof. Dr. Martin Grötschel |
by appointment |
MA 302 |
84185-210 |
groetschelzib.de |
Assistent: |
Rüdiger Stephan |
by appointment |
MA 308 |
314-28 323 |
stephanmath.tu-berlin.de |
Tutor: |
Torsten Ueckerdt |
Thu 12:00 - 14:00 |
Unixpool |
|
ueckerdtmath.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 |
Times
Course materials
- Lecture
- Exercise course
- Wednesday, October 18, 2006 [Exercise.pdf] [Sudoku.pdf] [sudoku.zpl] [sudoku1.data] [sudoku2.data] [sudoku3.data] [sudoku4.data]
- Wednesday, October 25, 2006 [JuiceGlasses.pdf]
- Wednesday, November 01, 2006 [Extended sample solution of Exercise 7 (pdf)]
- Wednesday, January 24, 2007 [Exercise.pdf]
- Wednesday, January 31, 2007 [Exercise.pdf]
Exercise sheets
Standard formats .ieq for Porta and .lp for CPLEX
Available software
Requirements for passing
- at least 50 % of the possible marks in the weekly homework
exercises 1-7
- at least 50 % of the possible marks in the weekly homework
exercises 8-14
- succesfull processing of the programming exercises
This page was last modified 13:03, 30 October 2006