Approximation Algorithm Variants for Convex Multiobjective Optimization Problems

Abstract

We consider a Benson type algorithm to ‘solve’ convex multiobjective optimization problems in the sense that it generates inner and outer approximations to the Pareto frontier. In each iteration of the algorithm, a Pascoletti-Serafini scalarization is solved for an arbitrary vertex of the current outer approximation. In this way, it is possible to determine if the vertex is close enough to the Pareto frontier. If not, then the current outer approximation is updated by a cut. This procedure continues until all the vertices are close enough. The update of the outer approximation can be done right after finding the first vertex that is not close enough to the Pareto frontier; or after checking all the vertices. This choice affects the performance of the algorithm. With this study, additional variants that are different than these two extreme ones are proposed and the performances of all these variants are compared via computational tests.

Keywords

• multiobjective optimization algorithms
• convex optimization
• linear programming