Multikriterielle kombinatorische Optimierung in höheren Dimensionen
Zusammenfassung der Projektergebnisse
Bei Optimierungsproblemen im technischen, ingenieurwissenschaftlichen wie auch im wirtschaftswissenschaftlichen Bereich sind häufig verschiedene, sich widersprechende Optimierungskriterien zu berücksichtigen. Multikriterielle Modelle tragen dieser Tatsache Rechnung und sind darüber hinaus geeignet, zusätzliche Informationen zur Restriktionsbehandlung und zum Umgang mit unsicheren Daten bereitzustellen. Beispiele für multikriterielle kombinatorische Optimierungsprobleme sind multikriterielle Rucksackprobleme, multikriterielle Zuordnungsprobleme und multikriterielle Netzwerkprobleme wie z. B. kürzeste Wege und Netzwerkflussprobleme, spannende Baumprobleme und das Traveling Salesman Problem. Die Anzahl der berücksichtigten Zielfunktionen hat entscheidenden Einfluss auf die Komplexität multikriterieller kombinatorischer Optimierungsprobleme. Während die Pareto-Front bei bikriteriellen Problemen noch vollständig geordnet werden kann – wenn die erste Zielfunktion steigt, fällt die zweite und umgekehrt –, ist dies bei drei und mehr Zielfunktionen nicht mehr möglich. Gleichzeitig mit der drastisch steigenden Zahl nichtdominierter Lösungen steigt damit auch die Komplexität der Pareto-Menge und ihrer Beschreibung. In diesem Projekt wird die geometrische und kombinatorische Struktur der Pareto-Menge genutzt, um sowohl auf theoretischer Ebene als auch auf algorithmischer Ebene entscheidende Fortschritte zu erzielen. Dies umfasst die Bestimmung repräsentativer Kandidatenmengen ebenso wie die Weiterentwicklung multikriterieller Branch-and-Bound-Verfahren und die Analyse verschiedener Präferenzstrukturen und Qualitätsmaße.
Projektbezogene Publikationen (Auswahl)
-
Ordinal costs in multi-objective combinatorial optimization. PhD thesis. University of Wuppertal
J. Sudhoff
-
DefiningPointAlgorithm
K. Dachert, T. Fleuren & K. Klamroth
-
Multi-objective matroid optimization with ordinal weights. Discrete Applied Mathematics, 335, 104-119.
Klamroth, Kathrin; Stiglmayr, Michael & Sudhoff, Julia
-
Ordinal optimization through multi-objective reformulation. European Journal of Operational Research, 311(2), 427-443.
Klamroth, Kathrin; Stiglmayr, Michael & Sudhoff, Julia
-
Theoretical Aspects of Subset Selection in Multi-Objective Optimisation. Natural Computing Series, 213-239. Springer International Publishing.
Guerreiro, Andreia P.; Klamroth, Kathrin & Fonseca, Carlos M.
-
A simple, efficient and versatile objective space algorithm for multiobjective integer programming. Mathematical Methods of Operations Research, 100(1), 351-384.
Dächert, Kerstin; Fleuren, Tino & Klamroth, Kathrin
-
Augmenting bi-objective branch and bound by scalarization-based information. Mathematical Methods of Operations Research, 100(1), 85-121.
Bauß, Julius & Stiglmayr, Michael
-
On improvements of multi-objective branch and bound. EURO Journal on Computational Optimization, 12, 100099.
Bauß, Julius; Parragh, Sophie N. & Stiglmayr, Michael
-
On Improvements of Multi-objective Branch and Bound. PhD thesis. University of Wuppertal
J. Bauß
-
A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization. Computers & Operations Research, 183, 107140.
Lopes, Gonçalo; Klamroth, Kathrin & Paquete, Luís
-
An output-polynomial time algorithm to determine all supported efficient solutions for multi-objective integer network flow problems. Discrete Applied Mathematics, 376, 1-14.
Könen, David & Stiglmayr, Michael
-
On Supportedness in Multi‐Objective Integer Linear Programming. Journal of Multi-Criteria Decision Analysis, 32(3).
Könen, David & Stiglmayr, Michael
-
“On Multi-objective Integer Network Flow Problems”. submitted. PhD thesis. University of Wuppertal
D. Konen
-
Output-sensitive complexity of multi-objective integer network flow problems. Journal of Combinatorial Optimization, 51(2).
Könen, David & Stiglmayr, Michael
