Un algorithme pour le déploiement des réseaux FTTH

International audienceLe problème de déploiement optimal d'un réseau FTTH (Fiber To The Home) consiste à concevoir un plan d'installation de fibres optiques de coût minimal permettant de connecter un ensemble de clients à un noeud de raccordement via un ensemble de coupleur. Nous présentons une modélisation de ce problème basée sur le concept de flot avec multiplicateurs et nous montrons comment obtenir par génération de colonnes une solution optimale fractionnaire du programme linéaire correspondant. Cette approche nécessite de résoudre à chaque itération un problème de plus court chemin généralisé multi-contraint. Pour cela, nous décrivons un algorithme pseudo-polynomial qui généralise au cas avec multiplicateurs l'algorithme de plus court chemin multi-contraint introduit dans [DS88]