A branch and bound algorithm for solving the multiple-choice knapsack problem |
| |
Authors: | M.E. Dyer N. Kayal J. Walker |
| |
Affiliation: | Department of Mathematics and Statistics, Teesside Polytechnic, Middlesbrough, Cleveland, TS1 3BA, U.K.;Department of Economics and Statistics, National University of Singapore, Kent Ridge, Singapore 0511 |
| |
Abstract: | The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported. |
| |
Keywords: | Integer-programs branch-and-bound multiple-choice constraints knapsack problem |
本文献已被 ScienceDirect 等数据库收录! |