A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems

Kurt M. Bretthauer, Bala Shetty, Siddhartha Syam

ORSA Journal on Computing · 1995 · Volume 7 · Issue 1

Abstract

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. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Keywords

programming, integer, quadratic knapsack problems

Enable JavaScript for citation tools and additional paper interactions.