An algorithm for the 0-1 equality knapsack problem

Balasubramanian Ram; Sanjiv Sarin

doi:10.1057/jors.1988.175

An algorithm for the 0-1 equality knapsack problem

Balasubramanian Ram
, Sanjiv Sarin

Industrial and Systems Engineering

Industrial and systems engineering with North Carolina A&T State University

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	1045-1049
Number of pages	5
Journal	Journal of the Operational Research Society
Volume	39
Issue number	11
DOIs	https://doi.org/10.1057/jors.1988.175
State	Published - Jan 1 1988

Keywords

Integer programming
Linear optimization

Access to Document

10.1057/jors.1988.175

Cite this

@article{11da29eeb76c47b4a4eb3f789ffafdfd,

title = "An algorithm for the 0-1 equality knapsack problem",

abstract = "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. {\textcopyright} 1988 Operational Research Society Ltd.",

keywords = "Integer programming, Linear optimization",

author = "Balasubramanian Ram and Sanjiv Sarin",

year = "1988",

month = jan,

day = "1",

doi = "10.1057/jors.1988.175",

language = "English",

volume = "39",

pages = "1045--1049",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

number = "11",

}

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 -

An algorithm for the 0-1 equality knapsack problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this