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.

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.

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.

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.

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.

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.

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.

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.

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.

Dieser Kurs wird nicht mehr 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.

Der berühmte Mathematiker Paul Erdös sagte, dass es ein "Buch der Beweise" gäbe, in dem besonders elegante Beweise stünden. Angelehnt daran haben Aigner und Ziegler im Springer-Verlag so ein Buch zusammen gestellt; es enthält Resultate aus Zahlentheorie, Geometrie, Analysis, Kombinatorik und Graphentheorie und zugehörige, besonders schöne Beweise, meistens sind diese recht kurz. Dieses Proseminar richtet sich an alle, die die Ästhetik der mathematischen Argumentation schätzen, in jedem Vortrag wird es daher sicher auch um einen Beweis gehen.

Als Empfehlung sei auf die Proseminar-Webseite vom i6 verwiesen, nicht nur die Ethischen Richtlinien der Fachgruppe Informatik sind dort interessant.