A projection method for the integer quadratic knapsack problem Academic Article

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. 1996 Operational Research Society Ltd. All rights reserved.

authors

• Shetty, Bala

published proceedings

• JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

author list (cited authors)

• Bretthauer, K. M., Shetty, B., & Syam, S.

citation count

• 16

complete list of authors

• Bretthauer, KM||Shetty, B||Syam, S

publication date

• March 1996

publisher

• Taylor & Francis  Publisher

keywords

• Integer Programming
• Quadratic Knapsack Problem

Digital Object Identifier (DOI)

• 10.1057/jors.1996.44

start page

• 457

end page

• 462

volume

• 47

issue

• 3

URL

• http://dx.doi.org/10.1057/jors.1996.44