186.835 Mathematical Programming
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2018S, VU, 2.0h, 3.0EC, wird geblockt abgehalten


  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

  • Get a broader knowledge in the area of mathematical optimization with focus on (mixed) integer linear programming (MIP)
  • Be able to model both academic and real world problems as MIPs
  • Be able to theoretically analyze and compare different mathematical programming formulations for a problem
  • Have knowledge on common methodology for solving MIPs
  • Be able to develop practical solution algorithms using state-of-the-art MIP frameworks

Inhalt der Lehrveranstaltung

  • Overview on mathematical optimization (focus on mixed integer models, but also including non-linear and non-deterministic models)
  • Modeling (real world) problems as MIPs (basic techniques, modeling with exponentially many constraints and / or variables)
  • Solution methods for MIPs
    - Cutting plane method, branch-and-cut
    - Decomposition approaches (Langrangian decomposition, Dantzig-Wolfe decomposition) and corresponding solution methods (subgradient method, column generation, branch-and-price)
  • Theory of valid inequalities and further theoretical concepts
    - (Strong) valid inequalities (Chvatal-Gomory cuts, Gomory cuts, mixed integer cuts, cover cuts, theoretical concepts such as dominance, redundancy, facet defining cuts)
    - "Well-solved" problems (properties, total unimodularity, optimization = separation)
  • Further issues in MIP computation and components of modern MIP solvers (presolving, primal heuristics, symmetry, frameworks)
  • Overview on further methods and extensions (stochastic- and robust optimization, non-linear programming, multiobjective optimization)

Weitere Informationen

Estimated effort:

Hours | Purpose
16       | Lecture
10       | Homework exercises 
30       | Programming exercise
19       | Exam preparation and exam
75       | Overall

Vortragende Personen

  • Leitner, Markus


LVA Termine

Mi.16:00 - 19:0007.03.2018Seminarraum FAV EG B (Seminarraum von Neumann) Introduction, Programming Exercise
Mi.16:00 - 19:0014.03.2018 - 23.05.2018Seminarraum FAV 01 A (Seminarraum 183/2) Vorlesung
Mathematical Programming - Einzeltermine
Mi.07.03.201816:00 - 19:00Seminarraum FAV EG B (Seminarraum von Neumann) Introduction, Programming Exercise
Mi.14.03.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Branch-and-Cut
Mi.11.04.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Branch-and-Price
Mi.02.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) Lagrangian Relaxation, Stochastic and Robust Optimization
Mi.09.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) (Strong) Valid Inequalities, Total Unimodularity
Mi.16.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) MIP Computation
Mi.23.05.201816:00 - 19:00Seminarraum FAV 01 A (Seminarraum 183/2) (reserve)
LVA wird geblockt abgehalten


In addition to the lectures, there will be homework assignments and a programming exercise.

Homework Assignments

Specifications will be made available for download in TISS.

Programming Exercise

You will have to design and implement different integer programming formulations for a specified optimization problem. Specifications and the framework will be available for download in TISS. You should join in groups of two for this programming exercise and send your results by mail to us (deadlines will be announced).

Final Exam

Dates for the final oral exam will be available in May and June and also in summer if required. Details will be announced here.

- Each team (w.r.t. the programming exercise) should choose a common date / timeslot for the exercise (unless there are good reasons not to do so).

- You should register for the exam by email (to both of us). In this email please specify who is going to take the exam (you and your partner), the date and constraints regarding the concrete time (as we will try to schedule the exams such that there are not too long breaks for us). For each group of two we will reserve 45 minutes and for a single student we will reserve 30 minutes.

- The concrete location of the exam will be announced to you by mail.


The mark you receive depends on the final exam (50%) and your accomplishments in the homework assignments (15%) and the programming exercise (35%).


Von Bis Abmeldung bis
01.02.2018 12:00 05.04.2018 23:59 05.04.2018 23:59



Es wird kein Skriptum zur Lehrveranstaltung angeboten.


  • Basic knowledge of (integer) linear programming (modeling, LP based Branch-and-Bound) as e.g. taught in Algorithmics
  • Knowledge of basic algorithms and data structures
  • Programming skills in Java or C++
  • Basic knowledge of linear algebra and graph theory

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen


bei Bedarf in Englisch