Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Robuste kombinatorische Optimierung

 

Gegenstand dieses Projektes ist die Entwicklung exakter und approximativer Verfahren zur Lösung von kombinatorischen Problemen auf endlichen Graphen unter Unsicherheiten. Die Unsicherheiten sind durch ein System von Ausfallmengen gegeben, die in Abhängigkeit des kombinatorischen Problems aus Knoten oder Kanten bestehen.

Jede Ausfallmenge stellt dabei ein Szenario dar, welches bei Eintritt zur Folge hat, dass die Knoten oder Kanten aus der zugehörigen Ausfallmenge aus dem Graphen gelöscht werden. Das Ziel ist es, für eine gegebene Kostenfunktion eine kostenminimale Kanten- oder Knotenmenge derart zu bestimmen, dass diese für jedes mögliche Szenario eine zulässige Lösung des zugrunde liegenden kombinatorischen Problems enthält (siehe [1,4]).

Im Fokus stehen hierbei insbesondere Untersuchungen zu Matching-Problemen, die vor allem Anwendungen im Bereich der Personal- und Produktionsplanung finden (siehe z. B. [2,3]).

 

 

[1]
David Adjiashvili, Sebastian Stiller, and Rico Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1):361–390, 2015.
URL

[2]
Giuliana Carello and Ettore Lanzarone. A cardinality-constrained robust model for the assignment problem in Home Care services. European Journal of Operational Research, 236(2):748–762, 2014.
URL

[3]
Mabel C. Chou, Geoffrey A. Chua, Chung-Piaw Teo, and Huan Zheng. Process flexibility revisited: The graph expander and its applications. Operations Research, 59(5):1090–1105, 2011.
URL

[4]
Kamal Jain and Vijay V. Vazirani
An approximation algorithm for the fault tolerant metric facility location problem.
In Klaus Jansen and Samir Khuller, editors, Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5–8, 2000 Proceedings, pages 177–182, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
URL