TY - JOUR
T1 - An algorithm for the 0-1 equality knapsack problem
AU - Ram, Balasubramanian
AU - Sarin, Sanjiv
PY - 1988/1/1
Y1 - 1988/1/1
N2 - The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10, 000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection. © 1988 Operational Research Society Ltd.
AB - The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10, 000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection. © 1988 Operational Research Society Ltd.
KW - Integer programming
KW - Linear optimization
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84974858046&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84974858046&origin=inward
U2 - 10.1057/jors.1988.175
DO - 10.1057/jors.1988.175
M3 - Article
SN - 0160-5682
VL - 39
SP - 1045
EP - 1049
JO - Journal of the Operational Research Society
JF - Journal of the Operational Research Society
IS - 11
ER -