Title: An exact algorithm for the Knapsack Problem with Setup

Authors: Yanchun Yang, Robert L. Bulfin

Addresses: Department of Industrial and System Engineering, Auburn University, 3301 Shelby Center, Auburn, AL 36832, USA. ' Department of Industrial and System Engineering, Auburn University, 3301 Shelby Center, Auburn, AL 36832, USA

Abstract: In this paper we studies a 0-1 Knapsack Problem with Setup (KPS). One set of 0-1 variables represent a family setup and serve as an Upper Bound (UB) on another set of 0-1 variables representing production of a job in a family. We present a branch-and-bound algorithm to find an optimal solution to KPS. The algorithm uses a two-stage branching strategy and chooses the next candidate problem to explore in a non-traditional way. We verify the efficacy of the algorithm through computational testing. This is the first time that an exact algorithm given to KPS with 10,000 integer variables. Computational experiments show that this algorithm is especially effective when objective and constraint coefficients are uncorrelated.

Keywords: knapsack problem; setup; branch-and-bound; upper bound.

DOI: 10.1504/IJOR.2009.025197

International Journal of Operational Research, 2009 Vol.5 No.3, pp.280 - 291

Published online: 16 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article