Optimization Online


Multivariable branching: A 0-1 knapsack problem case study

Yu Yang (yangyu***at***gatech.edu)
Natashia Boland (natashia.boland***at***gmail.com)
Martin Savelsbergh (martin.savelsbergh***at***isye.gatech.edu)

Abstract: 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.

Keywords: Multi-variable branching, 0-1 knapsack problems

Category 1: Applications -- OR and Management Sciences

Citation: Yu Yang, Natashia Boland, Martin Savelsbergh, "Multi-Variable Branching: A Case Study with 0-1 Knapsack Problems", 2019.

Download: [PDF]

Entry Submitted: 10/13/2019
Entry Accepted: 10/14/2019
Entry Last Modified: 07/30/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society