Multivariable branching: A 0-1 knapsack problem case study

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 … Read more