406 Weil Hall
1949 Stadium Road
Gainesville, FL 32611
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.