Show simple item record

Solving single and multi-objective combinatorial optimization problems by ordered enumeration

dc.contributor.advisorVanderpooten, Daniel
dc.contributor.authorBelhoul, Lyes*
dc.date.accessioned2015-02-17T12:23:53Z
dc.date.available2015-02-17T12:23:53Z
dc.date.issued2014-12
dc.identifierhttp://basepub.dauphine.fr/theses/2014PA090060
dc.identifier
dc.identifierhttp://www.theses.fr/2014PA090060
dc.identifier2014PA090060
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/14672
dc.description.abstractfrNotre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation.en
dc.languagefr
dc.language.isofren
dc.subjectÉnumération ordonnéeen
dc.subjectBranch and Bounden
dc.subjectProblèmes d’optimisation combinatoire mono et multi-Objectifsen
dc.subjectProblème d’affectationen
dc.subjectProblème du voyageur de commerce asymétriqueen
dc.subjectOrdered Enumerationen
dc.subjectMono and Multi-Objective Combinatorial Optimization Problemsen
dc.subjectAssignment Problemen
dc.subjectAsymmetric Travelling Salesman Problemen
dc.subject.ddc511.6en
dc.subject.classificationjelC61en
dc.titleRésolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnéefr
dc.titleSolving single and multi-objective combinatorial optimization problems by ordered enumerationen
dc.typeThèseen
dc.subject.classificationrameauOptimisation combinatoire
dc.subject.classificationrameauProblème du voyageur de commerce
dc.subject.classificationrameauProblèmes d'affectation (programmation)
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenOur aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.en
dc.identifier.citationpages123en
dc.identifier.theseid2014PA090060en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.rights.intranetnonen
hal.person.labIds*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record