Machine learning-driven hybrid optimization based on decision diagrams

Les problèmes d'optimisation combinatoire se posent dans de nombreux domaines des mathématiques et de l'informatique, ainsi que dans des applications telles que l'ordonnancement et la planification. Malgré des décennies de développement des différentes technologies d'optimisation, certains problèmes combinatoires restent encore difficiles à résoudre. Le développement d'outils d'optimisation génériques pour résoudre ces problèmes difficiles est donc un domaine de recherche actif et continu. Dans cette thèse, nous proposons de nouveaux mécanismes d'optimisation hybrides qui exploitent les avantages complémentaires de différents paradigmes, à savoir, (i) l'optimisation basée sur les diagrammes de décision (ODD), (ii) la programmation en nombres entiers (PNE), et (iii) l'apprentissage automatique (AA) pour améliorer les méthodes d'optimisation. Dans une première contribution, nous explorons l'utilisation de l'AA pour discriminer la difficulté des instances uniquement en fonction de caractéristiques spécifiques du problème. Nous montrons que l'AA peut effectivement révéler des patrons cachés sur le problème qui rendent sa résolution facile ou difficile par un solveur de PNE. De plus, les fonctions apprises (classificateurs) se révèlent utiles pour fournir des informations au solveur de PNE afin d'ajuster sa configuration et d'augmenter sa performance. Deuxièmement, nous proposons une approche d'optimisation hybride en combinant l'ODD et la PNE. Nous nous appuyons sur le rôle que les diagrammes de décision (DD) de taille limitée peuvent jouer en tant qu'arbre de recherche. De plus, nous exploitons la machinerie très developpée des solveurs PNE pour concevoir de nouveaux mécanismes permettant d'explorer, de manière collaborative, l'espace de solution. En outre, l'AA est utilisé pour améliorer les performances du solveur hybride en fournissant des informations utiles lors de l'exploration. Les expériences de calcul montrent que si une structure appropriée est révélée, l'approche intégrée est supérieure aux solveurs basées soit uniquement sur les DD, soit sur la PNE. Enfin, dans une troisième contribution, une nouvelle représentation du problème basée sur les DD est proposée pour le problème quadratique du stable maximum, une version plus difficile et non linéaire du problème du stable maximum. De plus, un algorithme hybride ODD-PNE est étendu en considérant les fonctionnalités de programmation quadratique d'un solveur PNE et une intégration plus étroite de l'AA pour guider l'exploration de l'espace de solution. L'algorithme proposé est plus performant qu'un solveur basé sur la programmation semi-définie et deux solveurs PNE commerciaux majeurs.