Article ID: | iaor19983010 |
Country: | United States |
Volume: | 7 |
Issue: | 1 |
Start Page Number: | 109 |
End Page Number: | 116 |
Publication Date: | Dec 1995 |
Journal: | INFORMS Journal On Computing |
Authors: | Shetty Bala, Bretthauer Kurt M., Syam Siddhartha S. |
Keywords: | programming: branch and bound, programming: quadratic |
We present a branch and bound algorithm for solving separable convex quadratic knapsack problems with lower and upper bounds on the integer variables. The algorithm solves a series of continuous quadratic knapsack problems via their Kuhn–Tucker conditions. We also discuss reoptimization procedures for efficiently solving the continuous subproblems. Computational results for problems with up to 300 integer variables are reported.