“Meet a GERAD researcher!” seminar

Title: Learning to branch in MILP solvers

Speaker: Maxime Gasse – Polytechnique Montréal, Canada

In this talk I will present the 'learning to branch' research project I am working on, along with some preliminary experimental results. A popular approach for solving mixed integer linear programs (MILPs) is the branch-and-bound (B&B) method, where the solution space is iteratively split in two according to a heuristic branching strategy, until it can be proved either that an optimal solution has been found, or that no solution exists. While powerful branching strategies have been devised over the years to make the solving process faster, we believe there is room for improvement and intend to learn better strategies from data by using machine learning. I will present: i) a formulation of the branching decision problem as a 1-player game; ii) a supervised learning experiment where we try to imitate the strong branching strategy on setcover instances using a graph convolutional network (GCN); iii) a reinforcement learning experiment that intend to improve upon the strategy learned by supervised learning.

---

Coffee and biscuits will be offered at the beginning of the seminar.
Welcome to everyone!