Show simple item record

dc.contributor.advisorVanderpooten, Daniel
dc.contributor.authorLacour, Renaud
dc.creatorLacour, renaud
dc.creatorKlamroth, Kathrin
dc.creatorVanderpooten, Daniel
dc.date2015
dc.date.accessioned2015-03-23T15:34:09Z
dc.date.available2015-03-23T15:34:09Z
dc.date.issued2014-07
dc.identifierhttp://basepub.dauphine.fr/theses/2014PA090067
dc.identifier
dc.identifierhttps://tel.archives-ouvertes.fr/tel-01134242
dc.identifierhttp://www.theses.fr/2014PA090067
dc.identifier2014PA090067
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14806
dc.description.abstractfrOn s'attache dans cette thèse à plusieurs aspects liés à la résolution de problèmes multi-objectifs, sans se limiter au cas biobjectif. Nous considérons la résolution exacte, dans le sens de la détermination de l'ensemble des points non dominés, ainsi que la résolution approchée dans laquelle on cherche une approximation de cet ensemble dont la qualité est garantie a priori.Nous nous intéressons d'abord au problème de la détermination d'une représentation explicite de la région de recherche. La région de recherche, étant donné un ensemble de points réalisables connus, exclut la partie de l'espace des objectifs que dominent ces points et constitue donc la partie de l'espace des objectifs où les efforts futurs doivent être concentrés dans la perspective de déterminer tous les points non dominés.Puis nous considérons le recours aux algorithmes de séparation et évaluation ainsi qu'aux algorithmes de ranking afin de proposer une nouvelle méthode hybride de détermination de l'ensemble des points non dominés. Nous montrons que celle-ci peut également servir à obtenir une approximation de l'ensemble des points non dominés. Cette méthode est implantée pour le problème de l'arbre couvrant de poids minimal. Les quelques propriétés de ce problème que nous passons en revue nous permettent de spécialiser certaines procédures et d'intégrer des prétraitements spécifiques. L'intérêt de cette approche est alors soutenu à l'aide de résultats expérimentaux.en
dc.languageen
dc.languageen
dc.language.isoenen
dc.publisher
dc.subjectOptimisation multi-objectifsen
dc.subjectReprésentation de la région de rechercheen
dc.subjectAlgorithmes de séparation et évaluationen
dc.subjectAlgorithmes de rankingen
dc.subjectProblème de l'arbre couvrant de poids minimalen
dc.subjectMulti-objective optimizationen
dc.subjectRepresentation of the search regionen
dc.subjectBranch and bound algorithmsen
dc.subjectRanking algorithmsen
dc.subjectMinimum spanning tree problemen
dc.subject.ddc003en
dc.subject.classificationjelC6en
dc.titleApproches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimalen
dc.title.alternativeExact and approximate solving approaches in multi-objective combinatorial optimization, application to the minimum weight spanning tree problemen
dc.typeThèseen
dc.subject.classificationrameauOptimisation combinatoire
dc.subject.classificationrameauRecherche opérationnelle
dc.subject.classificationrameauAlgorithmes
dc.subject.classificationrameauGraphes, Théorie des
dc.description.abstractenThis thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results.en
dc.identifier.citationpages123en
dc.identifier.theseid2014PA090067en
dc.subject.ddclabelRecherche opérationnelleen
dc.rights.intranetnonen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record