Show simple item record

dc.contributor.authorGaland, Lucie
dc.contributor.authorPerny, Patrice
dc.contributor.authorSpanjaard, Olivier
dc.date.accessioned2011-04-28T09:55:17Z
dc.date.available2011-04-28T09:55:17Z
dc.date.issued2010
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6079
dc.language.isoenen
dc.subjectSubmodular capacity
dc.subjectMultiobjective discrete optimisation
dc.subjectMinimum spanning tree problem
dc.subjectShortest path problem
dc.subjectChoquet integral
dc.subject.ddc003en
dc.titleChoquet-based optimisation in multiobjective shortest path and spanning tree problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper is devoted to the search of Choquet-optimal solutions in finite graph problems with multiple objectives. The Choquet integral is one of the most sophisticated preference models used in decision theory for aggregating preferences on multiple objectives. We first present a condition on preferences (name hereafter preference for interior points) that characterizes preferences favouring compromise solutions, a natural attitude in various contexts such as multicriteria optimisation, robust optimisation and optimisation with multiple agents. Within Choquet expected utility theory, this condition amounts to using a submodular capacity and a convex utility function. Under these assumptions, we focus on the fast determination of Choquet-optimal paths and spanning trees. After investigating the complexity of these problems, we introduce a lower bound for the Choquet integral, computable in polynomial time. Then, we propose different algorithms using this bound, either based on a controlled enumeration of solutions (ranking approach) or an implicit enumeration scheme (branch and bound). Finally, we provide numerical experiments that show the actual efficiency of the algorithms on multiple instances of different sizes.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol204
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages303-315
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2009.10.015
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-09-09T16:22:55Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record