Servicenavigation

Project Details

Back

Projekt Print View

General approximation methods for multicriteria optimization problems

Subject Area Mathematics
Term from 2018 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 398572517
 
Final Report Year 2023

Final Report Abstract

In many multiobjective optimization problems, the set of Pareto-optimal or efficient solutions – each of which can potentially be relevant for a decision maker – and the associated set of images are enormous and hard to determine exactly. Therefore, approximations aim to reduce the number of required solutions substantially while still guaranteeing a provable solution quality. Approximations are sets of solutions that, for each possible image, contain a solution whose image is component-wise at least as good up to a multiplicative factor. We have provided a general theory of how scalarizations – transformations of the problem into scalar-valued problems by means of weighting and combining the objectives – can be utilized to obtain approximations. In particular, we have introduced a novel transformation theory for scalarizations that establishes that multiobjective minimization and maximization problems can, in principle, be approximated equally well by scalarizations. Supplemented with our in-depth analyses of the well-known weighted sum and weighted Tchebycheff scalarization, scalarizations are now profoundly understood in this context. Additionally, we have related convex approximations – a relaxed notion of approximation – to approximations of multi-parametric optimization problems, for the computation of which we have designed three algorithms (partially with cardinality guarantees) that outperform existing approximation algorithms in both theory and practice. These algorithms and all examined instances are available in a freely accessible and easy-to-use software package. Within this project, we have not only made significant progress on existing notions of approximation, but have also introduced refined notions to delimit more precisely the frontier of existence of polynomial-cardinality approximations and their efficient computability: we have improved upon the seminal existence result for approximations due to Papadimitriou and Yannakakis by showing that polynomial-cardinality one-exact approximations – approximations that are exact in one objective – with approximation factors arbitrarily close to one in the remaining objectives always exist under the same assumptions. This is best possible in the sense that polynomial-cardinality approximations that are exact in more than one objective do, in general, not exist. We have obtained similar results also on quasi-k-exact approximations – in which feasible solutions are approximated exactly in k of the objectives, but the choice of these k objectives differs between different solutions – and multi-factor approximations that use a set of vectors of approximation factors instead of a single one. Complementing our theoretical insights, we have proposed several efficient algorithms (partially with cardinality guarantees) to obtain all these approximations.

Publications

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung