Les problèmes de multiflots entiers permettent de modéliser de nombreux problèmes de transport d'énergie, de routage et de placement dans les réseaux. Nous nous intéressons aux cas particulier des multiflots monoroutés, qui apparaissent dans diverses applications, et qui imposent des valeurs binaires aux variables de flot.
Le problème du monoroutage dans un réseau consiste, étant donnés un graphe (G,E) muni des capacités C, et un ensemble de demandes concurrentes d_i entre les sommets sources s_i et les sommet puits t_i, à trouver un routage dans lequel chaque demande d_i est routée sur un seul chemin reliant s_i à t_i , et cela en respectant les capacités du réseau. Ce problème se modélise sous forme d'un programme linéaire en 0 - 1 qui généralise le problème de bin packing, de partition ou le problème de chemins disjoints, eux même NP-difficiles.
Pour résoudre efficacement ce problème combinatoire et difficile, nous considérons différentes approches et comparons empiriquement leurs performances.
La première approche est basée sur l'étude polyédrale du problème. Dans la littérature, peu d'études ont concerné directement la structure polyédrique du problème du monoroutage. En effet, la plupart des approches de résolution développées sont basées sur des algorithmes d'approximation. Les inégalités de coupe et de couverture ainsi que les inégalités métriques utilisées dans la littérature imposent l'existence de capacités suffisantes sur les liaisons du réseau pour pouvoir acheminer toutes les demandes. Cependant, elles ne permettent pas d'exprimer le fait que chaque demande doit emprunter un seul chemin. L'exploitation de la structure de bin packing, présente dans le problème du monoroutage, permet de développer de nouvelles classes d'inégalités valides qui expriment plus efficacement la contrainte du monoroutage. Nous proposons différentes classes d'inégalités valides implémentées dans un algorithme de Branch-and-cut. Cependant la taille des problèmes résolus par cet algorithme reste limitée.
C'est pourquoi, nous proposons de nouvelles approches combinant l'efficacité des solveurs SAT et des solveurs de la programmation par contraintes avec les méthodes d'optimisation combinatoire pour améliorer les performances de nos algorithmes.
En effet, cette approche consiste à profiter du fait que la modélisation sous la forme d'un programme linéaire en nombres entiers du problème de monoroutage utilise des variables {0,1}. Ces variables de décision étant booléennes, il est donc possible de résoudre ce problème à l'aide des solveurs SAT dits «modernes», souvent très efficaces en pratique. De plus, la forme particulière des contraintes utilisées -- à savoir, des équations ou inéquations linéaires -- permet d'envisager l'utilisation de solveurs pseudo-booléens, qui permettent non seulement de gérer nativement ce type de contraintes, mais également d'appliquer un raisonnement à base de plans-coupant connu pour être plus puissant que celui des solveurs SAT fondés sur la résolution.
Enfin, nous proposons une troisième approche se reposant sur des solveurs de programmation par contraintes. Ces solveurs généralisent les solveurs SAT ou pseudo-booléens en permettant l'utilisation d'une grande variété de contraintes portant sur des variables entières (et en particulier, sur des variables {0,1}). Bien que ne disposant pas d'un système de raisonnement aussi puissant que celui des solveurs SAT, ces solveurs implantent de nombreuses structures de données très efficaces leur permettant d'avoir en pratique de très bons résultats sur une grande variété de problèmes.