Optimization Online


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

Gabriele Eichfelder(gabriele.eichfelder***at***tu-ilmenau.de)
Leo Warnow(leo.warnow***at***tu-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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society