Branching on a set of variables, rather than on a single variable, can give tighter bounds at the child nodes and can result in smaller search trees. However, selecting a good set of variables to branch on is even more challenging than selecting a good single variable to branch on. Generalized strong branching extends the strong branching concepts developed for choosing a single variable to choosing a set of variables. As the computational requirements of a full implementation of strong branching are prohibitive, we use extreme gradient boosting to train a model to predict the ranking of (sets of) candidate variables. An extensive computational study using instances from three well-known classes of optimization problems demonstrates that branching on sets of variables outperforms branching on a single variable, that a learned model can be used effectively to select among (sets of) candidate variables, and that the learned strong branching strategies outperform the default branching strategy of state-of-the-art commercial solver CPLEX in terms of both the number of nodes explored in the search tree and the time it takes to explore the search tree.
Citation
Yu Yang, Natashia Boland, Bistra Dilkina, Martin Savelsbergh, "Learning Generalized Strong Branching for Set Covering, Set Packing, and 0-1 Knapsack Problems", 2020.
Article
View Learning Generalized Strong Branching for Set Covering, Set Packing, and 0-1 Knapsack Problems