Although many algorithms for multicriteria optimization provide good approximations, a precise control of their quality is challenging. In this paper we provide algorithmic tools to obtain exact approximation quality values for given approximations and develop a new method for multicriteria optimization guided by this quality. We show that the well-established "-indicator measure is NP-hard to compute when the number of criteria is unlimited already in the case of simple underlying linear optimization problems. Despite this hardness result, we develop a practically efficient method to compute the epsilon-indicator for an arbitrary fixed number of criteria, applicable also to approximations consisting of polyhedra. Based on the corresponding characterization we develop an algorithm for the approximation of Pareto frontiers which computes the -indicator and improves its value in each iteration. Comparisons to other algorithms for multicriteria optimization on benchmarks with two to five criteria show that the performance of our method is competitive.
Citation
Preprint, Fraunhofer ITWM Institute for Industrial Mathematics, Kaiserslautern, Germany, 7/2021
Article
View Precise control of approximation quality in multicriteria optimization