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.

Abstract

The discrete and finite nature of combinatorial optimization problems arises in many areas of mathematics and computer science as well as in applications such as scheduling and planning.Despite decades of development and remarkable speedups in general-purpose solvers, some combinatorial problems are still difficult to be solved. The design of generic optimization solvers to tackle such challenging problems is a continuous and active research area. In this dissertation, we propose novel hybrid optimization mechanisms that exploit complementary strengths from different paradigms. The integrated mechanisms leverage (i) the decision diagram-based optimization (DDO) solving approach, (ii) a more mature technology such as mixed-integer programming (MIP), and, finally, (iii) the use of machine learning (ML) to enhance optimization methods. In a first contribution, we explore the use of ML for combinatorial optimization. We employ a learning framework to discriminate instance hardness as a function of problem-specific features. We show that ML can effectively reveal hidden patterns that make the problem either easy or difficult to be solved through a MIP solver. Moreover, the trained classifiers prove useful to adjust the MIP solver configuration and boost the performance. Second, we propose a hybrid optimization approach combining DDO and MIP. We rely on the role that limited-size DDs play as a search tree. We then exploit the mature machinery of MIP solvers and design novel mechanisms to explore, in a collaborative way, the solution space. In addition, ML is employed to enhance the hybrid solver performance by providing useful information during search. Computational experiments show that if suitable structure is revealed, the integrated approach outperforms both stand-alone DD and MIP solvers. Finally, in a third contribution, a novel problem representation based on DDs is proposed for the quadratic stable set problem, a more difficult and nonlinear version of the maximum independent set problem. Furthermore, a hybrid DD-MIP algorithm is extended by considering the quadratic programming capabilities of a MIP solver and a more tightly integration of ML to guide the exploration of the solution space. The proposed algorithm provides state-of-theart results when compared with a semidefinite programming-based solver and two leading commercial MIP solvers.