Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems

Satya Tamby () and Daniel Vanderpooten ()
Additional contact information
Satya Tamby: Université Paris Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, 75016 Paris, France
Daniel Vanderpooten: Université Paris Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, 75016 Paris, France

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 72-85

Abstract: 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.

Keywords: multiobjective optimization; combinatorial optimization; nondominated points; ?-constraint (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2020.0953 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:72-85

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().