×

An exact algorithm for the two-constraint 0-1 knapsack problem. (English) Zbl 1165.90575

Summary: 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.

MSC:

90C09 Boolean programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI