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.

Abstract

The Set Partitioning Problem (SPP) is a combinatorial optimization problem, formulated as an integer linear programming model. The SPP aims to find a minimum cost partition of a set of tasks (e.g., flights, customers, ...). The SPP model has two types of constraints: partitioning constraints ensuring that each task is covered exactly once; and side constraints for modeling other aspects of the problem, such as staff availability. The SPP can be used to model several real-world problems such as vehicle routing and crew pairing problems (CPP). The problems mentioned above are usually solved using Branch-and-Price based approaches. Branch-and-Price is a fractional dual method that aims to find integer solutions by ignoring the integrality constraints in the SPP model. Branch-and-Price explores a search tree where each branch node is solved using the column generation method (CG). Despite its wide popularity, Branch-and-Price becomes increasingly slow on very large and difficult problems. Therefore, the expected integer solutions are only obtained in the end of the resolution. Other methods, known as primal methods, are also used to solve the SPP. They look for optimality by improving the current integer solution. These methods start from an initial integer solution which is generally available in industrial contexts. One of the most efficient primal methods is the integral simplex using decomposition (ISUD) algorithm and its two improved variants called ZOOM and I2SUD. This primal algorithm finds a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ISUD is one of the potential primal algorithms that has been able to efficiently solve large SPPs, and so giving a boost of interest towards primal approaches. Even with its two improved variants, ISUD still has two main limitations: i) it assumes that the columns are generated a priori, ii) it does not handle the side constraints commonly encountered in practice. In the first subject of this thesis, we develop an integral column generation (ICG) heuristic that combines ISUD and column generation to solve SPPs with a very large number of variables. Computational experiments on instances of the public transit vehicle and crew scheduling problem (VCSP) and of CPP involving up to 2000 constraints show that ICG clearly outperforms two popular column generation heuristics (RMH : restricted master heuristic and DH : diving heuristic). ICG can yield optimal or near-optimal solutions in less than one hour of computational time, generating up to 300 integer solutions during the solution process. However, ICG cannot solve SPPs with side constraints. In the second subject, we develop a generalized version of ICG, denoted I2CG, that can solve efficiently large-scale set partitioning problems with side constraints (SPPSC). The latter are difficult to handle in the context of primal methods because it can create local minima by cutting all integer extreme points adjacent to the current solution. Computational experiments on instances of the airline crew pairing problem involving up to 1761 constraints show that I2CG is efficient and significantly outperforms DH and RMH. For the largest tested instance, I2CG can produce more than 500 integer solutions leading to an optimal or quasi-optimal (i.e., near-optimal) solution. The third subject proposes a machine learning based improvement process for the I2CG algorithm. Indeed, we use a prediction model to predict with some probability the connections between flights. These probabilities are embedded in the I2CG algorithm to favour the generation of columns with a higher probability of being in the optimal or near-optimal solutions. Computational experiments on 49 instances of the CPP involving up to 1740 flights show that the new version of I2CG is faster than I2CG. It generates a sequence of integer solutions with decreasing costs until reaching an optimal or quasi-optimal solution and the computational time is reduced by 50% on average.