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!