Programmation par contraintes pour le dimensionnement de réseaux en présence de certaines contraintes d'intégrité

Diego Olivier Fernandez Pons

Ilog


Résumé:

Une des principales difficultés des problèmes de dimensionnement de réseaux de télécommunications réside dans le compromis qu'il faut trouver entre qualité de service et coût du réseau. L'utilisation de méthodes de décomposition telles la décomposition de Benders ou le branch-cut-and-price a permis de très importants progrès dans le domaine car elles permettent de traiter assez indépendamment ces deux aspects. Les modèles ont donc pu être complexifiés afin de se rapprocher des problèmes réels.

Ces techniques rencontrent cependant quelques difficultés en présence de certaines contraintes d'intégrité en raison de l'absence de caractérisations polyédrales, par exemple quand on oblige chaque communication à être routée par un chemin unique.

Nous montrerons comment des méthodes de programmation par contraintes, du fait qu'elles explorent directement des espaces de chemins et non de flots permettent de réaliser des solutions simples mais compétitives.


[Diego Olivier Fernandez Pons]
[Ilog]