AG Kombinatorische Optimierung

Kombinatorische Optimierung

Semipflichtmodul ``Kombinatorische Optimierung´´
ALG-KO6 (6 LP)

Vertiefungsmodul ``Kombinatorische Optimierung ++´´
ALG-3-C (3 LP)



Inhalt

Graph Kombinatorische Optimierungsprobleme treten bei vielen praktischen Anwendungen auf (z.B. Flugplanung, Produktionsplanung, Transportplanung, Schichtplanung, Logistik).

Nach einer Einführung in verschiedene kombinatorische Optimierungsprobleme werden allgemeine Optimierungsmethoden (exakte und heuristische Verfahren) vorgestellt und an Beispielen aus der Praxis illustriert. Danach werden kombinatorische Optimierungsprobleme behandelt, die sich als lineare Programme formulieren und effizient mit dem Simplexverfahren lösen lassen.

Stichworte: Branch-and-Bound-Algorithmen, Dynamische Programmierung, Constraint Programming, Heuristiken, Lokale Suche, Tabusuche, Genetische Algorithmen, Ameisenalgorithmen, Approximationsalgorithmen mit Gütegarantie, Lineare Programmierung, Simplexverfahren, Spieltheorie

Literatur

Materialien

Materialien KO++

Software

Zur Lösung von LP- und MIP-Problemen wird in den Übungen die SCIP Optimization Suite eingesetzt, die die Programme ZIMPL, SCIP und SoPlex enthält. Diese sind für den akademischen Einsatz frei verfügbar. Die Programme sind auf den CIP-Pool-Rechnern installiert, können aber auch auf dem eigenen Computer verwendet werden.

Um ZIMPL bzw. SCIP in allen Verzeichnissen ausführen zu können, müssen Sie das Installationsverzeichnis in der PATH Variable hinzufügen. Eine Beschreibung dazu finden Sie z.B. hier

Teilnahme

Die Veranstaltung ist vorgesehen für B.Sc. ab dem 3. Semester. Teilnehmen können alle interessierten Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science.

Schein

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der Übungsaufgaben (jeweils 50 % der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche Absolvierung einer Prüfung (Klausur) am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.

Vertiefungsmodul KO++

In diesem Erweiterungsmodul für besonders Interessierte gibt es Vorlesungs- sowie Praktikumsanteile. In Kleingruppen wird eine praktische Aufgabe bearbeitet, zu der ein Bericht zu schreiben ist. Abgabe davon und Abschlusspräsentation im März (27./28.3.25). Zulassung: jeweils 50 % der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben der ersten 4 Übungsblätter