Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorTamby, Satya
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2021-11-26T09:43:45Z
dc.date.available2021-11-26T09:43:45Z
dc.date.issued2021
dc.identifier.issn1091-9856
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22252
dc.language.isoenen
dc.subjectmultiobjective optimizationen
dc.subjectcombinatorial optimizationen
dc.subjectnondominated pointsen
dc.subjectε-constrainten
dc.subject.ddc003en
dc.titleEnumeration of the Nondominated Set of Multiobjective Discrete Optimization Problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameINFORMS Journal on Computing
dc.relation.isversionofjnlvol33en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2021
dc.relation.isversionofjnlpages72-85en
dc.relation.isversionofdoi10.1287/ijoc.2020.0953en
dc.relation.isversionofjnlpublisherINFORMS - Institute for Operations Research and the Management Sciencesen
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2021-11-26T09:41:04Z
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record