Machine learning algorithms in Mixed-Integer Programming

De nombreux problèmes de la vie courante comportent des décisions discrètes, et peuvent être modélisés sous la forme de programmes d'optimisation en nombres entiers. De tels modèles peuvent désormais être résolus efficacement à l'aide de solveurs matures comportant un vaste arsenal algorithmique, ce qui explique l'utilisation quotidienne de la programmation mathématique mixte en nombres entiers (PNE) dans de multiples secteurs. Alors que les techniques d'apprentissage automatiques (à partir d'exemples) sont de plus en plus mises en œuvre pour l'analyse de données et la predicion, une attention nouvelle est donnée à l'apprentissage dans le contexte d'algorithmes d'optimisation, notamment dans les choix algorithmiques des solveurs de PNE. Cette thèse s'inscrit dans ce courant de recherche : nous analysons et proposons de nouvelles méthodes pour intégrer des techniques d'apprentissage automatique au sein d'algorithmes d'optimisation, et explorons le potentiel de cette interaction. Premièrement, nous passons en revue l'état de l'art quant à l'utilisation de techniques d'apprentissage automatique pour la sélection de variables et de nœuds dans un arbre de branchement. Plusieurs travaux de PNE sont identifiés comme précurseurs d'approches basées sur l'apprentissage automatique. En discutant les hypothèses et questions sousjacentes de ces décisions, nous proposons un nouveau cadre pour analyser les approches récentes d'apprentissage, et soulignons des nouvelles perspectives quant à l'utilisation de l'apprentissage pour guider le branchement. Deuxièmement, nous développons un modèle de classification pour identifier si un programme d'optimisation quadratique convexe avec variables mixtes doit être linéarisé ou non. En particulier, cette approche vise à exploiter, au sein du processus d'apprentissage, la connaissance de l'algorithme d'optimisation. Comme le montre l'implémentation au sein du solveur IBM-CPLEX, ces travaux décrivent plus largement une méthodologie pour combiner des technologies d'apprentissage et de PNE. Troisièmement, nous employons une approche basée sur la classification des séries temporelles pour prédire, après avoir utilisé une fraction du temps de calcul alloué, si un problème de PNE sera résolu ou non dans le temps imparti par l'utilisateur. Plus généralement, ces expériences sont un point de départ pour explorer comment des algorithmes d'apprentissage automatique peuvent utiliser l'information du processus de branchement pour en identifier les tendances, et éventuellement influencer la résolution. Enfin, nous présentons un nouveau cadre d'apprentissage par imitation pour le problème de sélection de variable dans un arbre de branchement. Afin d'obtenir des stratégies de branchement pouvant être généralisées à des instances de PNE génériques, nous introduisons un nouveau modèle d'aprentissage qui prend en compte l'évolution de l'arbre de branchement et le rôle des variables candidates. En plus d'atteindre les performances recherchées, cette approche offre de nouvelles bases pour de futures recherches sur les algorithmes de branchement.

Abstract

A variety of real-world tasks involve decisions of discrete nature, and can be mathematically modeled as Mixed-Integer Programming (MIP) optimization problems. Daily deployed in multiple application domains, MIP formulations are nowadays solved effectively and reliably, thanks to the complex and rich algorithmic frameworks developed in modern MIP solvers. With machine learning (ML) being extensively leveraged to “learn from examples”, new attention has been given to the application of learned predictions in optimization settings, especially in the context of MIP solvers' algorithmic design. The present thesis contributes to this thread of research: we discuss and propose novel methods on the theme of using ML algorithms alongside MIP ones, and explore some opportunities of this fruitful interaction. First, to document ML attempts addressing the decisions of variable and node selection in Branch and Bound (B&B), we present a survey on learning and branching. By interpreting previous MIP literature contributions as forerunners of ML-based works, and discussing the assumptions and concerns underlying these critical heuristic decisions, we provide an original canvas to analyze recent learned approaches and outline new points of view. Second, we develop a classification framework to tackle the algorithmic question of whether to linearize convex quadratic MIPs, aiming at a tight integration of the optimization knowledge in the learning pipeline. As experiments practically led to the deployment of a classifier in the IBM-CPLEX optimization solver, the work more generally outlines a reference methodology for the combination of ML and MIP technologies. Third, we employ a feature-based sequence classification approach to predict, after only a fraction of the available computing time has passed, whether a MIP will be solved before time-limiting. From a broader perspective, the experiments represent a starting point for exploring how statistical learning algorithms could utilize data from B&B to identify trends in MIP optimization, and possibly influence the resolution process. Finally, we contribute a novel imitation learning framework for variable selection. With the goal of learning branching policies that generalize across generic MIP instances, we introduce a new architectural paradigm that places at its center the evolution of B&B search trees and the role of candidate variables within it. On top of establishing the sought generalization capabilities, the approach offers fresh and promising ideas for future research on branching.