184. Generalizing Hyperboxing Algorithms for Diverse Domination Cones
Invited abstract in session TA-5: Multiobjective Optimization 1: Non-standard Dominance Cones, stream Decision Theory and Multi-criteria Decision Making.
Thursday, 8:45-10:15Room: H7
Authors (first author is the speaker)
| 1. | Mara Schubert
|
| Optimization, Fraunhofer ITWM |
Abstract
Explicitly calculating the non-dominated set of a multi-criteria optimization (MCO) problem is seldom possible. Instead, many algorithms aim to determine a set of points that effectively represent the entire non-dominated set.
Among such algorithms are hyperboxing algorithms. These algorithms divide the objective space into hyperrectangles to iteratively reduce the area where additional non-dominated points may exist. A key concept is that identifying a non-dominated point allows excluding the area dominated by this point and the area where any point would dominate it. The remaining space is divided into boxes, and a solution to the MCO problem within the largest such box is sought.
Most hyperboxing algorithms are designed for MCO problems with respect to the positive orthant as domination cone. This is reflected in two stages: once when solving the MCO problem and once when constructing the boxes. We present an adaptation of a hyperboxing algorithm where the construction of boxes is not necessarily based on the domination cone, provided certain conditions are met. This adaptation does not change the convergence properties of the algorithm. However, it significantly generalizes the types of domination cones that can be addressed by the hyperboxing algorithm. Notably, it is applicable even to non-polyhedral domination cones, making it more versatile than many other algorithms that systematically enhance approximation quality in the objective space.
Keywords
- Multi-Objective Decision Making
- Multi-Objective Programming
- Approximation Algorithms
Status: accepted
Back to the list of papers