Machine Learning for Integer Programming: Methods, Challenges, and Prospects

Mixed Integer Programming (MIP) is one of the most widely used frameworks for modeling real-world decision-making tasks. MIP solvers, which are based on a branch-and-bound algorithm, are capable of solving large-scale problems much faster than what worst-case complexity bounds may suggest. This surprising fact has been attributed to algorithmic and engineering enhancements to MIP solvers (rather than just better hardware), accumulated over the last three decades.

Along with the increase in the complexity of MIP algorithms, there is also an increase in the amount of "data" that is generated by the repeated solution of similar instances of the same mathematical optimization problem. This creates an opportunity for leveraging Machine Learning (ML) to "optimize the optimizers".

In this talk, I will give an overview of research developments at the intersection of ML and MIP, with a focus on two recent works on (1) learning to schedule heuristics in a MIP solver [NeurIPS-21, https://openreview.net/forum?id=fEImgFxKU63] and (2) Monte Carlo Tree Search to find backdoor sets, a handful of integer variables such that the MIP instance can be solved to global optimality by branching only on those variables [https://arxiv.org/abs/2110.08423].