Méthodes de décomposition pour la parallélisation du simplexe en nombres entiers

Le SPP est un problème de la programmation linéaire en nombres entiers qui est utilisé pour modéliser des problèmes industriels dans de nombreux domaines comme la planification des horaires du personnel, la logistique et la reconnaissance de formes. Dans l'industrie de transport, il consiste à partitionner un ensemble de tâches (ex : vols d'avion, segments de trajet d'autobus...) en sous-ensembles (routes de véhicules ou rotations de personnel navigant) de sorte que les sous-ensembles sélectionnés aient un coût total minimal et que chaque tâche appartienne à un seul et unique sous-ensemble. Souvent, il est résolu par la méthode ”branch and bound” ou ses variantes. Ces méthodes s'avèrent lentes dans le cas de problèmes denses de grande taille. Cependant, en industrie, il est apprécié d'avoir une solution rapidement et de tenir compte des informations disponibles telles que l'existence d'une solution initiale notamment lors de la ré-optimisation par exemple. Cet aspect est fourni aisément par les méthodes primales qui, à partir d'une solution initiale, produisent une suite de solutions à coûts décroissants qui converge vers une solution optimale. L'algorithme du simplexe en nombres entiers avec décomposition (ISUD) est une méthode primale qui, à chaque itération, décompose le problème original en deux sous-problèmes. Un premier sous-problème, appelé problème réduit, qui ne considère que les colonnes dites compatibles avec la solution courante, i.e., s'écrivant comme combinaison linéaire de colonnes/variables non dégénérées de la solution courante. Un deuxième sous-problème, appelé problème complémentaire, qui contient seulement les colonnes incompatibles avec la solution courante. Le problème complémentaire permet de trouver une direction de descente composée de plusieurs variables garantissant une solution meilleure, mais pas nécessairement entière. Dans le cas de solutions fractionnaires, un branchement en profondeur permet souvent d'aboutir rapidement à une solution entière. De nos jours, l'informatique connaît des évolutions frappantes. Les transformations que connaît le matériel informatique en termes de vitesse et de puissance sont impressionnantes : un ordinateur portable contemporain est l'équivalent des plus grosses machines des années 1970. Cette évolution induit une transformation du logiciel et des algorithmes aussi profonde, en termes de qualité et de complexité. Par conséquent, la tendance actuelle est de produire des processeurs multicoeurs assimilables à des machines parallèles et de concevoir et implémenter des algorithmes parallèles. L'objectif général de cette thèse est d'étudier les apports du parallélisme à l'algorithme d'ISUD. Le but est de proposer des implémentations parallèles d'ISUD afin d'améliorer ses performances et tirer profit des évolutions contemporaines de l'informatique. Pour concevoir ces algorithmes parallèles, nous avons exploité le parallélisme à l'intérieur d'ISUD et nous avons introduit des décompositions spécifiques au SPP. Dans un premier temps, notre démarche est de grouper les colonnes de la solution courante en clusters afin de décomposer le problème initial en sous-problèmes indépendants. Ces derniers sont résolus en parallèle afin d'améliorer la solution courante par combinaison des solutions optimales des sous-problèmes. Pour cela, nous construisons un graphe dont les noeuds sont les colonnes de la solution courante. Nous attribuons aux arêtes des poids calculés par des fonctions de densité qui utilisent les informations issues du problème original comme le nombre de colonnes qui couvrent des tâches des colonnes Ai et Aj de la solution courante. Le graphe construit est scindé en sous-graphes et par la suite nous obtenons des clusters de la solution courante. Ainsi, nous avons ajouté une deuxième décomposition dynamique à celle qui est déjà intrinsèque à ISUD. Le résultat est un algorithme parallèle, le simplexe en nombres entiers avec double décomposition, baptisé ISU2D. Nous avons testé ce nouvel algorithme sur des instances d'horaires de chauffeurs d'autobus ayant 1600 contraintes et 570000 variables. L'algorithme réduit le temps d'exécution d'ISUD par un facteur de 3, voire 4 pour certaines instances. Il atteint la solution optimale, ou une solution assez proche, pour la majorité de ces instances en moins de 10 min alors que le solveur commercial CPLEX ne parvient pas à trouver une solution réalisable avec un gap moins de 10% après une durée de plus d'une heure d'exécution. L'algorithme ISU2D, dans sa première version, représente une première implémentation parallèle de l'algorithme du simplexe en nombres entiers. Cependant, ISU2D souffre encore de la limitation qui est l'utilisation d'une seule décomposition de la solution courante à la fois. Dans un deuxième temps, nous améliorons ISU2D en généralisant certains aspects de son concept. Notre objectif dans cette étape est d'utiliser plusieurs décompositions dynamiques simultanément. Nous proposons un algorithme, nommé DISUD, distribué à base d'ISUD et du paradigme du système multi-agent (SMA). Chaque agent est une entité qui est, au moins partiellement, autonome et caractérisée par la décomposition dynamique de la solution courante qu'elle applique. Les agents peuvent être indépendants ou coopérants suivant la stratégie adoptée. Ainsi, nous augmentons les performances d'ISU2D et nous tirons profit d'avantage des nouveautés en matériel informatique. Les tests faits sur des instances issues de l'optimisation des horaires du personnel navigant de compagnies aériennes montrent que DISUD fonctionne mieux que DCPLEX, la version distribuée du solveur commercial de pointe CPLEX. Il atteint des solutions de qualité meilleure que le DCPLEX en réduisant le temps d'exécution par un facteur de 4 en moyenne. De plus, il a résolu des instances de grande taille que le DCPLEX n'a pu amélioré après une heure d'exécution. Dans un troisième travail, nous réalisons l'objectif d'intégrer le DISUD dans un environnement de génération de colonnes (GC). Ce choix se justifie par le fait que l'intégration de la méthode de génération de colonnes avec les méthodes d'énumération telle le ”branch and price” est largement utilisé dans l'industrie. ISUD présente du potentiel pour remplacer les méthodes d'énumération usuelles pour résoudre le SPP. Par conséquent, il y a du potentiel à intégrer GC et DISUD pour traiter des problèmes de l'industrie. Nous développons donc DICG la version distribuée de génération de colonnes qui utilise DISUD. Les résultats que nous avons obtenus lors de nos tests ont montré que DICG permet d'avoir des solutions de bonne qualité et réduit le temps de calcul d'un facteur de 2 voire 4 par comparaison avec la DRMH, version distribuée de ” Restricted Master Heuristic”. Avec ces trois travaux, nous pensons avoir réalisé des apports intéressants et amélioré les performances d'ISUD. En outre, nous ouvrons la voie pour des travaux futurs afin d'élargir les utilisations de la version distribuée d'ISUD comme par exemple, rendre les agents plus intelligents via des algorithmes d'apprentissage.