A Projection Method for the Integer Quadratic Knapsack Problem Export

@article{citeulike:4235436, 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.}, author = {Bretthauer, Kurt M. and Shetty, Bala and Syam, Siddhartha}, citeulike-article-id = {4235436}, citeulike-linkout-0 = {http://dx.doi.org/10.2307/3010587}, citeulike-linkout-1 = {http://www.jstor.org/stable/3010587}, doi = {10.2307/3010587}, issn = {01605682}, journal = {The Journal of the Operational Research Society}, keywords = {article, knapsack, masters, quadratic}, number = {3}, pages = {457--462}, posted-at = {2009-03-29 18:59:27}, priority = {2}, publisher = {Palgrave Macmillan Journals on behalf of the Operational Research Society}, title = {A Projection Method for the Integer Quadratic Knapsack Problem}, url = {http://dx.doi.org/10.2307/3010587}, volume = {47}, year = {1996} }

TY - JOUR ID - citeulike:4235436 L3 - citeulike-article-id:4235436 N2 - 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. IS - 3 JF - The Journal of the Operational Research Society SN - 01605682 EP - 462 TI - A Projection Method for the Integer Quadratic Knapsack Problem PB - Palgrave Macmillan Journals on behalf of the Operational Research Society VL - 47 SP - 457 KW - article KW - knapsack KW - masters KW - quadratic AU - Bretthauer, Kurt AU - Shetty, Bala AU - Syam, Siddhartha PY - 1996/// UR - http://dx.doi.org/10.2307/3010587 ER -