Algorithmes d'embaquetage et de couverture fractionnaire

Les problèmes d’empaquetage et de couverture sont des classes généraux de nombreuse applications en réalité. Un cas spécial du problème d’empaquetage est le problème des flots à plusieurs commodités. Ici, on doit transférer les commodités pour remplir les demandes sous les contraintes de capacité...

Full description

Saved in:
Bibliographic Details
Main Author: LE, Duc Phong
Other Authors: PERENNES, Stéphane
Format: Theses and Dissertations
Language:French
Published: 2015
Online Access:http://repository.vnu.edu.vn/handle/VNU_123/79
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Vietnam National University, Hanoi
Language: French
id oai:112.137.131.14:VNU_123-79
record_format dspace
spelling oai:112.137.131.14:VNU_123-792017-04-05T14:15:16Z Algorithmes d'embaquetage et de couverture fractionnaire LE, Duc Phong PERENNES, Stéphane Les problèmes d’empaquetage et de couverture sont des classes généraux de nombreuse applications en réalité. Un cas spécial du problème d’empaquetage est le problème des flots à plusieurs commodités. Ici, on doit transférer les commodités pour remplir les demandes sous les contraintes de capacités des arêtes. Les problèmes de coloration et de découple sont ceux de couverture. Malheureusement, si ces problèmes sont contraints à être entiers alors ils sont NP-Complets. Cependant, on peut trouver une solution d’approximation pour ces problèmes en se basant sur leurs versions fractionnaires. Dans ce rapport, nous présentons une technique de relaxation Lagrangienne pour la conception des algorithmes d’approximation pour des problèmes ci-dessus. L’idée principale est simple : partant du problème initial P, certaines contraintes sont relâchées et remplacées par des pénalités selon le degré de leur violation. En général, on utilise deux types de fonction potentielle exponentielle et logarithmique pour cette technique. Dans ce cadre de ce travail, nous nous concentrons seulement sur des algorithmes qui appliquent la fonction potentielle exponentielle. Nous faisons aussi des études sur le problème des flots à plusieurs commodités. Après, nous faisons aussi une comparaison avec des autres méthodes de génération de chemins dans le cas du flot et de génération de colonnes dans le cas général. Nous décrivons et examinons notre implémentation du problème des flots à plusieurs commodités basée sur l’algorithme d’approximation de Plotkin et al [20, 17]. Leur algorithme est efficace en théorie, cependant une implémentation directe est lent en pratique. Nous modifions cet algorithme et démontrons que sa performance est en pratique garantie comme la prédiction en théorie. 2015-07-14T04:02:07Z 2015-07-14T04:02:07Z 2006 Thesis http://repository.vnu.edu.vn/handle/VNU_123/79 fr application/pdf
institution Vietnam National University, Hanoi
building VNU Library & Information Center
country Vietnam
collection VNU Digital Repository
language French
description Les problèmes d’empaquetage et de couverture sont des classes généraux de nombreuse applications en réalité. Un cas spécial du problème d’empaquetage est le problème des flots à plusieurs commodités. Ici, on doit transférer les commodités pour remplir les demandes sous les contraintes de capacités des arêtes. Les problèmes de coloration et de découple sont ceux de couverture. Malheureusement, si ces problèmes sont contraints à être entiers alors ils sont NP-Complets. Cependant, on peut trouver une solution d’approximation pour ces problèmes en se basant sur leurs versions fractionnaires. Dans ce rapport, nous présentons une technique de relaxation Lagrangienne pour la conception des algorithmes d’approximation pour des problèmes ci-dessus. L’idée principale est simple : partant du problème initial P, certaines contraintes sont relâchées et remplacées par des pénalités selon le degré de leur violation. En général, on utilise deux types de fonction potentielle exponentielle et logarithmique pour cette technique. Dans ce cadre de ce travail, nous nous concentrons seulement sur des algorithmes qui appliquent la fonction potentielle exponentielle. Nous faisons aussi des études sur le problème des flots à plusieurs commodités. Après, nous faisons aussi une comparaison avec des autres méthodes de génération de chemins dans le cas du flot et de génération de colonnes dans le cas général. Nous décrivons et examinons notre implémentation du problème des flots à plusieurs commodités basée sur l’algorithme d’approximation de Plotkin et al [20, 17]. Leur algorithme est efficace en théorie, cependant une implémentation directe est lent en pratique. Nous modifions cet algorithme et démontrons que sa performance est en pratique garantie comme la prédiction en théorie.
author2 PERENNES, Stéphane
author_facet PERENNES, Stéphane
LE, Duc Phong
format Theses and Dissertations
author LE, Duc Phong
spellingShingle LE, Duc Phong
Algorithmes d'embaquetage et de couverture fractionnaire
author_sort LE, Duc Phong
title Algorithmes d'embaquetage et de couverture fractionnaire
title_short Algorithmes d'embaquetage et de couverture fractionnaire
title_full Algorithmes d'embaquetage et de couverture fractionnaire
title_fullStr Algorithmes d'embaquetage et de couverture fractionnaire
title_full_unstemmed Algorithmes d'embaquetage et de couverture fractionnaire
title_sort algorithmes d'embaquetage et de couverture fractionnaire
publishDate 2015
url http://repository.vnu.edu.vn/handle/VNU_123/79
_version_ 1680965543309344768