Retour aux activités
Séminaire “Un chercheur du GERAD vous parle!”

Learning to branch in MILP solvers


11 déc. 2018   15h30 — 16h30

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.

Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!

Guy Desaulniers responsable


Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Axe de recherche