Lower bound on size of branch-and-bound trees for solving lot-sizing problem

Santanu S. Dey (santanu.deyisye.gatech.edu)
Prachi Shah (prachi.shahgatech.edu)

Abstract: We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions.

Keywords: exponential lower bound, lot-sizing, branch-and-bound

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming

Category 3: Integer Programming (Other )

Citation:

Download: [PDF]

Entry Submitted: 12/07/2021
Entry Accepted: 12/07/2021
Entry Last Modified: 12/07/2021

Modify/Update this entry