 |
Approche par agrégation pour le problème de tension minimum à coûts binaires |
| Bruno Bachelet (LIMOS, Clermont-Ferrand, France) |
| Rapport de recherche LIMOS/RR04-08 Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes Université Blaise Pascal Clermont-Ferrand, France 22 février 2004 |
La technique d'agrégation, dédiée aux graphes série-parallèles et introduite récemment pour résoudre le problème de la tension minimum à coûts linéaires par morceaux, est adaptée ici pour résoudre le problème de la tension minimum à coûts binaires (ou problème BCT). Même sur des graphes série-parallèles, le problème BCT a été prouvé NP-complet. A notre connaissance, l'agrégation est le seul algorithme, avec la programmation linéaire mixte, proposé pour résoudre de manière exacte le problème BCT sur des graphes série-parallèles. Une comparaison de l'efficacité des deux méthodes est présentée ici.
Vous pouvez télécharger les du problème BCT qui ont été utilisées pour les résultats numériques de cet article.