.png){kind=icon}
.png){kind=icon}
Return
A Polynomial-Time Inner Approximation Algorithm for Multiobjective and Parametric Optimization
.png){kind=icon}
PRE
AI
DOI：10.1287/ijoc.2025.1308.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
multiobjective mixed-integer optimization
multiobjective approximation
convex approximation sets
parametric optimization
inner approximation algorithm
Journal
I
IF:
2.1
Papers:
86
Citations:
3.2K