The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm

Authors: Mhand Hifi, Hedi Mhalla, Mustapha Michaphy

Abstract:

In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.

Keywords: combinatorial optimization, max-min optimization, knapsack, heuristics, problem reduction

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

References:

[1] Brown JR. The knapsack sharing, Operations Research, 1979; 27:341-355. 860
[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. Variante du knapsack contraint : methode exacte, 2010, ROADEF conference.
[6] Hifi M., MHalla H., Sadfi S. An exact algorithm for the knapsack sharing problem, 2005, vol. 32, No 5, pp. 1311-1324.
[7] Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem, Journal of ACM, 1974;21:277-292.
[8] Iida H. A note on the max—min 0-1 knapsack problem, Journal of Combinatorial Optimization 1999;3:89-94.
[9] Kuno T., Konno H., Zemel E. A linear-time algorithm for solving continuous maximum knapsack problems, Operations Research Letters, 1991;10:23-26.
[10] Kouvelis P,Yu G. Robust discrete optimization and its applications, Dordrecht: Kluwer Academic Publishers; 1997.
[11] Luss H. Minmax resource allocation problems: optimization and para-metric analysis, European Journal of Operational Research, 1992;60:76-86.
[12] Martello S., Toth P (eds.). Knapsack problems: algorithms and computer implementation, John Wiley and Sons, 1990.
[13] Martello S, Toth P. Upper bounds et algorithms for hard 0-1 knapsack problems, Operations Research, 1997;45:768-778.
[14] Pang JS., Yu CS. A min-max resource allocation problem with substi-tutions, European Journal of Operational Research, 1989;41:218-223.
[15] Tang CS. A max-min allocation problem: its solutions and applications, Operations Research, 1988;36:359-367.
[16] Taniguchi, F., Yamada, T., Kataoka, S., Heuristic and exact algorithms for the maxmin optimization of the multi-scenario knapsack problem, Computers and Operations Research, 2008; 35: 2034-2048.
[17] Yamada T., Futakawa M. Heuristic and reduction algorithms for the knapsack sharing problem, Computers and Operations Research, 1997;24:961-967.
[18] Yamada T., Futakawa M., Kataoka S. Some exact algorithms for the knapsack sharing problem, European Journal of Operational Research, 1998;106:177-183.
[19] T. Yamada. Max-Min Optimization of the multiple knapsack problem: An implicit enumeration approch, E. Kozan, A. Ohuchi eds., "Operations Research/Management Science at Work: Applying Theory in the Asia Pacific Region", Kluwer Academic Publishers, pp. 351-362, 2002.
[20] Yu G. On the max—min 0-1 knapsack problem with robust optimization applications, Operations Research 1973;44:407-15.