An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem

Silvano Martello () and Paolo Toth ()
Additional contact information
Silvano Martello: DEIS, University of Bologna, Bologna, Italy
Paolo Toth: DEIS, University of Bologna, Bologna, Italy

Operations Research, 2003, vol. 51, issue 5, 826-835

Abstract: We consider a knapsack problem in which each item has two types of weight and the container has two types of capacity. We discuss the surrogate, Lagrangian, and continuous relaxations, and give an effective method to determine the optimal Lagrangian and surrogate multipliers associated with the continuous relaxation of the problem. These results are used to obtain an exact branch-and-bound algorithm, which also includes heuristic procedures and a reduction technique. The performance of bounds and algorithms is evaluated through extensive computational experiments.

Keywords: Programming; integer: algorithms; branch-and-bound; Relaxation: two-constraint 0--1 knapsack problem (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.5.826.16757 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:51:y:2003:i:5:p:826-835

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().