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.
| 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 | |
| State | Published - Nov 1988 |
| Externally published | Yes |
Keywords
- Integer programming
- Linear optimization