Text

Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems

In this paper, we propose a generic algorithm to compute exactly the set of nondominated points for multiobjective discrete optimization problems. Our algorithm extends the ε-constraint method, originally designed for the biobjective case only, to solve problems with two or more objectives. For this purpose, our algorithm splits the search space into zones that can be investigated separately by solving an integer program. We also propose refinements, which provide extra information on several zones, allowing us to detect, and discard, empty parts of the search space without checking them by solving the associated integer programs. This results in a limited number of calls to the integer solver. Moreover, we can provide a feasible starting solution before solving every program, which significantly reduces the time spent for each resolution. The resulting algorithm is fast and simple to implement. It is compared with previous state-of-the-art algorithms and is seen to outperform them significantly on the experimented problem instances.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON COMPUTING; Vol.33 No.1 Winter 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 72 - 85

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

COMBINATORIAL OPTIMIZATION
MULTIOBJECTIVE OPTIMIZATION
NONDOMINATED POINTS
E-CONSTRAINT

Info Detail Spesifik

https://doi.org/10.1287/ijoc.2020.0953

Pernyataan Tanggungjawab

Satya Tamby, Daniel Vanderpooten

Versi lain/terkait

Lampiran Berkas

Komentar