This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Martello, S. Articles by Toth, P. Search for Related Content

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

DEIS, University of Bologna, Bologna, Italy
DEIS, University of Bologna, Bologna, Italy
smartello{at}deis.unibo.it
ptoth{at}deis.unibo.it

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.

Subject classifications: Programming, integer: algorithms, branch-and-bound; Relaxation: two-constraint 0–1 knapsack problem.
History: Received September 2001; revision received November 2002; accepted November 2002.