Advancements in the computation of enclosures for multi-objective optimization problems

A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. One advantage of enclosures is that they can be computed working almost entirely in the criterion space and hence avoiding the typical shortcomings of decision space based approaches, e.g., branch-and-bound approaches. A quite general framework to compute an enclosure is the box approximation algorithm as recently used in the solver called BAMOP. In this paper we show how that framework can be simplified and improved significantly, especially concerning its practical numerical use. In fact, we show for selected numerical instances that our new approach is up to eight times faster than the original one. Moreover, for the first time we describe a warm start strategy for the computation of an enclosure which has not been done in the literature so far. We show that the presented framework is not only of theoretical but also of practical use, e.g., for continuous convex or mixed-integer quadratic optimization problems.

Citation

Published in European Journal of Operational Research (https://doi.org/10.1016/j.ejor.2023.02.032)

Article

Download

View Advancements in the computation of enclosures for multi-objective optimization problems