Seminarraum 811, Mathematikgebäude

Viele praktische Optimierungsprobleme lassen sich als ganzzahliges Programm formulieren. Diese Technik ist nicht zuletzt deswegen auch in der Praxis so erfolgreich, weil leistungsfähige Lösungsalgorithmen (Branch-and-Bound, Branch-and-Cut) gut implementiert zur Verfugung stehen. Viele Probleme (z.B. Vehicle Routing, Bin Packing, p-Median, Graphenfärbung) führen allerdings auf speziell strukturierte Modelle, die immer öfter mit Branch-and-Price-Algorithmen gelöst werden können. Hierbei wird das originale Modell mit Hilfe einer Dekomposition in ein so genanntes Master- und ein Subproblem umformuliert, so dass die Struktur des Problems ausgenutzt wird und im Allgemeinen z.B. wesentlich verbesserte duale Schranken an das Optimum erzielt werden können (Stichwort: Column Generation). Der Pferdefuss: Alle diese Ansätze erfordern eine eigene Implementation und immer noch ein solides Wissen einer Vielzahl von Details der Algorithmen und Dekompositionen. Wünschenswert wäre also ein „generischer“ Ansatz, der die notwendige Dekomposition automatisch ausführt, falls sie sich anbietet, und einen Branch-and-Price-Algorithmus ohne weiteres Zutun des Benutzers anstösst. In diesem Vortrag berichten wir über jüngste Fortschritte in dieser Richtung.

Prof. Dr. Marco Luebbecke

RWTH Aachen