Étude et séparation des inégalités valides pour des problèmes de partitionnement et de couverture

Cette thèse s'intéresse aux inégalités valides et leurs algorithmes de séparation pour les problèmes de partitionnement et de couverture suivants : le problème d'horaires de véhicules avec plusieurs dépôts (Multiple Depot Vehicle Scheduling Problem, MDVSP), le problème de partitionnement d'ensemble (Set Partitioning Problem, SPP) et le problème du transversal de circuits de cardinalité minimale (MINimum cardinality Feedback Vertex Set problem, MIFVS). Notons que les inégalités valides introduites sont aussi applicables à d'autres problèmes ayant des structures similaires aux problèmes étudiés. Dans la première partie de cette thèse, nous présentons un algorithme combinant la méthode d'élimination de variables, la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants pour la résolution du MDVSP. Nous utilisons la formulation mathématique de multi-flot dans les réseaux, proposée par Ribeiro et Soumis (1994). Pour réduire la taille du problème nous débutons par l'application de la méthode d'élimination de variables. Dans la première phase, nous appliquons une proposition énoncée par Nemhauser et Wosley (1988) et dans la deuxième phase, nous utilisons le principe introduit par Irnich et al.(2010) mais sans génération de colonnes. Ensuite, afin d'améliorer la valeur de la borne inférieure, nous décrivons une méthode de génération de plans coupants. Cette dernière est basée sur une généralisation des inégalités valides introduites par Hadjar et al. (2006). Pour séparer ces inégalités valides, nous proposons d'identifier deux structures particulières propres au MDVSP. Par la suite, nous comparons la performance de différentes stratégies de notre algorithme à l'aide des instances générées aléatoirement. Finalement, nous concluons qu'en général notre algorithme est meilleur que le solveur commercial CPLEX. La première méthode de séparation proposée pour identifier la première structure, que nous nommons structure de cycle impair conflictuel, utilise la similitude entre le problème du stable et le MDVSP. Notre méthode consiste à construire un graphe de conflit à l'aide d'un sous-ensemble d'arcs possédant certaines propriétés dans le multigraphe représentant le MDVSP. Nous prouvons qu'un trou impair dans le graphe de conflit correspond à un cycle impair conflictuel dans le multigraphe du MDVSP. Afin d'identifier les trous impairs nous adaptons l'algorithme proposé par Nemhauser et Sigismondi (1992). En outre, nous démontrons que chaque cycle impair conflictuel permet d'obtenir une inégalité valide violée par la solution fractionnaire courante. Afin d'enrichir ces inégalités, nous décrivons une procédure de liftage. La deuxième méthode de séparation proposée pour identifier la deuxième structure, que nous nommons structure de coupe impaire, exploite la ressemblance entre le problème de couplage et le MDVSP et, par conséquent, entre les inégalités valides du MDVSP et les inégalités d'Edmonds (1965). La relation entre les deux problèmes est basée sur le principe de conflit, pour le problème de couplage, deux arêtes adjacentes sont toujours en conflit et pour le MDVSP deux sous-chemins adjacents peuvent être en conflit s'ils ont la même source ou le même puits ou s'ils sont de couleurs différentes), donc si nous remplaçons un sous-chemin par une arête, alors les inégalités d'Edmonds engendrent des inégalités valides du MDVSP. Afin d'identifier des structures de coupes impaires, nous construisons un graphe de chemins réguliers, où un chemin régulier est une suite d'arcs de même couleur. Ensuite, nous formulons le problème de séparation comme un programme linéaire en nombres entiers et nous prouvons que certaines solutions entières de ce dernier nous permettent d'identifier des inégalités de coupe impaire. Afin de l'enrichir, nous proposons une procédure de liftage. Nous démontrons que chaque coupe impaire liftée correspond à une inégalité valide pour le MDVSP. Dans la deuxième partie de cette thèse, nous proposons la résolution du problème de partitionnement d'ensemble par une méthode combinant la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants. Notons que nous nous intéressons au problème de partitionnement pur. Nous introduisons deux nouvelles classes d'inégalités valides: nommées les inégalités de type I et de type II, pour le problème de partitionnement. En outre, nous formulons le problème de séparation de chaque classe d'inégalités valides comme un programme linéaire en nombres entiers et nous montrons que certaines solutions entières de ce dernier permettent d'identifier des inégalités valides pour le problème de partitionnement. Ensuite, nous proposons de séparer les inégalités de clique en résolvant un autre problème auxiliaire en nombres entiers. Enfin, nous analysons l'efficacité de notre algorithme en utilisant quelques instances de Hoffman et Padberg (1993) et d'autres générées aléatoirement à l'aide du générateur proposé par Lewis et al. (2008). Finalement, nous concluons que notre algorithme est plus efficace que CPLEX lorsque la densité du problème à résoudre est supérieure à 16% et ne l'est pas dans le cas contraire. Dans la dernière partie de cette thèse, nous présentons une méthode combinant la génération de contraintes et des plans coupants afin de résoudre une variante du problème de transversal de circuits de cardinalité minimale. Ce dernier est relié à l'analyse des dictionnaires des langues naturelles. Nous nous intéressons à un des problèmes de linguistique qui consiste à déterminer le nombre minimum de mots à connaître pour comprendre toutes les définitions d'un dictionnaire donné. Ce problème est formulé comme un problème de transversal de circuits de cardinalité minimale. Nous décrivons des méthodes de séparation de trois classes d'inégalités valides : deux classes particulières des inégalités de Chvátal-Gomory et les inégalités de clique de cardinalité 3. Nous formulons le problème de séparation de chaque classe comme un programme linéaire en nombres entiers et nous démontrons que certaines solutions entières permettent d'identifier des inégalités valides pour le problème à résoudre. Enfin, nous présentons et nous analysons les résultats des tests effectués à l'aide des exemplaires extraits de dictionnaires de langue anglaise. Malheureusement, les résultats obtenus ne sont pas concluants étant donné que pour certaines instances nous n'avons pas réussi à trouver les solutions optimales en utilisant le solveur commercial, ni à prouver l'optimalité en utilisant notre algorithme. Néanmoins, nous constatons que l'ajout des inégalités valides permet de trouver de meilleures solutions réalisables dans le temps limite imparti et dans certains cas à trouver la solution optimale. Les travaux présentés dans cette thèse constituent une démarche basée sur les caractéristiques du problème à résoudre. Notre objectif est de présenter de nouveaux algorithmes efficaces pour la séparation des inégalités valides, permettant l'amélioration de la valeur de la relaxation linéaire, mais « bien qu'on ait du cœur à l'ouvrage, l'art est long et le temps est court ». (Charles Baudelaire, Les fleurs du mal).