We explore the benefits of multi-variable branching strategies for linear programming based branch and bound algorithms for the 0-1 knapsack problem, i.e., of branching on sets of variables rather than on a single variable (the current default in integer programming solvers). We present examples where multi-variable branching shows advantage over single-variable branching, and partially characterize situations in which this happens. We show that for the class of 0-1 knapsack instances introduced by \citet{chvatal1980hard} to demonstrate that linear programming branch and bound algorithms (employing a single-variable branching scheme) must explore exponentially many nodes, a linear programming branch and bound algorithm employing a multi-variable branching scheme can solve any instance in either three or seven nodes. Finally, we investigate the performance of various multi-variable branching strategies computationally, and demonstrate their potential.
Citation
Yu Yang, Natashia Boland, Martin Savelsbergh, "Multi-Variable Branching: A Case Study with 0-1 Knapsack Problems", 2019.
Article
View Multivariable branching: A 0-1 knapsack problem case study