A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems

Abstract

General multi-objective optimization problems are often solved by a sequence of parametric single objective problems, so-called scalarizations. If the set of nondominated points is finite, and if an appropriate scalarization is employed, the entire nondominated set can be generated in this way. In the bicriteria case it is well known that this can be realized by an adaptive approach which, given an appropriate initial search space, requires the solution of a number of subproblems which is at most two times the number of nondominated points. For higher dimensional problems, no linear methods were known up to now. We present a new procedure for finding the entire nondominated set of tricriteria optimization problems for which the number of scalarized subproblems to be solved is at most three times the number of nondominated points of the underlying problem. The approach includes an iterative update of the search space that, given a (sub-)set of nondominated points, describes the area in which additional nondominated points may be located. In particular, we show that the number of boxes, into which the search space is decomposed, depends linearly on the number of nondominated points.

32 pages, 8 figures, Journal of Global Optimization, 2014

References in corpus (1)

• Multi-objective integer programming: An improved recursive algorithm

Cited by in corpus (7)

• The Hypervolume Indicator: Problems and Algorithms
• On the representation of the search region in multi-objective optimization
• Effective anytime algorithm for multiobjective combinatorial optimization problems
• CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines
• An improved hyperboxing algorithm for calculating a Pareto front representation
• Branch-and-bound for biobjective mixed-integer linear programming
• Learning to Project in Multi-Objective Binary Linear Programming