Fachvortrag in englischer Sprache

Dank der bahnbrechenden Arbeit von Bertsimas & Sim aus dem Jahr 2003 können wir robuste kombinatorische Optimierungsprobleme unter Budgetunsicherheit theoretisch lösen, indem wir entweder n+1 deterministische Probleme lösen oder eine kompakte LP-Umformulierung vornehmen, die nur zusätzliche kontinuierliche Variablen einführt. Daher steigt die rechnerische Komplexität nicht an. In der Praxis kann sich die Rechenzeit jedoch im Vergleich zur deterministischen Instanz erheblich verlängern. In diesem Vortrag stellen wir zwei Ansätze vor, um die Lösung solcher Probleme zu beschleunigen. Einerseits leiten wir einen maßgeschneiderten Branch-and-Bound-Algorithmus ab. Andererseits zeigen wir, wie gültige Ungleichungen für das deterministische Problem wiederverwendet werden können, um neue gültige Ungleichungen für das robuste Problem zu erhalten. Dies ist eine gemeinsame Arbeit mit Timo Gersing und Christina Büsing.

Referent: Prof. Dr. Arie M.C.A. Koster, Forschungsbereich Diskrete Optimierung, RWTH Aachen