Algorithmes d'embaquetage et de couverture fractionnaire

• 主要作者: LE, Duc Phong
• 其他作者: PERENNES, Stéphane
• 格式: Theses and Dissertations
• 語言: French
• 出版: 2015
• 在線閱讀: http://repository.vnu.edu.vn/handle/VNU_123/79

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.