Show simple item record

dc.contributor.authorKlamroth, Kathrin
dc.contributor.authorLacour, Renaud
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2015-04-14T17:40:39Z
dc.date.available2015-04-14T17:40:39Z
dc.date.issued2015
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14945
dc.language.isoenen
dc.subjectlocal upper bounds
dc.subjectMultiple objective programming
dc.subjectgeneric solution approaches
dc.subjectsearch region
dc.subject.ddc003en
dc.titleOn the representation of the search region in multi-objective optimization
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a finite set N of feasible points of a multi-objective optimization (MOO) problem, the search region corresponds to the part of the objective space containing all the points that are not dominated by any point of N, i.e. the part of the objective space which may contain further nondominated points. In this paper, we consider a representation of the search region by a set of tight local upper bounds (in the minimization case) that can be derived from the points of N. Local upper bounds play an important role in methods for generating or approximating the nondominated set of an MOO problem, yet few works in the field of MOO address their efficient incremental determination. We relate this issue to the state of the art in computational geometry and provide several equivalent definitions of local upper bounds that are meaningful in MOO. We discuss the complexity of this representation in arbitrary dimension, which yields an improved upper bound on the number of solver calls in epsilon-constraint-like methods to generate the nondominated set of a discrete MOO problem. We analyze and enhance a first incremental approach which operates by eliminating redundancies among local upper bounds. We also study some properties of local upper bounds, especially concerning the issue of redundant local upper bounds, that give rise to a new incremental approach which avoids such redundancies. Finally, the complexities of the incremental approaches are compared from the theoretical and empirical points of view.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol245
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages767-778
dc.relation.isversionofdoi10.1016/j.ejor.2015.03.031
dc.identifier.urlsitehttp://arxiv.org/abs/1502.06111
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintouien
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-05-30T14:57:49Z


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