Génération de colonnes en nombres entiers pour les problèmes de type partitionnement d'ensemble

Le problème de partitionnement d'ensemble (SPP : Set Partitioning Problem) est un problème d'optimisation combinatoire, se formulant comme un modèle de programmation linéaire en nombres entiers. L'objectif du SPP est de trouver une partition d'un ensemble de tâches (e.g., vols, clients, ...) à coût minimum. Le modèle du SPP est composé de deux types de contraintes : les contraintes de partitionnement qui assurent que chaque tâche soit couverte exactement une fois, et des contraintes supplémentaires qui permettent de modéliser d'autres aspects du problème traité comme les disponibilités du personnel. Le SPP permet de modéliser plusieurs problèmes rencontrés dans l'industrie comme les problèmes de tournées de véhicules et de rotations d'équipages dans le domaine aérien (CPP : crew pairing problem). Les problèmes mentionnés ci-dessus sont généralement résolus à l'aide de la méthode Branchand- Price. C'est une méthode duale fractionnaire dont l'objectif est de trouver des solutions entières en ignorant, dans un premier temps, les contraintes d'intégralité sur les variables du modèle de SPP. Pour ce faire, Branch-and-Price explore un arbre de branchement où chaque noeud de branchement est résolu à l'aide de la méthode de génération de colonnes. Malgré sa popularité, Branch-and-Price peut être lente dans le cas de problèmes difficiles de très grande taille. Par conséquent, les solutions entières recherchées ne sont obtenues que vers la fin de la résolution. D'autres méthodes, dites primales, sont également utilisées pour résoudre le SPP. Elles cherchent une solution optimale en améliorant à chaque itération la solution entière courante. À l'itération 0, ces méthodes partent d'une solution entière initiale qui est généralement disponible pour les problèmes industriels. Parmi les méthodes primales efficaces, on trouve l'algorithme du simplexe en nombres entiers avec décomposition (ISUD) et ses deux variantes améliorées nommées ZOOM et I2SUD. Cet algorithme primal trouve une séquence de solutions entières avec des coûts décroissants, menant à une solution optimale ou quasioptimale. ISUD est l'un des algorithmes primaux potentiels qui a pu résoudre efficacement des problèmes SPP de grande taille. Ceci a vivifié l'intérêt que l'on commence à porter aux approches primales. Malgré ses deux variantes améliorées, ISUD a cependant deux limitations majeures : i) il suppose que les colonnes sont générées a priori, ii) il ne gère pas les contraintes supplémentaires, souvent rencontrées en milieux pratiques. Ceci dit, et à l'instar de ces constats, nous proposons dans le cadre de cette thèse trois sujets pour remédier aux limitations précédemment soulevées. Dans le premier sujet, nous proposons une méthode de génération de colonnes en nombres entiers (ICG) qui combine ISUD et la génération de colonnes pour résoudre des problèmes de partitionnement avec un très grand nombre de variables. ICG génère une séquence de solutions entières avec des coûts décroissants, menant à une solution optimale ou quasi-optimale. Des expérimentations numériques sur des instances du CPP et du problème d'horaires de chauffeurs et d'autobus (VCSP : vehicle and crew scheduling problem), impliquant jusqu'à 2000 contraintes montrent que ICG surpasse nettement deux heuristiques populaires de génération de colonnes. ICG trouve des solutions optimales ou quasi-optimales en moins d'une heure de temps de résolution, en générant jusqu'à 300 solutions entières pendant le processus de résolution. Cependant, ICG ne permet pas de résoudre les SPPs avec des contraintes supplémentaires, d'où le deuxième sujet de cette thèse. Dans le deuxième sujet, nous proposons une version améliorée d'ICG, notée I2CG, qui peut résoudre efficacement des problèmes de partitionnement d'ensembles de grande taille avec des contraintes supplémentaires. Ces dernières sont difficiles à gérer dans le contexte des méthodes primales car elles peuvent créer des minimums locaux en coupant tous les points extrêmes entiers adjacents à la solution courante. Les expérimentations numériques sur des instances du CPP impliquant jusqu'à 1761 contraintes montrent que I2CG est efficace et surpasse largement deux heuristiques populaires de génération de colonnes. Pour la plus grande instance testée, I2CG a pu produire en moins d'une heure de temps de calcul plus que 500 solutions entières menant à une solution optimale ou quasi-optimale. Le troisième sujet porte sur l'amélioration de la méthode I2CG à l'aide des techniques d'apprentissage machine. En effet, nous utilisons un modèle de prédiction pour prédire avec une certaine probabilité les connexions entre les vols dans le CPP. Ces probabilités sont incorporées dans la méthode I2CG pour favoriser la génération des colonnes ayant une plus grande probabilité d'appartenir à des solutions optimales ou quasi-optimales. Les tests effectués sur 49 instances de CPP, impliquant jusqu'à 1740 vols, montrent clairement que la nouvelle version d'I2CG est plus rapide que I2CG. En effet, la nouvelle version génère et trouve aussi une séquence de solutions entières avec des coûts décroissants jusqu'à atteindre une solution optimale ou quasi-optimale en réduisant le temps de résolution total de 50% en moyenne.