Current Term - Winter 2021/22

Column Generation und Branch-and-Price

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

Prerequisites

Indispensible: Solid knowledge in linear/integer optimization from the courses "quantitative methods" and "operations research 1" (BWL) or "efficient algorithms" (CS) or "integer linear optimization" (maths), i.e., in particular you master duality, branch-and-bound, and modeling with integer programs.

Contents

State of the art in models and algorithms to solve extremely large-scale and complex optimization problems, in particular column generation and branch-and-price: structued integer programs, Dantzig-Wolfe reformulation, Lagrange relaxation, cutting planes in connection with column generation, branching rules, stabilization technqiues, implementation tricks, practical applications

Learning Goals

The students aquire basic and advanced skills in modelling very large-scale and practical optimization problems, as well as the algorithmic thinking to solve such models using decomposition approaches. By working on practical implementation exercises, these algorithms shall be actually applied and the basic implementation of a column generation approach will be learned. Students will be enabled to read scientific publications at the current level of scientific knowledge and transfer this knowledge to practical modeling situations.

 

Literature

  • Desrosiers, J. and Lübbecke, M.
    Selected Topics in Column Generation. Operations Research, 53(6):1007—1023, December 2005.
  • Desrosiers, J. and Lübbecke, M.
    A Primer in Column Generation. In Desaulniers, G., Desrosiers, J. and Solomon, M.M., Column Generation. chapter 1, pages 1—32, Springer US, January 2005.

Operations Research 1

Infos:

  • Lecturer: Marco Lübbecke
  •  
    • Hermann von Westerholt
  • Typ:lectures
  • Languageenglish
  • Contact:

Content:

Theory
Practice
Modeling
Coding

Prerequisites

Basic knowledge in linear optimization and graph algorithms, in particular modeling with networks (minimum cost flows, shortest paths) and linear programs. If missing, this background must be acquired before or simultaneously to the course.

Contents

1. Modeling with integer linear programs: assignment problems, knapsack problem, faclity location, machine scheduling, traveling salesperson problem, vehicle routing, set partitioning, bin packing, cutting stock, logical constraints; 2. algorithms for solving integer programs: branch-and-bound, cutting planes, branch-and-cut, dynamic programming; 3. basics of heuristics and meta heuristics (construction and improvement heuristics, greedy algorithm, local search, simulated annealing, tabu search, evolutionary and genetic algorithms); 4. particular modeling situations like soft constraints, non-linearities, heuristic modeling; introduction to computational complexity theory

Learnig Goals

Students learn modeling techniques and methods of integer optimization, in particular their use cases and limitations. Students aquire the ability to identify the mathematical core of a practical optmization task and to exploit problem structure when selecting/developing a model or selecting an algorithm. The theoretical knowledge is deepened using practical exercises with standard software (currently Gurobi/Python). We generally sharpen abstraction capabilities.

 

Videos from winter term WS17/18 are here.

OR Praktikum

Infos:

  • Lecturer: Marco Lübbecke
  •  
    • Elisabeth Rodriguez-Heck
  • Typ:Practice Project
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding

Seminar

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:seminar
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding

Next Term - Summer 2022

Operations Research 2 every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman or english
  • Turnus: every summer term

Content:

Theory
Practice
Modeling
Coding

OR Praktikum every term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:Practice Project
  • Languagegerman
  • Turnus: every term

Content:

Theory
Practice
Modeling
Coding

Praktische Optimierung mit Modellierungssprachen every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures and exercises
  • Languagegerman or english
  • Turnus: every summer term

Content:

Theory
Practice
Modeling
Coding

Quantitative Methoden every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman
  • Turnus: every summer term

Content:

Theory
Practice
Modeling
Coding

Literature

  • Ahuja, R.K., Magnanti, T.L. and Orlin, J.B.
    Network Flows: Theory, Algorithms, and Applications. Prentice Hall, December 1992.
  • Bertsimas, D. and Tsitsiklis, J.N.
    Introduction to Linear Optimization. Athena Scientific, January 1997.
  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.
    Introduction to Algorithms. MIT Press, January 2009.

Seminar every term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:seminar
  • Languagegerman
  • Turnus: every term

Content:

Theory
Practice
Modeling
Coding

Entire List of Courses we offer

Approximationsalgorithmen irregularly

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures and exercises
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

Literature

  • Vazirani, V.V.
    Approximation Algorithms. Springer, January 2001.
  • Hochbaum, D.S.
    Approximation Algorithms for NP-hard Problems. PWS Publishing Company, January 1997.
  • Williamson, D.P. and Shmoys, D.B.
    The Design of Approximation Algorithms. Cambridge University Press, January 2011.

Column Generation und Branch-and-Price every winter term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

Prerequisites

Indispensible: Solid knowledge in linear/integer optimization from the courses "quantitative methods" and "operations research 1" (BWL) or "efficient algorithms" (CS) or "integer linear optimization" (maths), i.e., in particular you master duality, branch-and-bound, and modeling with integer programs.

Contents

State of the art in models and algorithms to solve extremely large-scale and complex optimization problems, in particular column generation and branch-and-price: structued integer programs, Dantzig-Wolfe reformulation, Lagrange relaxation, cutting planes in connection with column generation, branching rules, stabilization technqiues, implementation tricks, practical applications

Learning Goals

The students aquire basic and advanced skills in modelling very large-scale and practical optimization problems, as well as the algorithmic thinking to solve such models using decomposition approaches. By working on practical implementation exercises, these algorithms shall be actually applied and the basic implementation of a column generation approach will be learned. Students will be enabled to read scientific publications at the current level of scientific knowledge and transfer this knowledge to practical modeling situations.

 

Literature

  • Desrosiers, J. and Lübbecke, M.
    Selected Topics in Column Generation. Operations Research, 53(6):1007—1023, December 2005.
  • Desrosiers, J. and Lübbecke, M.
    A Primer in Column Generation. In Desaulniers, G., Desrosiers, J. and Solomon, M.M., Column Generation. chapter 1, pages 1—32, Springer US, January 2005.

Operations Research 1 every winter term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languageenglish

Content:

Theory
Practice
Modeling
Coding

Prerequisites

Basic knowledge in linear optimization and graph algorithms, in particular modeling with networks (minimum cost flows, shortest paths) and linear programs. If missing, this background must be acquired before or simultaneously to the course.

Contents

1. Modeling with integer linear programs: assignment problems, knapsack problem, faclity location, machine scheduling, traveling salesperson problem, vehicle routing, set partitioning, bin packing, cutting stock, logical constraints; 2. algorithms for solving integer programs: branch-and-bound, cutting planes, branch-and-cut, dynamic programming; 3. basics of heuristics and meta heuristics (construction and improvement heuristics, greedy algorithm, local search, simulated annealing, tabu search, evolutionary and genetic algorithms); 4. particular modeling situations like soft constraints, non-linearities, heuristic modeling; introduction to computational complexity theory

Learnig Goals

Students learn modeling techniques and methods of integer optimization, in particular their use cases and limitations. Students aquire the ability to identify the mathematical core of a practical optmization task and to exploit problem structure when selecting/developing a model or selecting an algorithm. The theoretical knowledge is deepened using practical exercises with standard software (currently Gurobi/Python). We generally sharpen abstraction capabilities.

 

Videos from winter term WS17/18 are here.

Operations Research 2 every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

OR Praktikum every term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:Practice Project
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding

Praktische Optimierung mit Modellierungssprachen every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures and exercises
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

Polyedrische Kombinatorik currently not offered

Infos:

  • Lecturer: Matthias Walter
  • Typ:lectures
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding

Programmieren, Algorithmen, Datenstrukturen currently not offered

Infos:

Content:

Theory
Practice
Modeling
Coding

Beschreibung EN

Literature

  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.
    Introduction to Algorithms. MIT Press, January 2009.

Proseminar irregularly

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:proseminar
  • Languagegerman or english

Content:

Theory
Practice
Modeling
Coding

Quantitative Methoden every summer term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:lectures
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding

Literature

  • Ahuja, R.K., Magnanti, T.L. and Orlin, J.B.
    Network Flows: Theory, Algorithms, and Applications. Prentice Hall, December 1992.
  • Bertsimas, D. and Tsitsiklis, J.N.
    Introduction to Linear Optimization. Athena Scientific, January 1997.
  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.
    Introduction to Algorithms. MIT Press, January 2009.

Seminar every term

Infos:

  • Lecturer: Marco Lübbecke
  • Typ:seminar
  • Languagegerman

Content:

Theory
Practice
Modeling
Coding