Zur
  Seite der TU

Linear and Integer Programming

(ADM II)

Zur Seite des Instituts für Mathematik
 

Winter Term 2006

 
LV-Nr.: 0230 L 236
 

Prof. Dr. Martin Grötschel
 

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

Lecture: Mon 10 - 12 H 0112 Prof. Dr. Martin Grötschel
Mon 14 - 16 MA 043
Exercise course: Wed 12 - 14 H 0111 Rüdiger Stephan
Tutorials: Tue 12 - 14 MA 651 Torsten Ueckerdt
Wed 14 - 16 MA 651


Course materials


Exercise sheets

Standard formats .ieq for Porta and .lp for CPLEX


Available software


Requirements for passing


Valid HTML 4.0! This page was last modified 13:03, 30 October 2006