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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:60122", author = "Mhand Hifi and Hedi Mhalla and Mustapha Michaphy", title = "The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm", 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", volume = "4", number = "11", pages = "1729-4", }
