The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076614Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1234
 Brown JR. The knapsack sharing, Operations Research, 1979; 27:341-355. 860
 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. Variante du knapsack contraint : methode exacte, 2010, ROADEF conference.
 Hifi M., MHalla H., Sadfi S. An exact algorithm for the knapsack sharing problem, 2005, vol. 32, No 5, pp. 1311-1324.
 Horowitz E., Sahni S. Computing partitions with applications to the knapsack problem, Journal of ACM, 1974;21:277-292.
 Iida H. A note on the max—min 0-1 knapsack problem, Journal of Combinatorial Optimization 1999;3:89-94.
 Kuno T., Konno H., Zemel E. A linear-time algorithm for solving continuous maximum knapsack problems, Operations Research Letters, 1991;10:23-26.
 Kouvelis P,Yu G. Robust discrete optimization and its applications, Dordrecht: Kluwer Academic Publishers; 1997.
 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 et 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.
 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.
 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.
 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.
 Yu G. On the max—min 0-1 knapsack problem with robust optimization applications, Operations Research 1973;44:407-15.