An approximation algorithm for multi-objective optimization problems using a box-coverage

Gabriele Eichfelder(gabriele.eichfeldertu-ilmenau.de)
Leo Warnow(leo.warnowtu-ilmenau.de)

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: multi-objective optimization, approximation algorithm, nondominated set, enclosure, box-coverage

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Global Optimization

Citation:

Download: [PDF]

Entry Submitted: 10/29/2020
Entry Accepted: 10/29/2020
Entry Last Modified: 10/29/2020

Modify/Update this entry