Skip to main content

Summer 2021

Approximation Algorithms

Master Course in Summer 2021
03-ME-602.99a (03-IMAT-APX), 6 CP (+ 3 CP possible)

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial-time algorithms and proving rigorous bounds on their worst case performances.

We review many classical results in the field of approximation algorithms, highlighting different techniques commonly used for the design of such algorithms. Among others, we will treat the following topics:

  • Greedy algorithms and Local Search
  • Rounding Data and Dynamic Programming 
  • Deterministic Rounding of Linear Programs (LPs)
  • Random Sampling and Randomized Rounding of LPs
  • Primal-Dual Methods
  • Hardness of Approximation
  • Problem Solving under Uncertainty 

Lecturers:

Time & Format:

We will teach the course with 4 hours per week, where roughly every other week one class will be an interactive exercise session. We will switch between synchronous teaching via Zoom and asynchronous classes vias videos and additional material. 

  • Tue 10-12
  • Thu 10-12

There is the possibility to further extend the content of the course as well as the credits by participating in a seminar. This participation consists of individually studying a recent research article and presenting the main results to the rest of the class. 

Start:

  • Tuesday, April 13, at 10:15 via zoom (link in StudIP)

Examination:

The examination will be by individual oral exam. A 1/3 grade bonus is awarded to students who correctly solve 60% of the homework exercises.

Literature: The course is based on parts of the literature below and recent research articles that will be provided later.

  • [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
  • [V] Approximation Algorithms, Vijay V. Vazirani
  • [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiří Matoušek, Springer, 2012

Operations Research

Sommersemester 2021, 6CP
03-BB-699.01 (03-IBAT-OR)

Moderne betriebliche Informationssysteme nutzen verschiedene quantitative Verfahren aus der Informatik und Mathematik um Planungs- und Entscheidungsprozesse zu unterstützen. So lassen sich viele praktische Fragestellungen als (ganzzahlige) lineare Optimierungsprobleme formulieren: z.B. Warenfluss und Planung von Produktionsprozessen in der Logistik, Portfoliotheorie und Risikomanagement in der Finanzwelt sowie Netzwerkdesign und Routing in der Telekommunikation.

Die Vorlesung gibt eine Einführung in die grundlegenden Methoden der linearen und ganzzahligen linearen Optimierung. Themen sind: Mathematische Modellierung praktischer Fragestellungen (Entscheidungs-, Planungs- und Optimierungsprobleme), Struktur und Geometrie linearer Programme, Simplexverfahren, Komplexität, Dualität, Sensitivitätsanalyse; Methoden zum Lösen ganzzahliger linearer Probleme: Branch-and Bound Methode, Schnittebenen-Verfahren, Dynamische Programmierung und Greedy Verfahren; gundlegende kombinatorische Algorithmen für Graphen- und Netzwerkflussprobleme.

Dozentin:  Prof. Dr. Nicole Megow
Tutoren:  Lukas Nölke, Alexander Lindermayr

Zeit und Format: 

Die Veranstaltung findet zum Teil asynchron virtuell statt. Vorlesungsvideos und schriftliche Materialien werden bereit gestellt.

  • Erste Veranstaltung: Montag, dem 12.04.2021, um 12:15 Uhr über Zoom (Link in StudIP).

Es gibt wöchentliche feste virtuelle Termine für Übung und Diskussion. Alle zwei Wochen findet eine betreute Rechnerübung statt.

Leistungsnachweis:

Es ist eine Klausur geplant. Durch Erreichen einer Mindestpunktzahl bei den wöchentlichen Übungsblättern kann ein Notenbonus erzielt werden.

Literatur:

  • [W] Winston, A.: Operations Research, Algorithms and Applications, Whiley & Sons, Duxbury Press, 2003.
  • [NSW] Nickel, Stein, Waldmann: Operations Research, Springer Gabler, 2. Auflage, 2014.
  • [DDKS] Domschke, W.; Drexl, A.; Klein, R.; Scholl, A.: Einführung in Operations Research, 5. Auflage, Springer, 2015.
  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.

Seminar: Combinatorial Optimization and Machine Learning

Sommersemester 2021, 6 CP
03-M-SEM-24

This seminar focusses on recent research at the interplay of combinatorial optimization and machine learning. Both fields provide important methods for solving various real-world problems. On the one hand, we study how machine learning techniques can improve well-established solution methods for NP-hard discrete optimization problems. How can untrusted prediction, e.g., machine-learned, be used to derived provable guarantees for the performance of online algorithms? How can machine learning accelerate existing optimization methods? On the other hand, combinatorial optimization problems are increasingly important in machine learning. We will study particular relevant problems such as clustering, feature selection and submodular function optimization.

Lecturer: Prof. Dr. Nicole Megow

Format: 

Students are expected to read and thoroughly understand original research papers, and to deliver an oral presentation and a write up.

Most likely the seminar will be virtual via Zoom.

  • Organizational  meeting: Tuesday, April 13, at 12:15 pm via Zoom (link in StudIP)

We will discuss the organization and allocate the research articles in the first meeting. Please register with StudIP. The seminar is planned as a block seminar, meaning that all talks will be at two days in the end of the semester. We will discuss this in the first zoom meeting.

Hands-on Tutorial on Optimization (engl./dt.)

Block course in Summer 2020 (July 26–30)
03-BE-699.12, 3 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems.

We develop a toolkit to model real-world problems as (discrete) linear programs. Some examples of basic optimization problems that are part of this toolkit are scheduling, packing, matching, routing, and network-design. We also explore different ways to find integer solutions such as cutting planes, Branch & Bound, and column generation. Based on this theoretical background, we focus on translating practical examples into mixed-integer linear programs. We learn how to use professional solvers (such as CPLEX, Gurobi, and FICO Xpress) and tailor the solution process to certain properties of the problem.

Throughout the course, we concentrate on modeling and solving practical problems with some theory parts in between.

Lecturers:

This course consists of two phases:

  • One week of lectures and practical labs during Mon July 26 – Fri July 30 full time. 
  • One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented before the beginning of the winter semester 2021/22.

There are no prerequisites except some basic programming skills to participate.

Please register by July 1st in StudIP.

The tentative schedule is as follows.

DayTentative topicsPractical tasks
1

Introduction, Modeling, Using CPLEX

Chips Factory, Crude Oil Processing

2

Matrix and Polyhedral Representations,
Integer Linear Programming Tools,
Cutting Planes and Symmetry

Graph Coloring, Farm Planning

3

Branch&Bound, TSP, CPLEX guest lecture

Cheese Coup

4

LP Duality, Modeling Tricks

Cheese Empire

5

Column Generation, Non-Optimal Solutions, Using Other Environments

Maintenance Scheduling

 Final Assignment