Aktuelles Semester - Winter 2018/19

Column Generation und Branch-and-Price

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch oder englisch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Unverzichtbar: Sichere Kenntnisse in linearer/ganzzahliger Optimierung aus "Quantitativen
Methoden" und "Operations Research 1" (BWL) oder "effizienten Algorithmen" (Informatik)
oder "ganzzahliger linearer Optimierung" (Mathematik), d.h. insbesondere Beherrschen von Dualität,
Branch-and-Bound, Modelierung mit ganzzahligen Programmen.

Modulinhalt

Stand der Technik in Modellen und Algorithmen zur Lösung extrem großer und komplexer Optimierungsprobleme, speziell Column Generation und Branch-and-Price: strukturierte ganzzahlige Programme, Dantzig-Wolfe Dekomposition, Lagrange-Relaxation, Schnittebenen in Verbindung mit Column Generation, Branchingregeln, Stabilisierungstechniken, Implementationstricks, praktische Anwendungen

Lernziele

Die Studierenden erwerben grundlegende und fortgeschrittene Fertigkeiten für die Modellierung extrem großer, praktischer Optimierungsprobleme sowie das algorithmische Denken, diese Probleme mit Dekompositionansätzen zu lösen. Im Umgang z.B. mit Modellierungssprachen sollen diese Algorithmen auch praktisch verstanden werden. Die Programmierung von Column Generation in einem algorithmischen Framework wie SCIP soll grundlegend erlernt werden. Die Studierenden sollen in die Lage versetzt werden, Veröffentlichungen auf dem Niveau des aktuellen Standes der Forschung einordnen und verstehen zu können, sowie das Wissen auf praktische Problemstellungen zu übertragen.

 

Literatur

  • Desrosiers, J. and Lübbecke, M.
    Selected Topics in Column Generation. Operations Research, 53(6):1007—1023, November 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, December 2004.

Operations Research 1

Infos:

  • Verantwortlich Marco Lübbecke
  •  
    • Matthias Walter
  • Typ:Vorlesung
  • Sprache:englisch
  • Kontakt:

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Kenntnisse im Bereich linearer Optimierung und grundlegender Graphenalgorithmen, vor allem zur Modellierung mit Netzwerken und linearen Programmen werden benötigt (und müssen sich ggfs. vorab oder begleitend angeeignet werden).

Modulinhalt

1. Modellierung mit linearen und ganzzahligen Programmen: Zuordnungsprobleme, Knapsack, Standortprobleme, TSP, Tourenplanung/Vehicle Routing, Schedulingprobleme, Set Cover, Set Packing, Set Partitioning, Bin Packing, Cutting Stock, logische Bedingungen; 2. Algorithmen für ganzzahlige Programme: Branch-and-Bound, Schnittebenen, Branch-and-Cut, Dynamische Programmierung; 3. Grundlagen Heuristiken und Metaheuristiken (Eröffnungs- und Verbesserungsheuristiken, Greedy Algorithmen, Lokale Suche, Simulated Annealing, Tabu-Search, Evolutionäre und Genetische Algorithmen); 4. Spezielle Modellierungssituationen wie weiche Bedingungen, Umgang mit Nichtlinearitäten, heuristisches Modellieren; 5. Einführung Komplexitätstheorie

Lernziele

Die Studierenden erlernen Modellierungstechniken und Methoden der ganzzahligen Optimierung, insbesondere deren Einsatzmöglichkeiten und Grenzen. Es soll die Fähigkeit geschult werden, den einer praktischen Aufgabe zugrundeliegenden mathematischen Kern zu identifizieren und dessen Struktur gewinnbringend bei der Auswahl oder Entwicklung von Modellen oder Lösungsalgorithmen einzusetzen. Die theoretischen Kenntnisse werden mit Hilfe von Standardsoftware (zurzeit Gurobi/Python) am Computer an Planungs- und Entscheidungsproblemen vertieft, die an die industrielle Praxis angelehnt sind. Das Abstraktionsvermögen wird geschult.

 

Vorlesungsvideos aus dem WS17/18 finden sich hier.

Polyedrische Kombinatorik

Infos:

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Kenntnisse ganzzahliger und linearer Optimierung (LP-Dualität, Polytope, Totale Unimodularität) und diskreter Mathematik (Graphen, Graphenalgorithmen, Analyse/Komplexiät von Algorithmen); Grundkenntnisse von Problemen der diskreten Optimierung/Operations Research (Knapsack, Matching, Set Cover, Bin Packing, TSP, etc.) hilfreich; mathematische Grundfertigkeiten unverzichtbar.

Inhalt:

In der Veranstaltung werden moderne Techniken und Resultate zu Polyedern aus der Kombinatorischen Optimierung behandelt. Die Vorlesung dient der Einführung der Grundbegriffe, Präsentation wichtiger Resultate und der gemeinsamen Analyse der Beweise. In der Übung werden der Stoff gefestigt und die erlernten Techniken an kleineren Beispielen geübt.

Kapitel: Matroide

Nach der Einführung in die kombinatorische Stuktur der Matroide und Betrachtung einfacher Strukturresultate wenden wir uns dem Lösungsalgorithmus (Greedy) zu. Dessen Funktionsweise liefert uns polyedrische Resultate zu den assoziierten ganzzahligen Hüllen, der Matroidpolytope. Weiterhin zeigen wir, dass sogar der Schnitt zweiter solcher Matroidpolytope ganzzahlig ist (Matroid Intersection) und wie Matroide uns helfen, dass man über submodularen Funktionen in Polynomialzeit optimieren kann.

Kapitel: Relaxierungen

Zunächst betrachten wir Techniken zum Vergleich der Stärke von linearen Relaxierungen, bzw. der Stärke von zusätzlichen Schnittebenenklassen und wenden diese exemplarisch an. Im zweiten Teil geht es um Negativresultate zur (oft exponentiellen) Anzahl der für eine Relaxierung im Originalraum benötigten Ungleichungen.

Kapitel: Erweiterte Formulierungen

Hier betrachten wir das Phänomen, dass bei der Beschreibung eines Polyeders Ungleichungen eingespart werden können, indem man es als Projektion eines höherdimensionalen Polyeders (als Erweiterte Formulierung) beschreibt. Es werden diverse Beispiele und Konstruktionstechniken für Erweiterte Formulierungen sowie eine Technik gezeigt, mit deren Hilfe man die Grenzen dieses Phänomens ausloten kann. Damit zeigen wir, dass das man zur Beschreibung des Cut-Polytops (das mit dem Max-Cut-Problem assoziiert ist) trotz Nutzung von Projektionen exponentiell viele Ungleichungen benötigt.

Kapitel: Äquivalenzen bei 0/1-Polytopen

Wir zeigen, dass folgende Probleme für 0/1-Polytope äquivalent sind:

  1. Das Finden einer Optimallösung
  2. Das Finden einer besseren Lösung (für eine gegebene Lösung)
  3. Das Lösen des Separationsproblems
  4. Das Lösen des primalen Separationsproblems

Hierzu wird unter anderem das zentrale Resultat zur Äquivalenz von Optimieren und Separieren gezeigt.

Ziele:

Neben der Vermittlung der teils klassischen, teils aktuellen Resultate wird vor allem die zugrundeliegende Methodik vermittelt. Sehr viel Wert wird auf die meist geometrische Intuition hinter den Resultaten bzw. Beweisideen gelegt.

Kommendes Semester - Sommer 2019

Approximationsalgorithmen unregelmäßig

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung und Übung
  • Sprache:de/en
  • Turnus: unregelmäßig

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Approximationsalgorithmen berechnen Lösungen für Optimierungsprobleme mit einer garantierten Güte in Polynomialzeit. Die Algorithmen selbst sind meißt sehr intuitiv und eher einfach, spannend ist vor allem oft die mathematische Analyse der Gütegarantie. Wir behandeln in dieser Vorlesung verschiedene kombinatorische Optimierungsprobleme, vor allem auf Graphen und Techniken zu deren Approximation, u.a. polynomiale Approximationsschemata (PTAS, FPTAS), konstante Approximationsalgorithmen, Nicht-Approximierbarkeit, Primal-duales Schema, Iteriertes Runden, Ausiwrkungen des PCP Theorems. Mathematische Grundfertigkeiten und Vorkenntnisse in Optimierung und Algorithmik sind notwendig, um diesem Kurs gut folgen zu können.

Literatur

  • 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.

Operations Research 2 jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch oder englisch
  • Turnus: jedes Sommersemester

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Kenntnisse in linearer Optimierung, grundlegende Kenntnisse ganzzahliger Optimierung etwa aus Operations Research 1 oder gleichwertig, Kenntnis grundlegender Graphenalgorithmen; mathematische Grundfertigkeiten sind unverzichtbar

Modulinhalt

Mathematische Hintergründe, Vertiefungen und Ergänzungen zu den in Operations Research 1 gelehrten Inhalten, insbesondere Komplexität von Problemen und Algorithmen, Polyedertheorie, ganzzahlige Optimierung: total unimodulare Matrizen, TDI-Systeme, Schnittebenenverfahren; gültige Ungleichungen; Facettenbeweise

Lernziele

Die Studierenden erwerben eine vertiefte Kenntnis abstrakter, algorithmischer und struktureller Zusammenhänge der linearen, ganzzahligen und diskreten Optimierung und das auch über konkrete Anwendungen hinaus.

Vorlesungsvideos aus dem SS17 finden sich hier.

 

OR Praktikum jedes Semester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Projektmodul
  • Sprache:de
  • Turnus: jedes Semester

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Kenntnisse in der Modellierung mit ganzzahligen Programmen, grundlegender Algorithmen des Operations Research, sowie sichere Programmierkenntnisse und/oder vertiefte Kenntnis einer algebraischen Modellierungssprache.

Inhalt:

Im Rahmen des OR-Praktikums erfolgt in der Regel die Bearbeitung einer realen Aufgabenstellung aus der Praxis in Kooperation mit einem Unternehmen. Sie bearbeiten hierbei die praktische Aufgabenstellung von A bis Z, d.h. von der Erarbeitung der Problemstellung und der Datenanalyse über die Konzeption und Modellerstellung und Algorithmenentwurf bis hin zur softwaretechnischen Implementierung. Ergebnisse sollen visualisiert, validiert und präsentiert werden. Hierbei arbeiten Sie im interdisziplinären Team aus 5-6 Studierenden der Betriebswirtschaftslehre, der Wirtschaftswissenschaft und des Wirtschaftsingenieurwesens, sowie der Informatik und Mathematik. Kooperationen der Vergangenheit waren z.B. mit INFORM (Aachen) zur Logistik in Containerterminals, Fraport (Frankfurt) zur Steuerung von Gepäckförderanlagen, oder velocity (Aachen) zur Standortplanung von Abstellablagen elektrisch unterstützer Fahrräder.

Ziele:

Vollständige Bearbeitung eines realen praktischen Optimierungsproblems in einem interdisziplinären Team. Erarbeitung von interdisziplinären Kooperations- und Kommunikationsformen, sowie Schulung von Problemlösungs- und Präsentationsfähigkeiten.

Praktische Optimierung mit Modellierungssprachen jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung und Übung
  • Sprache:deutsch oder englisch
  • Turnus: jedes Sommersemester

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Sicherheit in der Modellierung mit linearen und ganzzahligen Programmen. Nützlich sind grundlegende Kenntnisse in der Modellierung mit einer Modellierungssprache etwa aus OR1 oder QM (ideal: Python/Gurobi) sowie eine generelle Fingerfertigkeit am Computer (Umgang mit einem Texteditor, Eingabe von Befehlen auf der Konsole, etc.).

Modulinhalt

Wir modellieren klassische Optimierungsprobleme mit zunehmendem Schwierigkeitsgrad mit dem Python/Gurobi Interface, zB Bin Packing in verschiedenen Varianten, Cutting Stock, Facility Location, TSP, etc.. Dabei werden auch aus OR1 oder CGBP bekannte Algorithmen (Cutting Plane Algorithmen, Column Generation) umgesetzt. Begleitend zur eigentlichen Modellierung enthalten die Aufgaben für der Praxis relevante Anteile wie parsen von Daten, Formatumwandlungen, Datenbereinigung, Visualisierung und Plausibilisierung, Fallstricke im Umgang mit Modellen und Solvern usw.

Lernziele

Wichtigstes Lernziel ist zu verinnerlichen, dass eine Optimierungsaufgabe in der Praxis nicht gelöst ist, wenn man ein mathematisches Modell für sie angeben kann. Ein Großteil der Arbeit entfällt immer noch auf den Umgang mit Daten. Die Studierenden lernen, dass manche Modelle nicht oder nicht zufriedenstellend mit "Standard"lösern gelöst werden und eigene Veränderungen am Algorithmus Abhilfe schaffen können. Plausibilisierung durch zB Visualisierung ist ebenfalls eines der Ziele, sowie generelle Verbesserung im Umgang mit Editor, Kommandozeile, etc.

Quantitative Methoden jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch
  • Turnus: jedes Sommersemester

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Die Schulmathematik sollte man nicht vergessen haben, insbesondere hilft im zweiten Teil der Vorlesung eine Auffrischung der linearen Algebra, Grundkenntnisse wie Matrizenschreibweise von Gleichungssystemen, Matrix-Vektor-Multiplikation usw.

Inhalt:

Die "Quantitativen Methoden" sind unser Basiskurs im Bachelorstudium; er ist mit "Einführung in Operations Research" untertitelt. Die Veranstaltung wird angeboten gemeinsam für Studierende der Mathematik/Informatik mit Anwendungsfach BWL und für Studierende der BWL/Wi.-Ing. Es werden grundlegende Begriffe der Graphentheorie sowie erste Graphenalgorithmen wie Breiten-/Tiefensuche, Kürzeste-Wege-Algorithmen und Netzwerkflussalgorithmen vorgestellt. Der zweite Teil ist eine Einführung in die lineare Optimierung, mit Geometrie, Simplexverfahren, Startbasis, Komplexität, Dualität und Sensitivitätsanalyse, sowie ersten Schritten im Modellieren mit binären Variablen. Die Studierenden lernen eine Modellierungssprache kennen; momentan verwenden wir Python/Gurobi.

Ziele:

Neben dem inhaltlichen Beherrschen grundlegender Algorithmen des Operations Research, Kenntnis derer Anwendungsvoraussetzungen und Anwendung auf konkrete Probleminstanzen stehen zwei Ziele im Vordergrund:1. das Erlernen algorithmischen Denkens; 2. der Erwerb von grundlegenden Kenntnissen und Fähigkeiten in der Modellierung praktisch motivierter Optimierungsprobleme mit Graphen und linearen Programmen.

Literatur

  • 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, December 1996.
  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.
    Introduction to Algorithms. MIT Press, December 2008.

Seminar jedes Semester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Seminar
  • Sprache:de
  • Turnus: jedes Semester

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Je nach Zielgruppe hat unser Seminar unterschiedliche Bezeichnungen, insb. Optimierung und Operations Research und Mathematische Optimierung.

Voraussetzungen:

Seminaristinnen und Seminaristen sollten sich auf dem Weg zur Masterarbeit befinden, also in (auch in der Theorie von) Operations Research und/oder mathematischer Optimierung und/oder theoretischer Informatik gut vorgebildet sein.

Inhalt:

Im Seminar behandeln die Teilnehmenden jeweils ein Thema, zumeist basierend auf einem oder mehreren (aktuellen) wissenschaftlichen Artikeln. Sie sollen ihr Thema tief durchdringen ("Expertin werden") und den anderen Teilnehmenden verständlich präsentieren. Themen sind je nach Semester etwa anwendungsorientierte Artikel, diskrete/kombinatorische Algorithmen, diskrete/ganzzahlige Optimierung, polyedrische Kombinatorik, etc.

Ziele:

Die Studierenden sollen sich in ein begrenztes Themengebiet (der mathematischen Optimierung) auf dem Niveau des Standes der Technik einarbeiten können, dieses durchdringen und anderen Studierenden verständlich präsentieren können. Nicht nur Fachkenntnis spielt dabei eine Rolle, sondern auch Präzision, Organisation, Didaktik und Ästhetik.

Veranstaltungsportfolio

Approximationsalgorithmen unregelmäßig

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung und Übung
  • Sprache:de/en

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Approximationsalgorithmen berechnen Lösungen für Optimierungsprobleme mit einer garantierten Güte in Polynomialzeit. Die Algorithmen selbst sind meißt sehr intuitiv und eher einfach, spannend ist vor allem oft die mathematische Analyse der Gütegarantie. Wir behandeln in dieser Vorlesung verschiedene kombinatorische Optimierungsprobleme, vor allem auf Graphen und Techniken zu deren Approximation, u.a. polynomiale Approximationsschemata (PTAS, FPTAS), konstante Approximationsalgorithmen, Nicht-Approximierbarkeit, Primal-duales Schema, Iteriertes Runden, Ausiwrkungen des PCP Theorems. Mathematische Grundfertigkeiten und Vorkenntnisse in Optimierung und Algorithmik sind notwendig, um diesem Kurs gut folgen zu können.

Literatur

  • 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 jedes Wintersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch oder englisch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Unverzichtbar: Sichere Kenntnisse in linearer/ganzzahliger Optimierung aus "Quantitativen
Methoden" und "Operations Research 1" (BWL) oder "effizienten Algorithmen" (Informatik)
oder "ganzzahliger linearer Optimierung" (Mathematik), d.h. insbesondere Beherrschen von Dualität,
Branch-and-Bound, Modelierung mit ganzzahligen Programmen.

Modulinhalt

Stand der Technik in Modellen und Algorithmen zur Lösung extrem großer und komplexer Optimierungsprobleme, speziell Column Generation und Branch-and-Price: strukturierte ganzzahlige Programme, Dantzig-Wolfe Dekomposition, Lagrange-Relaxation, Schnittebenen in Verbindung mit Column Generation, Branchingregeln, Stabilisierungstechniken, Implementationstricks, praktische Anwendungen

Lernziele

Die Studierenden erwerben grundlegende und fortgeschrittene Fertigkeiten für die Modellierung extrem großer, praktischer Optimierungsprobleme sowie das algorithmische Denken, diese Probleme mit Dekompositionansätzen zu lösen. Im Umgang z.B. mit Modellierungssprachen sollen diese Algorithmen auch praktisch verstanden werden. Die Programmierung von Column Generation in einem algorithmischen Framework wie SCIP soll grundlegend erlernt werden. Die Studierenden sollen in die Lage versetzt werden, Veröffentlichungen auf dem Niveau des aktuellen Standes der Forschung einordnen und verstehen zu können, sowie das Wissen auf praktische Problemstellungen zu übertragen.

 

Literatur

  • Desrosiers, J. and Lübbecke, M.
    Selected Topics in Column Generation. Operations Research, 53(6):1007—1023, November 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, December 2004.

Operations Research 1 jedes Wintersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:englisch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Kenntnisse im Bereich linearer Optimierung und grundlegender Graphenalgorithmen, vor allem zur Modellierung mit Netzwerken und linearen Programmen werden benötigt (und müssen sich ggfs. vorab oder begleitend angeeignet werden).

Modulinhalt

1. Modellierung mit linearen und ganzzahligen Programmen: Zuordnungsprobleme, Knapsack, Standortprobleme, TSP, Tourenplanung/Vehicle Routing, Schedulingprobleme, Set Cover, Set Packing, Set Partitioning, Bin Packing, Cutting Stock, logische Bedingungen; 2. Algorithmen für ganzzahlige Programme: Branch-and-Bound, Schnittebenen, Branch-and-Cut, Dynamische Programmierung; 3. Grundlagen Heuristiken und Metaheuristiken (Eröffnungs- und Verbesserungsheuristiken, Greedy Algorithmen, Lokale Suche, Simulated Annealing, Tabu-Search, Evolutionäre und Genetische Algorithmen); 4. Spezielle Modellierungssituationen wie weiche Bedingungen, Umgang mit Nichtlinearitäten, heuristisches Modellieren; 5. Einführung Komplexitätstheorie

Lernziele

Die Studierenden erlernen Modellierungstechniken und Methoden der ganzzahligen Optimierung, insbesondere deren Einsatzmöglichkeiten und Grenzen. Es soll die Fähigkeit geschult werden, den einer praktischen Aufgabe zugrundeliegenden mathematischen Kern zu identifizieren und dessen Struktur gewinnbringend bei der Auswahl oder Entwicklung von Modellen oder Lösungsalgorithmen einzusetzen. Die theoretischen Kenntnisse werden mit Hilfe von Standardsoftware (zurzeit Gurobi/Python) am Computer an Planungs- und Entscheidungsproblemen vertieft, die an die industrielle Praxis angelehnt sind. Das Abstraktionsvermögen wird geschult.

 

Vorlesungsvideos aus dem WS17/18 finden sich hier.

Operations Research 2 jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch oder englisch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Kenntnisse in linearer Optimierung, grundlegende Kenntnisse ganzzahliger Optimierung etwa aus Operations Research 1 oder gleichwertig, Kenntnis grundlegender Graphenalgorithmen; mathematische Grundfertigkeiten sind unverzichtbar

Modulinhalt

Mathematische Hintergründe, Vertiefungen und Ergänzungen zu den in Operations Research 1 gelehrten Inhalten, insbesondere Komplexität von Problemen und Algorithmen, Polyedertheorie, ganzzahlige Optimierung: total unimodulare Matrizen, TDI-Systeme, Schnittebenenverfahren; gültige Ungleichungen; Facettenbeweise

Lernziele

Die Studierenden erwerben eine vertiefte Kenntnis abstrakter, algorithmischer und struktureller Zusammenhänge der linearen, ganzzahligen und diskreten Optimierung und das auch über konkrete Anwendungen hinaus.

Vorlesungsvideos aus dem SS17 finden sich hier.

 

OR Praktikum jedes Semester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Projektmodul
  • Sprache:de

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Kenntnisse in der Modellierung mit ganzzahligen Programmen, grundlegender Algorithmen des Operations Research, sowie sichere Programmierkenntnisse und/oder vertiefte Kenntnis einer algebraischen Modellierungssprache.

Inhalt:

Im Rahmen des OR-Praktikums erfolgt in der Regel die Bearbeitung einer realen Aufgabenstellung aus der Praxis in Kooperation mit einem Unternehmen. Sie bearbeiten hierbei die praktische Aufgabenstellung von A bis Z, d.h. von der Erarbeitung der Problemstellung und der Datenanalyse über die Konzeption und Modellerstellung und Algorithmenentwurf bis hin zur softwaretechnischen Implementierung. Ergebnisse sollen visualisiert, validiert und präsentiert werden. Hierbei arbeiten Sie im interdisziplinären Team aus 5-6 Studierenden der Betriebswirtschaftslehre, der Wirtschaftswissenschaft und des Wirtschaftsingenieurwesens, sowie der Informatik und Mathematik. Kooperationen der Vergangenheit waren z.B. mit INFORM (Aachen) zur Logistik in Containerterminals, Fraport (Frankfurt) zur Steuerung von Gepäckförderanlagen, oder velocity (Aachen) zur Standortplanung von Abstellablagen elektrisch unterstützer Fahrräder.

Ziele:

Vollständige Bearbeitung eines realen praktischen Optimierungsproblems in einem interdisziplinären Team. Erarbeitung von interdisziplinären Kooperations- und Kommunikationsformen, sowie Schulung von Problemlösungs- und Präsentationsfähigkeiten.

Praktische Optimierung mit Modellierungssprachen jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung und Übung
  • Sprache:deutsch oder englisch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen

Sicherheit in der Modellierung mit linearen und ganzzahligen Programmen. Nützlich sind grundlegende Kenntnisse in der Modellierung mit einer Modellierungssprache etwa aus OR1 oder QM (ideal: Python/Gurobi) sowie eine generelle Fingerfertigkeit am Computer (Umgang mit einem Texteditor, Eingabe von Befehlen auf der Konsole, etc.).

Modulinhalt

Wir modellieren klassische Optimierungsprobleme mit zunehmendem Schwierigkeitsgrad mit dem Python/Gurobi Interface, zB Bin Packing in verschiedenen Varianten, Cutting Stock, Facility Location, TSP, etc.. Dabei werden auch aus OR1 oder CGBP bekannte Algorithmen (Cutting Plane Algorithmen, Column Generation) umgesetzt. Begleitend zur eigentlichen Modellierung enthalten die Aufgaben für der Praxis relevante Anteile wie parsen von Daten, Formatumwandlungen, Datenbereinigung, Visualisierung und Plausibilisierung, Fallstricke im Umgang mit Modellen und Solvern usw.

Lernziele

Wichtigstes Lernziel ist zu verinnerlichen, dass eine Optimierungsaufgabe in der Praxis nicht gelöst ist, wenn man ein mathematisches Modell für sie angeben kann. Ein Großteil der Arbeit entfällt immer noch auf den Umgang mit Daten. Die Studierenden lernen, dass manche Modelle nicht oder nicht zufriedenstellend mit "Standard"lösern gelöst werden und eigene Veränderungen am Algorithmus Abhilfe schaffen können. Plausibilisierung durch zB Visualisierung ist ebenfalls eines der Ziele, sowie generelle Verbesserung im Umgang mit Editor, Kommandozeile, etc.

Polyedrische Kombinatorik jedes Wintersemester

Infos:

  • Verantwortlich Matthias Walter
  • Typ:Vorlesung
  • Sprache:de

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Kenntnisse ganzzahliger und linearer Optimierung (LP-Dualität, Polytope, Totale Unimodularität) und diskreter Mathematik (Graphen, Graphenalgorithmen, Analyse/Komplexiät von Algorithmen); Grundkenntnisse von Problemen der diskreten Optimierung/Operations Research (Knapsack, Matching, Set Cover, Bin Packing, TSP, etc.) hilfreich; mathematische Grundfertigkeiten unverzichtbar.

Inhalt:

In der Veranstaltung werden moderne Techniken und Resultate zu Polyedern aus der Kombinatorischen Optimierung behandelt. Die Vorlesung dient der Einführung der Grundbegriffe, Präsentation wichtiger Resultate und der gemeinsamen Analyse der Beweise. In der Übung werden der Stoff gefestigt und die erlernten Techniken an kleineren Beispielen geübt.

Kapitel: Matroide

Nach der Einführung in die kombinatorische Stuktur der Matroide und Betrachtung einfacher Strukturresultate wenden wir uns dem Lösungsalgorithmus (Greedy) zu. Dessen Funktionsweise liefert uns polyedrische Resultate zu den assoziierten ganzzahligen Hüllen, der Matroidpolytope. Weiterhin zeigen wir, dass sogar der Schnitt zweiter solcher Matroidpolytope ganzzahlig ist (Matroid Intersection) und wie Matroide uns helfen, dass man über submodularen Funktionen in Polynomialzeit optimieren kann.

Kapitel: Relaxierungen

Zunächst betrachten wir Techniken zum Vergleich der Stärke von linearen Relaxierungen, bzw. der Stärke von zusätzlichen Schnittebenenklassen und wenden diese exemplarisch an. Im zweiten Teil geht es um Negativresultate zur (oft exponentiellen) Anzahl der für eine Relaxierung im Originalraum benötigten Ungleichungen.

Kapitel: Erweiterte Formulierungen

Hier betrachten wir das Phänomen, dass bei der Beschreibung eines Polyeders Ungleichungen eingespart werden können, indem man es als Projektion eines höherdimensionalen Polyeders (als Erweiterte Formulierung) beschreibt. Es werden diverse Beispiele und Konstruktionstechniken für Erweiterte Formulierungen sowie eine Technik gezeigt, mit deren Hilfe man die Grenzen dieses Phänomens ausloten kann. Damit zeigen wir, dass das man zur Beschreibung des Cut-Polytops (das mit dem Max-Cut-Problem assoziiert ist) trotz Nutzung von Projektionen exponentiell viele Ungleichungen benötigt.

Kapitel: Äquivalenzen bei 0/1-Polytopen

Wir zeigen, dass folgende Probleme für 0/1-Polytope äquivalent sind:

  1. Das Finden einer Optimallösung
  2. Das Finden einer besseren Lösung (für eine gegebene Lösung)
  3. Das Lösen des Separationsproblems
  4. Das Lösen des primalen Separationsproblems

Hierzu wird unter anderem das zentrale Resultat zur Äquivalenz von Optimieren und Separieren gezeigt.

Ziele:

Neben der Vermittlung der teils klassischen, teils aktuellen Resultate wird vor allem die zugrundeliegende Methodik vermittelt. Sehr viel Wert wird auf die meist geometrische Intuition hinter den Resultaten bzw. Beweisideen gelegt.

Programmieren, Algorithmen, Datenstrukturen zurzeit nicht angeboten

Infos:

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Dieser Kurs wird zurzeit nicht angeboten. Die Ausweichempfehlung: Hören Sie einen Kurs "Programmieren" (zB Programmierung für alle) und einen Kurs "Algorithmen und Datenstrukturen", z.B. in der Aachener Informatik oder als Online Kurs. Diese werden in der Vertiefung ORM anerkannt.

 

Voraussetzungen:

Mathematische Grundfertigkeiten.

Inhalt:

In diesem sehr steilen Kurs erfolgt die Vermittlung von Programmierkenntnissen in einer höheren Programmiersprache wie Java oder Python. Daneben werden grundlegende Algorithmen wie Suchen und Sortieren oder Huffman-Codierung gelernt, sowie Basis-Datenstrukturen wie Arrays, Listen, Stacks, Queues, Heaps, Hashmaps und binäre Suchbäume. Neben regelmäßigen algorithmischen und theoretischen Aufgaben muss fast wöchentlich eine zunehmend anspruchsvollere Programmieraufgabe fehlerfrei testiert werden, was in der Planung wegen eines beachtlichen Zeitaufwandes berücksichtigt werden sollte.

Ziele:

Programmieren ist mehr als das Beherrschen einer Programmiersprache. Die Studierenden sind in der Lage, eine Aufgabe algorithmisch zu strukturieren und in einer Programmiersprache umzusetzen. Dabei bedienen sie sich sinnvoll geeigneter Datenstrukturen und kennen algorithmische Grundprinzipien wie Interation, Rekursion, Divide-and-Conquer, sowie Abstraktionselemente wie Vererbung. Sie bedienen sich eines vereinbarten Programmierstils, kennen elementare Regeln des Erstellens übersichtlichen und wartungsarmen Quellcodes und können angemessen dokumentieren.

 

Literatur

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

Quantitative Methoden jedes Sommersemester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Vorlesung
  • Sprache:deutsch

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Voraussetzungen:

Die Schulmathematik sollte man nicht vergessen haben, insbesondere hilft im zweiten Teil der Vorlesung eine Auffrischung der linearen Algebra, Grundkenntnisse wie Matrizenschreibweise von Gleichungssystemen, Matrix-Vektor-Multiplikation usw.

Inhalt:

Die "Quantitativen Methoden" sind unser Basiskurs im Bachelorstudium; er ist mit "Einführung in Operations Research" untertitelt. Die Veranstaltung wird angeboten gemeinsam für Studierende der Mathematik/Informatik mit Anwendungsfach BWL und für Studierende der BWL/Wi.-Ing. Es werden grundlegende Begriffe der Graphentheorie sowie erste Graphenalgorithmen wie Breiten-/Tiefensuche, Kürzeste-Wege-Algorithmen und Netzwerkflussalgorithmen vorgestellt. Der zweite Teil ist eine Einführung in die lineare Optimierung, mit Geometrie, Simplexverfahren, Startbasis, Komplexität, Dualität und Sensitivitätsanalyse, sowie ersten Schritten im Modellieren mit binären Variablen. Die Studierenden lernen eine Modellierungssprache kennen; momentan verwenden wir Python/Gurobi.

Ziele:

Neben dem inhaltlichen Beherrschen grundlegender Algorithmen des Operations Research, Kenntnis derer Anwendungsvoraussetzungen und Anwendung auf konkrete Probleminstanzen stehen zwei Ziele im Vordergrund:1. das Erlernen algorithmischen Denkens; 2. der Erwerb von grundlegenden Kenntnissen und Fähigkeiten in der Modellierung praktisch motivierter Optimierungsprobleme mit Graphen und linearen Programmen.

Literatur

  • 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, December 1996.
  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.
    Introduction to Algorithms. MIT Press, December 2008.

Seminar jedes Semester

Infos:

  • Verantwortlich Marco Lübbecke
  • Typ:Seminar
  • Sprache:de

Inhalte:

Theorie
Praxis
Modellierung
Programmierung

Je nach Zielgruppe hat unser Seminar unterschiedliche Bezeichnungen, insb. Optimierung und Operations Research und Mathematische Optimierung.

Voraussetzungen:

Seminaristinnen und Seminaristen sollten sich auf dem Weg zur Masterarbeit befinden, also in (auch in der Theorie von) Operations Research und/oder mathematischer Optimierung und/oder theoretischer Informatik gut vorgebildet sein.

Inhalt:

Im Seminar behandeln die Teilnehmenden jeweils ein Thema, zumeist basierend auf einem oder mehreren (aktuellen) wissenschaftlichen Artikeln. Sie sollen ihr Thema tief durchdringen ("Expertin werden") und den anderen Teilnehmenden verständlich präsentieren. Themen sind je nach Semester etwa anwendungsorientierte Artikel, diskrete/kombinatorische Algorithmen, diskrete/ganzzahlige Optimierung, polyedrische Kombinatorik, etc.

Ziele:

Die Studierenden sollen sich in ein begrenztes Themengebiet (der mathematischen Optimierung) auf dem Niveau des Standes der Technik einarbeiten können, dieses durchdringen und anderen Studierenden verständlich präsentieren können. Nicht nur Fachkenntnis spielt dabei eine Rolle, sondern auch Präzision, Organisation, Didaktik und Ästhetik.