Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems

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.(c) 2021 Elsevier B.V. All rights reserved.

Automated summary

This article investigates the impact of branching on a set of variables on search tree size and bounds. It introduces the concept of generalized strong branching and trains a model using extreme gradient boosting to predict the ranking of candidate variable sets. Experimental results demonstrate that branching on sets of variables outperforms branching on a single variable in terms of the number of nodes explored in the search tree and the time required for exploration.