Algorithmes d'embaquetage et de couverture fractionnaire

- Nous faisons aussi des études sur le problème des flots à plusieurs commodités.
- Nous décrivons et examinons notre implémentation du problème des flots à plu- sieurs commodités basée sur l’algorithme d’approximation de Plotkin et al [20, 17]..
- 5.4 La solution des flots.
- A.1 Diagrame de classes de la bibliothèque Mascopt.
- 30 5.1 Quelques fonctions principales pour le problème des flots.
- Les problèmes d’empaquetage et de couverture fractionnaire sont généraux pour plusieurs applications en réalité, par exemple : le problème des flots maximum, sac à dos, coloration.
- Elle a prouvé le caractère polynomiale de la programmation linéaire..
- En réalité, la complexité est peut-être polynôme de la taille très grandes de données d’entrées.
- dans le cas de la génération de chemins pour le problème des flots.
- Un problème d’empaquetage peut être formulé comme des problèmes de la programmation linéaire.
- La complexité de la résolution par programmation linéaire standard n’est cependant pas toujours satisfaisante.
- ²)b pour le problème d’empaquetage).
- pour le problème d’empaquetage et O(m + ρ log 2 m + ² −2 ρ log(m² −1.
- pour le problème de couverture.
- Un problème important traité dans le cadre d’empaquetage est le problème des flots à plusieurs commodités.
- – Modifier et implémenter l’algorithme de Rao et al.
- [20, 17, 5] pour le problème des flots à plusieurs commodités..
- La réalisation de cet objectif implique la poursuite de recherches de haut niveau dans les domaines de l’algorithmique, de la simulation et des mathématiques discrètes..
- Dans le chapitre 2, nous rappelons un peu de la théorie de graphe.
- Et puis, nous discutons des algorithmes d’approximation basés sur la méthode de la fonction potentielle exponentielle pour le problème d’empaquetage et de couverture fraction- naire dans le chapitre 3.
- Nous examinerons également l’algorithme de Plotkin et al..
- Le chapitre 4 aborde le problème des flots à plusieurs commodités.
- Dans ce chapitre, nous présentons l’algorithme de Fleischer [5] et celui de Plotkin et al..
- Le premier a utilisé le problème le chemin le plus court comme le problème dual.
- Dans le chapitre 5, nous décrirons notre implémentations pour le problème des flots à plusieurs commodités.
- Notre implémentation est basé sur l’algorithme de Rao et al [20, 17, 5].
- On considère généralement que le problème des ponts de Königsberg (chercher un parcours eulérien qui passe exactement une fois par chaque arête), résolu par Euler, est le premier résultat formel de la théorie des graphes.
- On trouve des applications de la théorie des graphes en informatique : recherche opérationnelle, théorie des jeux et théorie de la décision..
- Définition 7 (Coupe Minimum (MinCut)) Le problème de la Coupe Minimum consiste à trouver une coupe C min entre s et t de capacité minimale..
- Le problème NP -Complet le plus célèbre est le problème satisfaisant.
- Définition 11 (Facteur d’approximation) Soit OP T (I) est la valeur d’une so- lution optimale pour l’entrée I, et soit ALG(I) est la valeur de la solution retournée par l’algorithme A pour l’entrée I.
- Mesure : La cardinale de la coloration..
- Donc, le problème de coloration fractionnaire devient un problème de flots sur A(P.
- Dans ce chapitre, nous faisons revoir quelques résultats fondamentaux de la mé- thode fonction potentielle exponentielle qui est développée milieu les années 90.
- Les fonctions potentielles exponentielles est introduites dans le domaine d’optimisation par Motzkin (1952) qui a suggéré des méthodes de la descente de type gradient pour résoudre des systèmes des inégalités linéaires.
- ont obtenu un schéma d’approximation totalement en temps polynomial pour le problème des flots uniforme de concurrencegrâce à cette méthode.
- D’abord, nous représenterons l’algorithme d’approximation de base pour des pro- blèmes d’empaquetage et de couverture fractionnaire basé sur la méthode de la fonc- tion potentielle exponentielle.
- Ensuite, nous analyserons l’algorithme de Plotkin et al.
- Ce problème est appelé le problème d’empaquetage fractionnaire..
- Le problème de couverture est également considéré similairement..
- Il est un facteur bien connu parmi les praticiens de la relaxation Lagrangienne qu’une formulation de programmation linéaire devrait autant que possible utiliser des bornes supérieures "petites".
- Dans [1], Bienstock a généralement introduit une méthode de la fonction poten- tielle exponentielle..
- la deuxième étape réalise une pro- cédure de la recherche binaire.
- Dans la partie suivante, nous allons examiner l’algorithme de Plotkin et al.
- Après, nous représentons l’algorithme pour le problème d’empaquetage fraction- naire, celui pour le problème de couverture fractionnaire est pareil..
- On va analyser la convergence de la fonction potentielle exponentielle présentée par Plotkin et al [20] pour le problème d’empaquetage fractionnaire..
- La dualité de la programmation linéaire nous donne une caractéristique de la solution optimale.
- 1 tel que x et sa solution dual correspondante y ont la valeur de la fonction potentielle Φ et ne pas satisfaire P 2.
- Preuve : À partir de la définition de ρ, on a Ax ≤ ρb et A˜ x ≤ ρb.
- Rappelez que, pendant cette procé- dure, σ = 4αρ ² , qui implique que la diminution de la fonction potentielle après chaque itération est Ω.
- Supposons qu’on est donné une sous-tâche rapide pour résoudre le problème d’optimisation suivant pour A et P.
- 1, si le problème GÉNÉRAL a une so-.
- Dans d’autre travaux concernant la méthode de la fonction potentielle logarithmique modifiée de Karmarkar, J.
- Afin que nous puissions obtenir la solution optimale, nous doivent questionner un oracle pour obtenir un élément de la solution à la fois - et malheureusement, cet oracle souffre de l’aspect aléatoire.
- Les développements algorithmiques reliés à la technique d’arrondissement in- conscient ont fourni le point de départ pour une nouvelle ligne de la recherche qui continue toujours, et qui a produit les algorithmes les plus efficaces pour le divers problèmes type-flots, incluant le problème des flots concurrents maximums.
- L’algorithme pour le problème des flots concurrents maximums donné dans [7], [5] évite la dépendance de la paramètre de largeur, là-bas, au lieu d’acheminer tout la demande des commodités le long d’un chemin le plus court, des flots sont acheminés beaucoup plus soigneusement.
- Le problème des flots est un cas spécial du problème d’empaquetage.
- D’abord, pour le problème du flot maximum f de s à t, si on le considère comme une solution d’optimisation de la polytope P ⊆ R m , où P est une combinaison convexe des che- mins (s, t) soumettre aux contraintes de capacité.
- En même façon, on peut formuler le problème des flots maximums en mettant P = P 1 x...xP k , où P i est le polytope qui représente l’espace de la solution de la commodité i, et Ax ≤ b présente des contraintes de capacité..
- Dans la partie ci-dessous, nous présentons l’algorithme de Fleischer et celui de Plotkin et al.
- L’algorithme dans [5] a considéré le problème de chemin le plus court comme la dualité de ce problème.
- Cet algorithme est une amélioration par rapport au cadre de travaux de Grag et Könemann [7], en fait au lieu de chercher le chemin le plus court dans toutes les commodités, il le calcule seulement pour chaque commodité selon la fonction de la longueur actuelle.
- Le problème résolu est appelé le problème des flots concur- rents maximums..
- L’algorithme dans [17] utilise une procédure relâchée d’optimalité pour résoudre le problème des flots concurrents maximums..
- e kf i ∗ (e)kl(e) dans le problème auxiliaire..
- Cela peut être calculé en utilisant l’algorithme pour le problème de flot maximum.
- Tous les deux algorithmes au-dessus recheminent en fait itérativement des com- modités afin de produire un nouveau flot qui est plus près de l’optimalité à partir de la solution initiale P .
- Cependant, l’algorithme dans [17] rechemine une commodité.
- est une fonction de la longueur [17].
- 4.1) fait de la synthèse et de la comparaison de la différence entre l’algorithme de Plotkin et al [20, 17] et celui de Fleischer [5]..
- Shahrokhi et Matula [23] ont proposé un schéma d’approximation en temps polynomial pour le problème des flots concurrents maximums avec des capacités uniforme en se basant sur la fonction potentielle exponentielle.
- Implémentation du problème des flots à plusieurs commodités.
- Dans ce chapitre, nous présentons nos implémentations pour le problème des flots à plusieurs commodités.
- Le temps de calculs de l’algorithme dépend beaucoup de la valeur de α.
- Changement de la taille du réseau.
- 5.1 – Quelques fonctions principales pour le problème des flots.
- 5.4 – La solution des flots.
- Nous avons également fait des études sur le problème des flots à plusieurs com- modités.
- Nous avons décrit et examiné notre implémentation du problème des flots à plusieurs commodités basée sur l’algorithme d’approximation de Plotkin et al [20, 17].
- A.1 – Diagrame de classes de la bibliothèque Mascopt.
- <Y>0.0</Y>.
- <X>0.0</X>.
- En pratique on peut procéder de la manière suivante : On instancie un objet de type MascoptViewer.
- Et tout devrait s’afficher de la manière souhaitée..
- Dans ce cas, il n’y a pas de solution optimale puisqu’il est possible de construire des solutions satisfaisant aux contraintes avec des valeurs arbitrairement élevées (ou basses) de la fonction objectif..
- de la programmation linéaire générale est définie par : maximiser c T x.
- x n demande de minimiser (ou maximiser) la valeur de la fonction d’objective qui est définie comme une com- binatoire linéaire des variables dans x soumettre au ensemble de m d’égalités ou d’inégalités..
- L’algorithme simplexe permet de résoudre les problèmes de la programmation linéaire en construisant tout d’abord une solution faisable qui est un sommet du po- lytope puis en se déplaçant selon les arêtes du polytope pour atteindre des sommets pour lesquels la valeur de l’objectif est de plus en plus grande, jusqu’à atteindre l’optimum.
- Cette méthode est elle-même une généralisation de la méthode de l’ellipsoïde optimisation convexe due à Arkadi Nemirovski, et à D.
- Pour la résolution pratique de problèmes de la programmation linéaire ordinaires, on utilise actuellement deux méthodes : la méthode simplexe dérivée et celle du point intérieur..
- 47 La théorie de la dualité est aussi un résultat très important de la programmation linéaire.
- Les algorithmes abordés dans des parties au-dessus sont également considérés en même temps comme la méthode primale - duale et la technique de la relaxation Lagrangienne..
- La méthode primale-duale pour des algorithmes d’approximation considère en même temps toutes les deux une formulation de programmation entière du problème primale et la dualité d’une relaxation de programmation linéaire de la programma- tion entière..
- Si il n’existe pas aucun, ceci donne une manière de modifier la solution duale pour augmenter la dualité de la valeur objective..
- L’idée de la relaxation Lagrangienne est simple..
- Attendons que pour n’importe quelles valeurs fixées de y i , la valeur optimale du programme relâchée (D.2) est une borne inférieure que OP T , où OP T est la valeur optimum du programme origine (D.1).
- Les fonctions potentielles exponentielles ont été introduites dans l’optimisation par Motzkin (1952) qui a suggéré des méthodes de la descente de type gradient pour résoudre des systèmes linéaire des inégalités.
- Shahrokhi et Matula (1990) [23] ont obtenu un schéma d’approximation totalement en temps polynomial pour le problème des flots uniforme de concurrence.
- Des bornes de la complexité de la coordination le plus connu ont été actuellement fournis pour tous les deux problèmes linéaire et non-linéaire par Grigoriadis et Khachiyan (1994) [9]..
- La solution du problème orginal peut être calculée à travers le problème suivant