The Knapsack Sharing Problem: A Tree Search Exact Algorithm

Authors: Mhand Hifi, Hedi Mhalla

Abstract:

In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.

Keywords: Branch and bound, combinatorial optimization, knap¬sack, knapsack sharing, heuristics, interval reduction.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079472

References:

[1] Brown JR. The knapsack sharing, Operations Research, 1979; 27:341-355.
[2] Brown JR. Solving knapsack sharing with general tradeoff functions, Mathematical Programming, 1991; 5:55-73.
[3] Hifi M., Sadfi S. The knapsack sharing problem: an exact algorithm, Journal of Combinatorial Optimization, 2002;6:35-54.
[4] Hifi M., Sadfi S., Sbihi A. An efficient algorithm for the knapsack shar-ing problem, Computational Optimization and Applications, 2002;23:27-45.
[5] Hifi M., MHalla H., Sadfi S. An exact algorithm for the knapsack sharing problem, to appear in Computers and Operations Research.
[6] Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem, Journal of ACM, 1974;21:277-292.
[7] Kuno T., Konno H., Zemel E. A linear-time algorithm for solving continuous maximum knapsack problems, Operations Research Letters, 1991;10:23-26.
[8] Luss H. Minmax resource allocation problems: optimization and para-metric analysis, European Journal of Operational Research, 1992;60:76¬86.
[9] Martello S., Toth P (eds.). Knapsack problems: algorithms and computer implementation, John Wiley and Sons, 1990.
[10] Martello S, Toth P. Upper bounds and algorithms for hard 0-1 knapsack problems, Operations Research, 1997;45:768-778.
[11] Pang JS., Yu CS. A min-max resource allocation problem with substi-tutions, European Journal of Operational Research, 1989;41:218-223.
[12] Tang CS. A max-min allocation problem: its solutions and applications, Operations Research, 1988;36:359-367.
[13] Yamada T., Futakawa M. Heuristic and reduction algorithms for the knapsack sharing problem, Computers and Operations Research, 1997;24:961-967.
[14] Yamada T., Futakawa M., Kataoka S. Some exact algorithms for the knapsack sharing problem, European Journal of Operational Research, 1998;106:177-183.