Gemischt-ganzzahlige nichtlineare multikriterielle Optimierung
Zusammenfassung der Projektergebnisse
Das Ziel dieses Projekts war die Entwicklung eines deterministischen algorithmischen Lösungsverfahrens für multikriterielle gemischt-ganzzahlige nichtlineare Optimierungsprobleme. Für gemischt-ganzzahlige konvexe Optimierungsprobleme, die im Fokus dieses Projekts standen, wurde ein solches Verfahren mit dem Hybrid Patch Decomposition Algorithmus (HyPaD) realisiert. Dieser Algorithmus zerlegt das gemischt-ganzzahlige Problem in kontinuierliche Teilprobleme, indem er die Werte der ganzzahligen Variablen fixiert. Für diese kontinuierlichen Probleme berechnet er iterativ schwach nichtdominierte Punkte unter Verwendung von Techniken der kontinuierlichen multikriteriellen Optimierung. Diese Punkte werden verwendet, um eine globale Oberschrankenmenge für die nichtdominierte Menge des gemischt-ganzzahligen Problems sowie untere Schranken für die nichtdominierten Mengen der kontinuierlichen Teilprobleme zu berechnen und iterativ zu verbessern. Diese unteren Schranken für die Teilprobleme liefern nur dann eine globale Unterschrankenmenge, wenn alle möglichen ganzzahligen Variablenbelegungen enumeriert werden. Um eine solche vollständige Enumeration - insbesondere bei einer großen Anzahl von ganzzahligen Variablen - zu vermeiden, wird gleichzeitig eine globale Unterschrankenmenge berechnet. Dazu werden lineare Relaxierungen des ursprünglichen gemischt-ganzzahligen Problems gelöst, die iterativ verfeinert werden. Skalarisierungen dieser Relaxierungen führen auf gemischt-ganzzahlige lineare Optimierungsprobleme, für die es schnelle Lösungsalgorithmen gibt. Der HyPaD Algorithmus kombiniert also auf geschickte Weise Techniken der kontinuierlichen multikriteriellen Optimierung und der einkriteriellen gemischt-ganzzahligen Optimierung zur Lösung multikriterieller gemischt-ganzzahliger konvexer Optimierungsprobleme. Da alle Techniken innerhalb des Algorithmus vollständig im Bildbereich operieren, können Probleme mit einer großen Anzahl von Optimierungsvariablen gelöst werden. Neben dem Nachweis der Korrektheit und Endlichkeit des Algorithmus wurden umfangreiche numerische Tests durchgeführt. Dazu wurde auch ein Generator für Testinstanzen für multikriterielle gemischt-ganzzahlige nichtlineare Optimierungsprobleme entwickelt. Mit dem Multiobjective Mixed-Integer Branch-and-Bound Algorithmus MOMIBB wurde weiterhin ein Lösungsverfahren für multikriterielle gemischt-ganzzahlige nichtkonvexe Optimierungsprobleme entwickelt. Dieser Algorithmus erzeugt Teilprobleme durch einen geometrischen Branch-und-Bound Ansatz im Urbildbereich. Bildpunkte dieser Teilprobleme werden verwendet, um eine globale Oberschrankenmenge zu berechnen. Darüber hinaus berechnet der Algorithmus untere Schranken für die nichtdominierten Mengen jedes Teilproblems. Auch für diesen Algorithmus wurden Korrektheit und Endlichkeit bewiesen und seine Leistungsfähigkeit in numerischen Tests untersucht. Für jeden der entwickelten Algorithmen ist eine Implementierung auf GitHub frei verfügbar.
Projektbezogene Publikationen (Auswahl)
-
An approximation algorithm for multi-objective optimization problems using a box-coverage. Journal of Global Optimization, 83(2), 329-357.
Eichfelder, Gabriele & Warnow, Leo
-
A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems. Mathematical Methods of Operations Research, 100(1), 291-320.
Eichfelder, Gabriele & Warnow, Leo
-
A Solver for Multiobjective Mixed-Integer Convex and Nonconvex Optimization. Journal of Optimization Theory and Applications, 203(2), 1736-1766.
Eichfelder, Gabriele; Stein, Oliver & Warnow, Leo
-
A test instance generator for multiobjective mixed-integer optimization. Mathematical Methods of Operations Research, 100(1), 385-410.
Eichfelder, Gabriele; Gerlach, Tobias & Warnow, Leo
-
Advancements in the computation of enclosures for multi-objective optimization problems. European Journal of Operational Research, 310(1), 315-327.
Eichfelder, Gabriele & Warnow, Leo
-
Using dual relaxations in multiobjective mixed-integer convex quadratic programming. Journal of Global Optimization, 92(1), 159-186.
De Santis, Marianna; Eichfelder, Gabriele; Patria, Daniele & Warnow, Leo
-
Computing an Approximation of the Non-Dominated Set of Multi-Objective Mixed-Integer Nonlinear Optimization Problems. Series on Computers and Operations Research, 423-474. World Scientific.
Eichfelder, Gabriele & Warnow, Leo
-
Test Instances for Multiobjective Mixed-Integer Nonlinear Optimization. Springer Optimization and Its Applications, 71-99. Springer Nature Switzerland.
Eichfelder, Gabriele; Gerlach, Tobias & Warnow, Leo
