| Article ID: | iaor20031598 |
| Country: | Japan |
| Volume: | 45 |
| Issue: | 3 |
| Start Page Number: | 293 |
| End Page Number: | 298 |
| Publication Date: | Sep 2002 |
| Journal: | Journal of the Operations Research Society of Japan |
| Authors: | Iida Hiroshi, Uno Takeaki |
| Keywords: | programming: integer |
This paper deals with the collapsing knapsack problem. In the literature, to solve the problem, a method incorporating a reduction from the problem to the 0–1 knapsack problem has been proposed. In this paper we show an alternative reduction which produces coefficients smaller than those by the previous. The improvement makes it possible to solve the resulting 0–1 knapsack problem faster than the previous. On our estimation in a case, the efficiency attains up to 150 times. We also show that the coefficients produced will be the smallest possible.