Méthodes pour favoriser l'intégralité de l'amélioration dans le simplexe en nombres entiers - Application aux rotations d'équipages aériens

Dans son cadre le plus général, le processus d'optimisation mathématique se scinde en trois grandes étapes. La première consiste à modéliser le problème, c'est-à-dire le représenter sous la forme d'un programme mathématique, ensemble d'équations constitué d'un objectif à minimiser ou maximiser (typiquement, les coûts ou le bénéfice de l'entreprise) et de contraintes à satisfaire (contraintes opérationnelles, convention collective, etc.). Aux décisions à prendre correspondent les variables du problème. S'il est une représentation parfaite de la réalité, ce modèle est dit exact, sinon il reste approximatif. La seconde étape du processus est la résolution de ce programme mathématique. Il s'agit de déterminer une solution respectant les contraintes et pour laquelle la valeur de l'objectif est la meilleure possible. Pour ce faire, on applique généralement un algorithme de résolution, ensemble de règles opératoires dont l'application permet de résoudre le problème énoncé au moyen d'un nombre fini d'opérations. Un algorithme peut être traduit grâce à un langage de programmation en un programme exécutable par un ordinateur. L'exécution d'un tel programme permet ainsi de résoudre le programme mathématique. Enfin, la dernière étape consiste à ajuster la solution obtenue à la réalité. Dans le cas où le modèle n'est qu'approximatif, cette solution peut ne pas convenir et nécessiter d'être modifiée a posteriori afin de s'accorder aux exigences de la réalité concrète. Cette thèse se concentre sur la seconde de ces trois étapes, l'étape de résolution, en particulier sur le développement d'un algorithme de résolution d'un programme mathématique précis, le partitionnement d'ensemble. Le problème de partitionnement d'ensemble permet de modéliser des applications variées : planification d'emplois du temps, logistique, production d'électricité, partage équitable, reconnaissance de forme, etc. Pour chacun de ces exemples l'objectif et les contraintes prennent des significations physiques différentes, mais la structure du modèle est la même. D'un point de vue mathématique, il s'agit d'un programme linéaire en nombres entiers, dont les variables sont binaires, c'est-à-dire qu'elles ne peuvent prendre que les valeurs 0 et 1. Le programme est linéaire car l'objectif et les contraintes sont représentés par des fonctions linéaires des variables. Les algorithmes les plus couramment utilisés pour la résolution de tels problèmes sont basés sur le principe de séparation et évaluation (branch-and-bound). Dans ces méthodes, les contraintes d'intégralité sont d'abord relâchées : les solutions peuvent alors être fractionnaires. La résolution du programme ainsi obtenu – appelé relaxation linéaire du programme en nombres entiers – est bien plus simple que celle du programme en nombres entiers. Pour obtenir l'intégralité, on sépare le problème afin d'éliminer les solutions fractionnaires. Ces séparations donnent naissance à un arbre de branchement où, à chaque noeud, la relaxation d'un problème de partitionnement de la taille du problème original est résolue. La taille de cet arbre, et donc le temps d'exécution, croissent exponentiellement avec la taille des instances. De plus, l'algorithme utilisé pour résoudre la relaxation, le simplexe, fonctionne mal sur des problèmes dégénérés, c'est-à-dire dont trop de contraintes sont saturées. C'est malheureusement le cas de nombreux problèmes issus de l'industrie, particulièrement du problème de partitionnement dont le taux de dégénérescence est intrinsèquement élevé. Une autre approche de ce type de problèmes est celle des algorithmes primaux : il s'agit de partir d'une solution entière non optimale, de trouver une direction qui mène vers une meilleure solution entière, puis d'itérer ce processus jusqu'à atteindre l'optimalité. À chaque étape, un sous-problème d'augmentation est résolu : trouver une direction d'amélioration (ou d'augmentation) ou affirmer que la solution courante est optimale. Les travaux concernant les méthodes primales sont moins nombreux que ceux sur le branch-and-bound, qui représentent depuis quarante ans la filière dominante pour la résolution de problèmes en nombres entiers. Développer une méthode primale efficace en pratique constituerait ainsi un changement majeur dans le domaine. Des travaux computationels sur des algorithmes primaux ressortent deux principaux défis rencontrés lors de la conception et l'implémentation de ces méthodes. D'une part, de nombreuses directions d'amélioration sont irréalisables, c'est-à-dire qu'effectuer un pas, aussi petit soit-il, dans ces directions implique une violation des contraintes du problème. On parle alors de dégénérescence ; c'est par exemple le cas des directions associées à certains pivots de simplexe (pivots dégénérés). Les directions irréalisables ne permettent pas à l'algorithme de progresser et peuvent mettre en péril sa terminaison s'il est impossible de déterminer de direction réalisable. D'autre part, lorsqu'une direction d'amélioration réalisable pour la relaxation linéaire a été déterminée, il est difficile de s'assurer que la solution vers laquelle elle mène est entière. Parmi les algorithmes primaux existants, celui qui apparait comme le plus prometteur est le simplexe en nombres entiers avec décomposition (Integral Simplex Using Decomposition, ISUD) car il intègre au cadre primal des techniques de décomposition permettant de se prémunir des effets néfastes de la dégénérescence. Il s'agit à notre connaissance du premier algorithme de type primal capable de battre le branch-and-bound sur des instances de grande taille ; par ailleurs, la différence est d'autant plus importante que le problème est grand. Bien que fournissant des éléments de réponse à la problématique de la dégénérescence, cette méthode n'aborde pas pour autant la question de l'intégralité lors du passage à une solution de meilleur coût ; et pour qu'ISUD puisse envisager de supplanter les méthodes de type branch-and-bound, il lui faut parcourir cette deuxième moitié du chemin. Il s'agit là de l'objectif de ce doctorat : augmenter le taux de directions entières trouvées par ISUD pour le rendre applicable aux instances industrielles de grande taille, de type planification de personnel. Pour aller dans cette direction, nous approfondissons tout d'abord les connaissances théoriques sur ISUD. Formuler ce dernier comme un algorithme primal, comprendre en quoi il se rattache à cette famille, le traduire pour la première fois dans un langage exclusivement primal sans faire appel à la dualité, constituent le terreau de cette thèse. Cette analyse permet ensuite de mieux décrire la géométrie sous-jacente ainsi que les domaines de réalisabilité des différents problèmes linéaires considérés. Quand bien même ce pan majeur de notre travail n'est pas présenté dans cette thèse comme un chapitre à part entière, il se situe indubitablement à l'origine de chacune de nos idées, de nos approches et de nos contributions. Cette approche de l'algorithme sous un angle nouveau donne lieu à de nombreuses simplifications, améliorations et extensions de résultats déjà connus. Dans un premier temps, nous généralisons la formulation du problème d'augmentation afin d'augmenter la probabilité que la direction déterminée par l'algorithme mène vers une nouvelle solution entière. Lors de l'exécution d'ISUD, pour déterminer la direction qui mènera à la solution suivante, on résout un programme linéaire dont la solution est une direction d'amélioration qui appartient au cône des directions réalisables. Pour s'assurer que ce programme est borné (les directions pourraient partir à l'infini), on lui ajoute une contrainte de normalisation et on se restreint ainsi à une section de ce cône. Dans la version originelle de l'algorithme, les coefficients de cette contrainte sont uniformes. Nous généralisons cette contrainte à une section quelconque du cône et montrons que la direction réalisable déterminée par l'algorithme dépend fortement du choix des coefficients de cette contrainte ; il en va de même pour la probabilité que la solution vers laquelle elle mène soit entière. Nous étendons les propriétés théoriques liés à la décomposition dans l'algorihtme ISUD et montrons de nouveaux résultats dans le cas d'un choix de coefficients quelconques. Nous déterminons de nouvelles propriétés spécifiques à certains choix de normalisation et faisons des recommandations pour choisir les coefficients afin de pénaliser les directions fractionnaires au profit des directions entières. Des résultats numériques sur des instances de planification de personnel montrent le potentiel de notre approche. Alors que la version originale d'ISUD permet de résoudre 78% des instances de transport aérien du benchmark considéré, 100% sont résolues grâce à l'un, au moins, des modèles que nous proposons. Dans un second temps, nous montrons qu'il est possible d'adapter des méthodes de plans coupants utilisés en programmation linéaire en nombres entiers au cas d'ISUD. Nous montrons que des coupes peuvent êtres transférées dans le problème d'augmentation, et nous caractérisons l'ensemble des coupes transférables comme l'ensemble, non vide, des coupes primales saturées pour la solution courante du problème de partitionnement. Nous montrons que de telles coupes existent toujours, proposons des algorithmes de séparation efficaces pour les coupes primales de cycle impair et de clique, et montrons que l'espace de recherche de ces coupes peut être restreint à un petit nombre de variables, ce qui rend le processus efficace. Des résultats numériques prouvent la validité de notre approche ; ces tests sont effectués sur des instances de planification de personnel navigant et de chauffeurs d'autobus allant jusqu'à 1 600 contraintes et 570 000 variables. Sur les instances de transport aérien testées l'ajout de coupes primales permet de passer d'un taux de résolution de 70% à 92%. Sur de grandes instances d'horaires de chauffeurs d'autobus, les coupes prouvent l'optimalité locale de la solution dans plus de 80% des cas. Dans un dernier temps, nous modifions dynamiquement les coefficients de la contrainte de normalisation lorsque la direction trouvée par l'algorithme mène vers une solution fractionnaire. Nous proposons plusieurs stratégies de mise-à-jour visant à pénaliser les directions fractionnaires basées sur des observations théoriques et pratiques. Certaines visent à pénaliser la direction choisie par l'algorithme, d'autres procèdent par perturbation des coefficients de normalisation en utilisant les équations des coupes mentionnées précédemment. Cette version de l'algorithme est testée sur un nouvel ensemble d'instances provenant de l'industrie du transport aérien. À notre connaissance, l'ensemble d'instances que nous proposons n'est comparable à aucun autre. Il s'agit en effet de grands problèmes d'horaires de personnel navigant allant jusqu'à 1 700 vols et 115 000 rotations, donc autant de contraintes et de variables. Ils sont posés sous la forme de problèmes de partitionnement pour lesquels nous fournissons des solutions initiales comparables à celles dont on disposerait en milieu industriel. Notre travail montre le potentiel qu'ont les algorithmes primaux pour résoudre des problèmes de planification de personnel navigant, problèmes clés pour les compagnies aériennes, tant par leur complexité intrinsèque que par les conséquences économiques et financières qu'ils entraînent.