02/02/2021

Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies

Giulia Zarpellon, Jason Jo, Andrea Lodi, Yoshua Bengio

Keywords:

Abstract Paper Similar Papers

Abstract: Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems. We aim instead at learning a policy that generalizes across heterogeneous MILPs: our main hypothesis is that parameterizing the state of the B&B search tree can aid this type of generalization. We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching. Experiments on MILP benchmark instances clearly show the advantages of incorporating an explicit parameterization of the state of the search tree to modulate the branching decisions, in terms of both higher accuracy and smaller B&B trees. The resulting policies significantly outperform the current state-of-the-art method for "learning to branch" by effectively allowing generalization to generic unseen instances.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949204
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 13:36 
 2
 1
 0
 0
 13:27 
 0
 0
 0
 0
 15:09 
 0
 0
 0
 0
 8:27 
 0
 0
 0
 0
 17:40 
 0
 0
 0
 0
 11:03 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 7:26 
 0
 0
 0
 0
 6:41 
 0
 0
 0
 0
 13:51 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 5:06 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 3:06 
 0
 0
 0
 0
 13:43 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 5:22 
 0
 0
 0
 0
 4:57 
 0
 0
 0
 0
 4:55 
 0
 0
 0
 0
 9:06 
 0
 0
 0
 0
 4:47 
 0
 0
 0
 0
 5:05 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 14:53 
 0
 0
 0
 0
 12:01 
 0
 0
 0
 0
 4:50 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 11:36 
 0
 0
 0
 0
 5:18 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 12:20 
 0
 0
 0
 0
 11:50 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 16:13 
 0
 0
 0
 0
 14:38 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 16:00 
 0
 0
 0
 0
 14:13 
 0
 0
 0
 0
 2:57