Date/Time
Date(s) - February 19, 2020
11:45 am - 12:35 pm
Location
406 Weil Hall
Categories
Yu Yang
Georgia Institute of Technology
Abstract: Learning Generalized Strong Branching for Set Covering, Set Packing, and 0-1 Knapsack Problems
Set branching, a natural generalization of standard branching, branches on a set of variables, which potentially gives tighter local bounds and consequently yields a smaller search tree. However, selecting a good set to branch on is more complicated than choosing a good single branching variable. Generalized strong branching on sets up to size k (GSB-k) considers sets of size no larger than k and chooses the branching set in a strong branching fashion. It’s prohibitively time-consuming due to the overhead incurred in solving a large number of linear programming (LP) relaxations. We apply machine learning techniques to learn GSB-2 and demonstrate that the learned branching scheme LRN-GSB significantly outperforms the default branching scheme (CPLEX-D) employed in the state-of-the-art commercial solver CPLEX on set covering, set packing, and 0-1 knapsack problems. Moreover, LRN-GSB is able to consistently beat CPLEX-D on large (hard) instances if trained only on small (easy) instances.