A projection method for the integer quadratic knapsack problem

Authors

Kurt M. Bretthauer, Indiana University - Bloomington
Bala Shetty, Texas A & M University - College Station
Siddhartha Syam, Marquette UniversityFollow

Document Type

Article

Language

eng

Format of Original

6 p.

Publication Date

1996

Publisher

Palgrave Macmillan

Source Publication

Journal of the Operational Research Society

Source ISSN

0160-5682

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.

Recommended Citation

Bretthauer, Kurt M.; Shetty, Bala; and Syam, Siddhartha, "A projection method for the integer quadratic knapsack problem" (1996). Management Faculty Research and Publications. 110.
https://epublications.marquette.edu/mgmt_fac/110