A Polynomial-Time Inner Approximation Algorithm for Multiobjective and Parametric Optimization

In multiobjective optimization, computing the entire nondominated set (also known as the Pareto front or the Pareto frontier) is often intractable. However, for any multiplicative factor greater than one, an approximation set can be constructed in polynomial time for many problems. In this paper, we use the concept of convex approximation sets: Each point in the nondominated set is approximated by a convex combination of images of solutions in such a set. Convex approximation sets can be used to efficiently approximate multiobjective optimization problems and parametric optimization problems. Recently, a convex approximation algorithm was presented that works in an adaptive fashion and runs faster than all previously existing algorithms. We use a different approach for constructing an even more efficient adaptive algorithm for computing convex approximation sets of multiobjective mixed-integer linear programs. Our algorithm is based on a skeleton algorithm for polyhedral inner approximation. If the weighted sum scalarization can be solved exactly or approximately in polynomial time, our algorithm can find a convex approximation set for an approximation factor arbitrarily close to this solution quality. We demonstrate that our new algorithm runs faster than the current state-of-the-art algorithm on instances of the multiobjective variants of the assignment problem, the knapsack problem, and the symmetric metric traveling salesman problem.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This research was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)—Project number 508981269 and GRK 2982, 516090167 “Mathematics of Interdisciplinary Multiobjective Optimization.”

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1308) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1308). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.