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é...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| 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 |
| Summary: | 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. |
|---|