Efficiently Constructing Convex Approximation Sets in Multiobjective Optimization Problems

Stephan Helfrich (), Stefan Ruzika () and Clemens Thielen ()
Additional contact information
Stephan Helfrich: Department of Mathematics, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Kaiserslautern 67663, Germany
Stefan Ruzika: Department of Mathematics, Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Kaiserslautern 67663, Germany
Clemens Thielen: Campus Straubing for Biotechnology and Sustainability, Technical University of Munich, Straubing 94315, Germany

INFORMS Journal on Computing, 2025, vol. 37, issue 5, 1223-1241

Abstract: Convex approximation sets for multiobjective optimization problems are a well-studied relaxation of the common notion of approximation sets. Instead of approximating each image of a feasible solution by the image of some solution in the approximation set up to a multiplicative factor in each component, a convex approximation set only requires this multiplicative approximation to be achieved by some convex combination of finitely many images of solutions in the set. This makes convex approximation sets efficiently computable for a wide range of multiobjective problems: even for many problems for which (classic) approximations sets are hard to compute. In this article, we propose a polynomial-time algorithm to compute convex approximation sets that builds on an exact or approximate algorithm for the weighted sum scalarization and is therefore applicable to a large variety of multiobjective optimization problems. The provided convex approximation quality is arbitrarily close to the approximation quality of the underlying algorithm for the weighted sum scalarization. In essence, our algorithm can be interpreted as an approximate version of the dual variant of Benson’s outer approximation algorithm. Thus, in contrast to existing convex approximation algorithms from the literature, information on solutions obtained during the approximation process is utilized to significantly reduce both the practical running time and the cardinality of the returned solution sets while still guaranteeing the same worst-case approximation quality. We underpin these advantages by the first comparison of all existing convex approximation algorithms on several instances of the triobjective knapsack problem and the triobjective symmetric metric traveling salesman problem.

Keywords: multiobjective optimization; approximation algorithm; convex approximation sets; Benson’s method (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0220 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:5:p:1223-1241

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().