zbMATH — the first resource for mathematics

Extending Dantzig’s bound to the bounded multiple-class binary knapsack problem. (English) Zbl 1023.90054
Summary: The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of G. B. Dantzig [Oper. Res. 5, 266–277 (1957)] and E. Balas and E. Zemel [Oper. Res. 28, 1130–1154 (1980; Zbl 0449.90064)] for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form.

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C10 Integer programming
PDF BibTeX Cite
Full Text: DOI