Title

A projection method for the integer quadratic knapsack problem

Document Type

Article

Publication Date

1996

Source Publication

Journal of the Operational Research Society

Abstract

In this paper we present a new branch and bound algorithm for solving a class of integer quadratic knapsack problems. A previously published algorithm solves the continuous variable subproblems in the branch and bound tree by performing a binary search over the breakpoints of a piecewise linear equation resulting from the Kuhn-Tucker conditions. Here, we first present modifications to a projection method for solving the continuous subproblems. Then we implement the modified projection method in a branch and bound framework and report computational results indicating that the new branch and bound algorithm is superior to the earlier method.

Comments

Journal of the Operational Research Society, Volume 47, No.3, pp 457–462 (1996). DOI: 10.1057/jors.1996.44