An approximation algorithm for multi-objective optimization problems using a box-coverage
Open Access
- 24 November 2021
- journal article
- research article
- Published by Springer Nature in Journal of Global Optimization
- Vol. 83 (2) , 329-357
Abstract
For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the nondominated set. However, often these approximations are used for further evaluations. For those applications a polyhedron is a structure that is not easy to handle. In this paper, we introduce an approximation with a simpler structure respecting the natural ordering. In particular, we compute a box-coverage of the nondominated set. To do so, we use an approach that, in general, allows us to update not only one but several boxes whenever a new nondominated point is found. The algorithm is guaranteed to stop with a finite number of boxes, each being sufficiently thin.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (432218631)
This publication has 37 references indexed in Scilit:
- An objective space cut and bound algorithm for convex multiplicative programmesJournal of Global Optimization, 2013
- A New Scalarization Technique to Approximate Pareto Fronts of Problems with Disconnected Feasible SetsJournal of Optimization Theory and Applications, 2013
- An approximation algorithm for convex multi-objective programming problemsJournal of Global Optimization, 2010
- Improved ε-Constraint Method for Multiobjective ProgrammingJournal of Optimization Theory and Applications, 2008
- Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methodsComputational Optimization and Applications, 2007
- Finding representative systems for discrete bicriterion optimization problemsOperations Research Letters, 2007
- Multiobjective optimization using evolutionary algorithms — A comparative case study1998
- An Overview of Evolutionary Algorithms in Multiobjective OptimizationEvolutionary Computation, 1995
- Scalarizing vector optimization problemsJournal of Optimization Theory and Applications, 1984
- Efficiency in multiple objective optimization problemsMathematical Programming, 1977