|
Monday February 10, 12pm-1pm, 1116-E Klaus
Learning to Branch in Mixed Integer ProgrammingElias Khalil
Advisor: Prof. Bistra Dilkina
|
 |
ABSTRACT
The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP.
Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-evaluate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance.
Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.
Joint work with Pierre Le Bodic, Le Song, George Nemhauser and Bistra Dilkina – to appear in AAAI’16.
Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-evaluate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the instance.
Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.
Joint work with Pierre Le Bodic, Le Song, George Nemhauser and Bistra Dilkina – to appear in AAAI’16.
BIO
Elias Khalil is a second-year Ph.D. student in CSE, working with Prof. Bistra Dilkina. His research interests are in discrete optimization, machine learning and networks. Elias holds an M.S. from Georgia Tech, and a B.S. from the American University of Beirut, Lebanon, both in Computer Science.