The Knapsack Sharing Problem: A Tree Search Exact Algorithm
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079472Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1215
 Brown JR. The knapsack sharing, Operations Research, 1979; 27:341-355.
 Brown JR. Solving knapsack sharing with general tradeoff functions, Mathematical Programming, 1991; 5:55-73.
 Hifi M., Sadfi S. The knapsack sharing problem: an exact algorithm, Journal of Combinatorial Optimization, 2002;6:35-54.
 Hifi M., Sadfi S., Sbihi A. An efficient algorithm for the knapsack shar-ing problem, Computational Optimization and Applications, 2002;23:27-45.
 Hifi M., MHalla H., Sadfi S. An exact algorithm for the knapsack sharing problem, to appear in Computers and Operations Research.
 Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem, Journal of ACM, 1974;21:277-292.
 Kuno T., Konno H., Zemel E. A linear-time algorithm for solving continuous maximum knapsack problems, Operations Research Letters, 1991;10:23-26.
 Luss H. Minmax resource allocation problems: optimization and para-metric analysis, European Journal of Operational Research, 1992;60:76¬86.
 Martello S., Toth P (eds.). Knapsack problems: algorithms and computer implementation, John Wiley and Sons, 1990.
 Martello S, Toth P. Upper bounds and algorithms for hard 0-1 knapsack problems, Operations Research, 1997;45:768-778.
 Pang JS., Yu CS. A min-max resource allocation problem with substi-tutions, European Journal of Operational Research, 1989;41:218-223.
 Tang CS. A max-min allocation problem: its solutions and applications, Operations Research, 1988;36:359-367.
 Yamada T., Futakawa M. Heuristic and reduction algorithms for the knapsack sharing problem, Computers and Operations Research, 1997;24:961-967.
 Yamada T., Futakawa M., Kataoka S. Some exact algorithms for the knapsack sharing problem, European Journal of Operational Research, 1998;106:177-183.