• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée

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

Belhoul, Lyes (2014), Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée, thèse de doctorat préparée sous la direction de Vanderpooten, Daniel, Université Paris Dauphine, 123 p.

Voir/Ouvrir
2014PA090060.pdf (779.8Kb)
Type
Thèse
Date
2014-12
Pages
123
Métadonnées
Afficher la notice complète
Auteur(s)
Belhoul, Lyes
Sous la direction de
Vanderpooten, Daniel
Résumé (FR)
Notre 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.
Résumé (EN)
Our 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.
Mots-clés
Énumération ordonnée; Branch and Bound; Problèmes d’optimisation combinatoire mono et multi-Objectifs; Problème d’affectation; Problème du voyageur de commerce asymétrique; Ordered Enumeration; Mono and Multi-Objective Combinatorial Optimization Problems; Assignment Problem; Asymmetric Travelling Salesman Problem
JEL
C61 - Optimization Techniques; Programming Models; Dynamic Analysis

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 
    Lacour, Renaud (2014-07) Thèse
  • Vignette de prévisualisation
    Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems 
    Cornu, Marek (2017-12-18) Thèse
  • Vignette de prévisualisation
    Détermination de solutions de meilleur compromis pour les problèmes d'optimisation combinatoire multiobjectif 
    Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2013) Communication / Conférence
  • Vignette de prévisualisation
    Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs 
    Jamain, Florian (2014-06) Thèse
  • Vignette de prévisualisation
    Conception d’une procédure de recherche de solutions de compromis pour le problème d’affectation multi-objectif 
    Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo