Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorJamain, Florian*
dc.contributor.authorVanderpooten, Daniel*
dc.date.accessioned2016-12-01T17:06:55Z
dc.date.available2016-12-01T17:06:55Z
dc.date.issued2017
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16037
dc.language.isoenen
dc.subjectMultiple objective programming
dc.subjectPareto set
dc.subjectNon-dominated points
dc.subjectDiscrete representation
dc.subjectExact and approximation algorithms
dc.subjectkernel
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleDiscrete representation of the non-dominated set for multi-objective optimization problems using kernels
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we are interested in producing discrete and tractable representations of the set of non-dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These representations must satisfy some conditions of coverage, i.e. providing a good approximation of the non-dominated set, spacing, i.e. without redundancies, and cardinality, i.e. with the smallest possible number of points. This leads us to introduce the new concept of (ε, ε′)-kernels, or ε-kernels when ɛ′=ɛ is possible, which correspond to ε-Pareto sets satisfying an additional condition of ε′-stability. Among these, the kernels of small, or possibly optimal, cardinality are claimed to be good representations of the non-dominated set. We first establish some general properties on ε-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an ε-kernel of small size or, for a fixed size k , an ε-kernel with a nearly optimal approximation ratio 1+ɛ. For more than two objectives, we show that ε-kernels do not necessarily exist but that (ε, ε′)-kernels always exist. Nevertheless, we show that the size of a smallest (ε, ε′)-kernel can be very far from the size of a smallest ε-Pareto set.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol260
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2017
dc.relation.isversionofjnlpages814-827
dc.relation.isversionofdoi10.1016/j.ejor.2016.11.020
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-03-22T14:21:33Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01505519*


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