Search

In this paper, we propose to solve the max-min knapsack problem with multiple scenarios by using an iterative algorithm that uses three main phases: (1) construction phase, (2) improvement phase, and (3) destroying/repairing phase. The first phase yields a (starting) pool of elite solutions for the problem by applying a greedy randomized search. The second phase tries to improve each solution at hand by using an intensification search using path-relinking combined with a look-ahead strategy. The third phase can be viewed as a diversification strategy, where the iterative algorithm tries to avoid premature convergence towards local optima. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. Its obtained results are compared to those reached by recent algorithms available in the literature. The computational part shows that the method remains competitive (in term of the quality of solutions achieved), where it is able to provide better bounds than those already published ones. © 2019, Springer-Verlag GmbH Germany, part of Springer Nature.

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., {"references":["Brown JR. The knapsack sharing, Operations Research, 1979; 27:341-355. \n860","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. [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."]}

We propose a heuristic for the constrained and the unconstrained circular cutting problem based upon simulated annealing. We define an energy function, the small values of which provide a good concentration of the circular pieces on the left bottom corner of the initial rectangle. Such values of the energy correspond to configurations where pieces are placed in the rectangle without overlapping. Appropriate software has been devised and computational results and comparisons with some other algorithms are also provided and discussed. © 2003 Elsevier B.V. All rights reserved.

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., {"references":["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.\n[10] Martello S, Toth P. Upper bounds and algorithms for hard 0-1 knapsack problems, Operations Research, 1997;45:768-778.\n[11] Pang JS., Yu CS. A min-max resource allocation problem with substi-tutions, European Journal of Operational Research, 1989;41:218-223.\n[12] Tang CS. A max-min allocation problem: its solutions and applications, Operations Research, 1988;36:359-367.\n[13] Yamada T., Futakawa M. Heuristic and reduction algorithms for the knapsack sharing problem, Computers and Operations Research, 1997;24:961-967.\n[14] Yamada T., Futakawa M., Kataoka S. Some exact algorithms for the knapsack sharing problem, European Journal of Operational Research, 1998;106:177-183."]}