• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2021
Journal name
INFORMS Journal on Computing
Volume
33
Number
1
Publisher
INFORMS - Institute for Operations Research and the Management Sciences
Pages
72-85
Publication identifier
10.1287/ijoc.2020.0953
Metadata
Show full item record
Author(s)
Tamby, Satya
Laboratoire 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; ε-constraint

Related items

Showing items related by title and author.

  • Thumbnail
    Discrete representation of the non-dominated set for multi-objective optimization problems using kernels 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
  • Thumbnail
    Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs 
    Jamain, Florian (2014-06) Thèse
  • Thumbnail
    Discrete representations of the non-dominated set 
    Galand, Lucie; Humbert--Ropers, Marie; Vanderpooten, Daniel (2022-06) Communication / Conférence
  • Thumbnail
    Approximate Pareto sets of minimal size for multi-objective optimization problems 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the number of non-dominated points of a multicriteria optimization problem 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo