 |
Étude de formulations étendues pour le problème de l'arbre couvrant budgeté
1 : Laboratoire dánalyse et modélisation de systèmes pour láide à la décision
Centre National de la Recherche Scientifique : UMR7243 / FRE3234 / UMR7024, Université Paris Dauphine-PSL
2 : LAMSADE
Université Paris IX - Paris Dauphine
Nous considérons le problème de l'arbre couvrant budgeté avec une approche basée sur la programmation mathématique. Les contraintes de sac à dos vont venir modifier la structure du polyèdre de l'arbre couvrant. L'objectif principal de notre travail est de
trouver des formulations étendues ainsi que des inégalités valides et facettes afin de concevoir des algorithmes de branchements efficaces pour résoudre ces problèmes de réseaux budgétés.
