Approximation Methods for Multiobjective Optimization Problems
The project "Approximation Methods for Multiobjective Optimization Problems" is part of "Project-Based Personnel Exchange Programme (PPP)" of the DAAD and is funded from 01st January 2018 to 31st December 2019.
Typically, multiobjective optimization problems (MOPs) are solved according to the Pareto principle of optimality: A solution is called Pareto optimal (or efficient) if no other feasible solution exists that is at least as good in all criteria and better in at least one criterion. Each of these efficient solutions corresponds to a different compromise among the set of objectives and is potentially relevant for a decision maker. Therefore, the goal of multiobjective optimization is to compute the set of efficient solutions (the efficient set) or a good representation of it.
Several results in the literature have shown that MOPs can be hard to solve even if the corresponding single objective version is solvable in polynomial time. In addition, the cardinality of the efficient set (or even its image) may be exponentially large. The idea of approximating the efficient set has existed for a long time and a bandwidth of specific (mostly combinatorial) problems can be approximated more or less efficiently. In contrast, only few general results are known concerning the approximation of MOPs.
The classical notion of multiobjective approximation results from a straightforward extension of the analogous notion used in single objective optimization: Instead of providing a single approximation factor stating how well the objective value of any feasible solution of a single objective problem is approximated in the worst case, the notion for multiobjective problems provides a single vector of approximation factors, which states how good any feasible solution is approximated in the worst case in all the different objective functions. This, however, does not allow to express trade-offs between the approximation of the different objective functions since the vector of approximation factors needs to contain the worst case approximation factor obtained for any solution in each component, even though the actual approximation factor obtained in a given objective may be far better for most of the solutions.
Consequently, this project aims at studying a new notion of approximation for multiobjective problems, called multi-factor approximation, which allows for a set of different approximation vectors and ensures that every efficient solution is approximated with some approximation vector from this set. This generalizes the classical notion of approximation, but leads to a more accurate description of the obtained approximation quality.
Within the project, we will explore and apply the new multi-factor definition of approximation for multiobjective optimization problems with the aim of obtaining tight and accurate approximation results. This goal will be pursued for general MOPs as well as for MOPs with a specific structure.
LAMSADE (Laboratoire d'Analyse et Modélisation de Systèmes pour l'Aide à la Décision), Université Paris Dauphine, Paris, France