Allgemeine Approximationsverfahren für multikriterielle Optimierungsprobleme

• Antragsteller: Professor Dr. Stefan Ruzika; Professor Dr. Clemens Thielen
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 398572517

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Bei vielen multikriteriellen Optimierungsproblemen sind die Menge der potentiell für Entscheidungsträger relevanten Pareto-Lösungen und die zugehörige Bildmenge sehr groß und sehr schwer exakt zu bestimmen. Daher zielen Approximationen darauf ab, die Anzahl der erforderlichen Lösungen erheblich zu reduzieren und trotzdem eine beweisbare Lösungsqualität zu garantieren. Eine Approximation ist eine Menge von Lösungen, welche für jede zulässige Lösung eine Lösung enthält, die in jeder Zielfunktion höchstens um einen gegebenen Faktor schlechter ist. Wir haben eine allgemeine Theorie dafür entwickelt wie Skalarisierungen - Überführungen eines multikriteriellen Problems in skalarwertige Ersatzprobleme durch Gewichten und Kombinieren der Zielfunktionen - Zur Berechnung von Approximationen verwendet werden können. Insbesondere haben wir eine neuartige Transformationstheorie für Skalarisierungen entwickelt die zeigt, dass multikriterielle Minimierungs- und Maximierungsprobleme sich prinzipiell gleich gut mittels Skalarisierungen approximieren lassen. Zusammen mit unserer eingehenden Analyse der bekannten Gewichtete-Summe­ und Gewichteten-Tchebycheff-Skalarisierung konnte somit ein umfassendes Verständnis von Skalarisierungen bzgl. Approximation erreicht werden. Zusätzlich haben wir einen engen Zusammenhang zwischen konvexen Approximationen und Approximationen multi-parametrischer Optimierungsprobleme hergestellt, für deren Berechnung wir drei Algorithmen (teilweise mit Kardinalitätsgarantien) entwickelt haben, die bekannte Approximationsalgorithmen in Theorie und Praxis übertreffen. Diese Algorithmen sowie die zugehörigen Instanzen sind als frei zugängliches Softwarepaket verfügbar. Wir konnten in diesem Projekt nicht nur signifikante Fortschritte bzgl. der bekannten Approximationsbegriffe erzielen, sondern haben zusätzlich verfeinerte Approximationsbegriffe entwickelt, um die Grenze der Existenz polynomiell großer Approximationen und deren effizienter Berechenbarkeit genauer abzustecken. Dabei haben wir das wichtige Existenzresultat von Papadimitriou und Yannakakis dahingegen verbessert, dass unter denselben Voraussetzungen sogar polynomiell große Approximationen beliebiger Güte existieren, die in einer Zielfunktion exakt sind. Dieses Ergebnis ist in dem Sinne bestmöglich, dass im Allgemeinen keine polynomiell großen Approximationen existieren, die in mehr als einer Zielfunktion exakt sind. Ähnliche Resultate konnten wir auch erzielen für auf Mengen von Approximationsfaktoren basierende Multi-Faktor-Approximationen sowie für quasi­k-exakte Approximationen, bei denen jede zulässige Lösung in k Zielfunktionen exakt approximiert wird, aber diese Zielfunktionen von der zu approximierenden Lösung abhängen dürfen. Ergänzend zu diesen theoretischen Erkenntnissen haben wir verschiedene effiziente Algorithmen (teilweise mit Kardinalitätsgarantien) zur Berechnung aller dieser Approximationen entwickelt.

Projektbezogene Publikationen (Auswahl)

• An FPTAS for a General Class of Parametric Optimization Problems. Computing and Combinatorics, 25–37.
  Bazgan, Cristina; Herzel, Arne; Ruzika, Stefan; Thielen, Clemens & Vanderpooten, Daniel
  
• An approximation algorithm for a general class of parametric optimization problems. Journal of Combinatorial Optimization, 43(5), 1328-1358.
  Bazgan, Cristina; Herzel, Arne; Ruzika, Stefan; Thielen, Clemens & Vanderpooten, Daniel
  
• One-exact approximate Pareto sets. Journal of Global Optimization, 80(1), 87-115.
  Herzel, Arne; Bazgan, Cristina; Ruzika, Stefan; Thielen, Clemens & Vanderpooten, Daniel
  
• Approximation Methods for Multiobjective Optimization Problems: A Survey. INFORMS Journal on Computing.
  Herzel, Arne; Ruzika, Stefan & Thielen, Clemens
  
• The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems. Theory of Computing Systems, 66(1), 395-415.
  Bazgan, Cristina; Ruzika, Stefan; Thielen, Clemens & Vanderpooten, Daniel
  
• An approximation algorithm for a general class of multi-parametric optimization problems. Journal of Combinatorial Optimization, 44(3), 1459-1494.
  Helfrich, Stephan; Herzel, Arne; Ruzika, Stefan & Thielen, Clemens
  
• Analysis of the weighted Tchebycheff weight set decomposition for multiobjective discrete optimization problems. Journal of Global Optimization, 86(2), 417-440.
  Helfrich, Stephan; Perini, Tyler; Halffmann, Pascal; Boland, Natashia & Ruzika, Stefan
  
• Approximating biobjective minimization problems using general ordering cones. Journal of Global Optimization, 86(2), 393-415.
  Herzel, Arne; Helfrich, Stephan; Ruzika, Stefan & Thielen, Clemens
  
• Approximating multiobjective optimization problems: How exact can you be?. Mathematical Methods of Operations Research, 100(1), 5-25.
  Bazgan, Cristina; Herzel, Arne; Ruzika, Stefan; Thielen, Clemens & Vanderpooten, Daniel
  
• Approximating single- and multi-objective nonlinear sum and product knapsack problems. Discrete Optimization, 48, 100771.
  Boeckmann, Jan; Thielen, Clemens & Pferschy, Ulrich
  
• Using scalarizations for the approximation of multiobjective optimization problems: towards a general theory. Mathematical Methods of Operations Research, 100(1), 27-63.
  Helfrich, Stephan; Herzel, Arne; Ruzika, Stefan & Thielen, Clemens
  
• Efficiently Constructing Convex Approximation Sets in Multiobjective Optimization Problems. INFORMS Journal on Computing.
  Helfrich, Stephan; Ruzika, Stefan & Thielen, Clemens