Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems
Tamby, Satya; Vanderpooten, Daniel (2021), Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems, INFORMS Journal on Computing, 33, 1, p. 72-85. 10.1287/ijoc.2020.0953
Type
Article accepté pour publication ou publiéDate
2021Journal name
INFORMS Journal on ComputingVolume
33Number
1Publisher
INFORMS - Institute for Operations Research and the Management Sciences
Pages
72-85
Publication identifier
Metadata
Show full item recordAuthor(s)
Tamby, SatyaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Vanderpooten, Daniel
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.Subjects / Keywords
multiobjective optimization; combinatorial optimization; nondominated points; ε-constraintRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
-
Jamain, Florian (2014-06) Thèse
-
Galand, Lucie; Humbert--Ropers, Marie; Vanderpooten, Daniel (2022-06) Communication / Conférence
-
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2015) Article accepté pour publication ou publié
-
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié