An exact algorithm for the two-constraint 0-1 knapsack problem
成果类型：
Article
署名作者：
Martello, S; Toth, P
署名单位：
University of Bologna
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.51.5.826.16757
发表日期：
2003
页码：
826-835
关键词：
摘要：
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.