×

The multiobjective multidimensional knapsack problem: a survey and a new approach. (English) Zbl 1277.90116

Summary: The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two-phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state-of-the-art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three-objective instances.

MSC:

90C27 Combinatorial optimization
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

PAES; SPEA2; MOTGA; MEMOTS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahuja, A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics 123 (1-3) pp 75– (2002) · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[2] Alsheddy , A. Tsang , E.P.K. 2009 Guided Pareto local search and its application to the 0/1 multi-objective knapsack problems Proceedings of the Eighth Metaheuristic International Conference (MIC’09) Hamburg, Germany 1 14
[3] Alsheddy , A. Tsang , E.P.K. 2010 Guided Pareto local search based frameworks for pareto optimization Proceedings of the WCCCI IEEE World Congress on Computational Intelligence Barcelona 1 8
[4] Alves, MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem, Computers & Operations Research 34 pp 3458– (2007) · Zbl 1127.90059 · doi:10.1016/j.cor.2006.02.008
[5] Angel, Metaheuristics for Multiobjective Optimisation, Vol. 535 of Lecture Notes in Economics and Mathematical Systems pp 153– (2004) · doi:10.1007/978-3-642-17144-4_6
[6] Balas, An algorithm for large zero-one knapsack problems, Operational Research 28 pp 1130– (1980) · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130
[7] Barichard , V. Hao , J.K. 2002 An empirical study of tabu search for the MOKP Proceedings of the First International Workshop on Heuristics 4 47 56
[8] Barichard, Genetic tabu search for the multi-objective knapsack problem, Journal of Tsinghua Science and Technology 8 (1) pp 8– (2003) · Zbl 1051.90021
[9] Bazgan, Solving efficiently the 0-1 multi-objective knapsack problem, Computers & Operations Research 36 (1) pp 260– (2009a) · Zbl 1175.90323 · doi:10.1016/j.cor.2007.09.009
[10] Bazgan, Implementing an efficient FPTAS for the 0-1 multi-objective knapsack problem, European Journal of Operational Research 198 (1) pp 47– (2009b) · Zbl 1163.90726 · doi:10.1016/j.ejor.2008.07.047
[11] Beausoleil, Multi-start and path relinking methods to deal with multiobjective knapsack problems, Annals of Operations Research 157 pp 105– (2008) · Zbl 1163.90019 · doi:10.1007/s10479-007-0199-8
[12] Ben Abdelaziz , F. Krichen , S. 1997 A tabu search heuristic for multiobjective knapsack problems Rutgers Center for Operations Research Piscataway, NJ
[13] Ben Abdelaziz, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization pp 205– (1999) · doi:10.1007/978-1-4615-5775-3_14
[14] Captivo, Solving bicriteria 0-1 knapsack problems using a labeling algorithm, Computers & Operations Research 30 (12) pp 1865– (2003) · Zbl 1047.90054 · doi:10.1016/S0305-0548(02)00112-0
[15] Czyzak, Pareto simulated annealing-a metaheuristic technique for multiple-objective combinatorial optimization, Journal of Multi-Criteria Decision Analysis 7 pp 34– (1998) · Zbl 0904.90146 · doi:10.1002/(SICI)1099-1360(199801)7:1<34::AID-MCDA161>3.0.CO;2-6
[16] Dantzig, Discrete variable extremum problems, Operations Research 5 pp 226– (1957) · doi:10.1287/opre.5.2.266
[17] Deb, Proceedings of First International Conference, EMO2001, Zurich, Switzerland, March 7-9, 2001, Vol. 1993 of Lecture Notes in Computer Science pp 67– (2001)
[18] Deb, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6 (2) pp 182– (2002) · Zbl 05451853 · doi:10.1109/4235.996017
[19] Delort , C. Spanjaard , O. 2010 Using bound sets in multiobjective optimization: application to the biobjective binary knapsack problem Proceedings of 9th International Symposium on Experimental Algorithms (SEA 2010), Napoli, Italy, May 20-22, 2010, Vol. 6049 of Lecture Notes in Computer Science 253 265
[20] Ehrgott, Multiple Criteria Optimization - State of the Art Annotated Bibliographic Surveys 52 pp 369– (2002) · Zbl 1024.00020 · doi:10.1007/0-306-48107-3_8
[21] Ehrgott, Bound sets for biobjective combinatorial optimization problems, Computers & Operations Research 34 pp 2674– (2007) · Zbl 1141.90509 · doi:10.1016/j.cor.2005.10.003
[22] Erlebach, Approximating multiobjective knapsack problems, Management Science 48 (12) pp 1603– (2002) · Zbl 1232.90324 · doi:10.1287/mnsc.48.12.1603.445
[23] Figuera , J.R. Wiecek , M. Tavares , G. 2006 Multiple criteria knapsack problems: network models and computational results Proceedings of the Multi-Objective Programming and Goal Programming Conference (MOPGP’06), Tours, France, June 12-14, 2006
[24] Florios, Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms, European Journal of Operational Research 203 (1) pp 14– (2010) · Zbl 1177.90341 · doi:10.1016/j.ejor.2009.06.024
[25] Gandibleux, Tabu search based procedure for solving the 0-1 multi-objective knapsack problem: the two objectives case, Journal of Heuristics 6 (3) pp 361– (2000) · Zbl 0969.90079 · doi:10.1023/A:1009682532542
[26] Gandibleux , X. Klamroth , K. 2006 Cardinality bounds for multiobjective knapsack problems based on weighted sums scalarizations Proceedings of the Multi-Objective Programming and Goal Programming Conference (MOPGP’06), Tours, France, June 12-14, 2006
[27] Gandibleux, Proceedings of First International Conference, EMO2001, Zurich, Switzerland, March 7-9, 2001, Vol. 1993 of Lecture Notes in Computer Science pp 429– (2001) · Zbl 1018.90046
[28] Glover, A multiphase dual algorithm for the zero-one integer programming problem, Operations Research 13 (6) pp 879– (1965) · Zbl 0163.41301 · doi:10.1287/opre.13.6.879
[29] Glover, Optimization by ghost image processes in neural networks, Computers & Operations Research 21 (8) pp 801– (1994) · Zbl 0812.90128 · doi:10.1016/0305-0548(94)90012-4
[30] Glover, Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research pp 1– (2000) · doi:10.1007/978-1-4615-4567-5_1
[31] Glover, Handbook of Metaheuristics (2003) · Zbl 1058.90002
[32] Glover, Tabu Search (1997) · doi:10.1007/978-1-4615-6089-0
[33] da Silva, Scatter search method for the bi-criteria multi-dimensional {0,1}-knapsack problem using surrogate relaxation, Journal of Mathematical Modelling and Algorithms 3 (3) pp 183– (2004) · Zbl 1057.90045 · doi:10.1023/B:JMMA.0000038617.09620.02
[34] da Silva, A scatter search method for bi-criteria {0-1}-knapsack problems, European Journal of Operational Research 169 pp 373– (2006) · Zbl 1079.90175 · doi:10.1016/j.ejor.2004.08.005
[35] da Silva, Core problems in bi-criteria {0,1}-knapsack problems, Computers & Operations Research 35 (1) pp 2292– (2008) · Zbl 1169.90439 · doi:10.1016/j.cor.2006.11.001
[36] da Silva, Integrating partial optimization with scatter search for solving bi-criteria {0,1}-knapsack problems, European Journal of Operational Research 177 pp 1656– (2007) · Zbl 1102.90046 · doi:10.1016/j.ejor.2005.10.013
[37] Haimes, On a bicriterion formulation of the problems of integrated system identification and system optimization, IEEE Transactions on Systems, Man, and Cybernetics 1 pp 296– (1971) · Zbl 0224.93016 · doi:10.1109/TSMC.1971.4308298
[38] Hansen, Bicriterion path problems, Lecture Notes in Economics and Mathematical Systems 177 pp 109– (1979) · Zbl 0444.90098 · doi:10.1007/978-3-642-48782-8_9
[39] Ishibuchi, A multi-objective genetic local search algorithm and its application to flow shop scheduling, IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews 28 (3) pp 392– (1998) · doi:10.1109/5326.704576
[40] Jaszkiewicz , A. 1998 Genetic local search for multiple objective combinatorial optimization Technical Report RA-014/98 Institute of Computing Science, Poznań University of Technology, Poznań Poland · Zbl 1002.90051
[41] Jaszkiewicz , A. 2000 Experiments done with the MOMHLIB http://www-idss.cs.put.poznan.pl/jaszkiewicz/momhlib/ Institute of Computing Science, Poznań University of Technology, Poznań Poland
[42] Jaszkiewicz , A. 2000 On the performance of multiple-objective genetic local search on the 0/1 knapsack problem-a comparative experiment Technical Report RA-002/2000 Institute of Computing Science, Poznań University of Technology, Poznań Poland
[43] Jaszkiewicz , A. 2001a A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm Technical Report RA-003/01 Institute of Computing Science, Poznań University of Technology, Poznań Poland · Zbl 1067.90149
[44] Jaszkiewicz, Comparison of local search-based metaheuristics on the multiple-objective knapsack problem, Foundations of Computing and Decision Sciences 26 (1) pp 99– (2001b)
[45] Jaszkiewicz, On the performance of multiple-objective genetic local search on the 0/1 knapsack problem-a comparative experiment, IEEE Transactions on Evolutionary Computation 6 (4) pp 402– (2002) · Zbl 05452025 · doi:10.1109/TEVC.2002.802873
[46] Jaszkiewicz, On the computational efficiency of multiple objective metaheuristics. The knapsack problem case study, European Journal of Operational Research 158 (2) pp 418– (2004) · Zbl 1067.90077 · doi:10.1016/j.ejor.2003.06.015
[47] Jorge , J. Gandibleux , X 2007 Nouvelles propositions pour la résolution exacte du problème de sac à dos bi-objectif unidimensionnel en variables binaires, février
[48] Kellerer, Knapsack Problems (2004) · doi:10.1007/978-3-540-24777-7
[49] Klamroth, Dynamic programming approaches to the multiple criteria knapsack problem, Naval Research Logistics 47 (1) pp 57– (2000) · Zbl 0956.90041 · doi:10.1002/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO;2-4
[50] Knowles , J. Corne , D. 1999 The Pareto archived evolution strategy: a new baseline algorithm for multiobjective optimisation Proceedings of 1999 Congress on Evolutionary Computation IEEE Service Center Washington, DC 98 105
[51] Knowles , J. Corne , D. 2000a M-PAES: A memetic algorithm for multiobjective optimization Proceedings of 2000 Congress on Evolutionary Computation, La Jolle, CA, July 6-9, 2000 1 IEEE Service Center Piscataway, NJ 325 332
[52] Knowles , J. Corne , D. 2000b A comparison of diverse approaches to memetic multiobjective combinatorial optimization Proceedings of the 2000 Genetic and Evolutionary Computation Conference Workshop Program Las Vegas, NV 103 108
[53] Kumar, Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem, Theoretical Computer Science 358 (1) pp 104– (2006) · Zbl 1097.68155 · doi:10.1016/j.tcs.2006.03.007
[54] Larranaga, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Genetic Algorithms and Evolutionary Computation) (2002)
[55] Laumanns, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research 169 (3) pp 932– (2006) · Zbl 1079.90122 · doi:10.1016/j.ejor.2004.08.029
[56] Li , H. Zhang , Q. Tsang , E. Ford , J.A. 2004 Hybrid estimation of distribution algorithm for multiobjective knapsack problem Proceedings of the Fourth European Conference on Evolutionary Computation in Combinatorial Optimization, Coimbre, Portugal, April 5-7, 2004 145 154 · Zbl 1177.90420
[57] Lin, An effective heuristic algorithm for the traveling-salesman problem, Operations Research 21 pp 498– (1973) · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[58] Lust , T. 2009 New metaheuristics for solving MOCO problems: application to the knapsack problem, the traveling salesman problem and IMRT optimization University of Mons Mons, Belgium
[59] Lust, MEMOTS: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization, RAIRO: Operations Research 42 (1) pp 3– (2008) · Zbl 1170.90479 · doi:10.1051/ro:2008003
[60] Lust, Two-phase Pareto local search for the biobjective traveling salesman problem, Journal of Heuristics 16 (3) pp 475– (2010) · Zbl 1189.90145 · doi:10.1007/s10732-009-9103-9
[61] Martello, Knapsack Problems (1990)
[62] Martins , E.Q.V. Dos Santos , J.L.E. 1999 The labeling algorithm for the multiobjective shortest path problem Departamento de Matemática, Universidade de Coimbra
[63] Mavrotas, Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core, Applied Mathematics and Computation 215 (7) pp 2502– (2009) · Zbl 1179.65072 · doi:10.1016/j.amc.2009.08.045
[64] Michalewicz, Methodologies for Intelligent Systems Conference (ISMIS) pp 134– (1994) · doi:10.1007/3-540-58495-1_14
[65] Miettinen, Nonlinear Multiobjective Optimization (1999) · Zbl 0949.90082
[66] Paquete, Metaheuristics for Multiobjective Optimisation, Vol. 535 of Lecture Notes in Economics and Mathematical Systems pp 177– (2004) · doi:10.1007/978-3-642-17144-4_7
[67] Pelikan , M. Sastry , K. Cantu-Paz , E. 2006 Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence) Springer-Verlag New York, Inc Secaucus, NJ
[68] Puchinger, EvoCOP, Vol. 3906 of Lecture Notes in Computer Science pp 195– (2006)
[69] Sato, Local dominance and local recombination in MOEAs on 0/1 multiobjective knapsack problems, European Journal of Operational Research 181 (3) pp 1708– (2007) · Zbl 1123.90069 · doi:10.1016/j.ejor.2006.08.006
[70] Serafini , P. 1992 Simulated annealing for multi-objective optimization problems Proceedings of the Tenth International Conference on Multiple Criteria Decision Making 1 87 92
[71] Steuer, Multiple Criteria Optimization: Theory, Computation and Applications (1986) · Zbl 0663.90085
[72] Talbi, Metaheuristics: From Design to Implementation (2009) · Zbl 1190.90293
[73] Teghem, Decision-making Process (Concepts and Methods) pp 199– (2009) · doi:10.1002/9780470611876.ch5
[74] Teghem, A survey of techniques for finding efficient solutions to multi-objective integer linear programming, Asia-Pacific Journal of Operational Research 3 (2) pp 95– (1986) · Zbl 0616.90045
[75] Tuyttens , D. 2006
[76] Ulungu , E.L. 1993 Optimisation Combinatoire multicritère: Détermination de l’ensemble des solutions efficaces et méthodes interactives Université de Mons-Hainaut, Faculté des Sciences Mons, Belgium
[77] Ulungu, Multiobjective combinatorial optimization problems: a survey, Journal of Multi-Criteria Decision Analysis 3 pp 83– (1994) · Zbl 0853.90098 · doi:10.1002/mcda.4020030204
[78] Ulungu, The two-phases method: an efficient procedure to solve biobjective combinatorial optimization problems, Foundation of Computing and Decision Science 20 pp 149– (1995) · Zbl 0853.90097
[79] Ulungu, Multicriteria Analysis pp 269– (1997)
[80] Ulungu, MOSA method: A tool for solving multiobjective combinatorial optimization problems, Journal of Multi-Criteria Decision Analysis 8 (4) pp 221– (1999) · Zbl 0935.90034 · doi:10.1002/(SICI)1099-1360(199907)8:4<221::AID-MCDA247>3.0.CO;2-O
[81] Vazirani, Approximation Algorithms (2001)
[82] Vianna , D.S. Arroyo , J.E.C. 2004 A GRASP algorithm for the multi-objective knapsack problem XXIV International Conference of the Chilean Computer Science Society (SCC’04), IEEE Computer Society, Arica, Chile, November 2004 69 75
[83] Visée, Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem, Journal of Global Optimization 12 pp 139– (1998) · Zbl 0908.90191 · doi:10.1023/A:1008258310679
[84] Voudouris, Guided local search and its application to the travelling salesman problem, European Journal of Operational Research 113 (2) pp 469– (1999) · Zbl 0937.90094 · doi:10.1016/S0377-2217(98)00099-X
[85] Zhang, Solving the biobjective zero-one knapsack problem by an efficient LP-based heuristic, European Journal of Operational Research 159 (3) pp 545– (2004) · Zbl 1065.90056 · doi:10.1016/S0377-2217(03)00420-X
[86] Zitzler , E. 1999 Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications Swiss Federal Institute of Technology (ETH) Zurich, Switzerland
[87] Zitzler , E. Thiele , L. 1999 Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach IEEE Transactions on Evolutionary Computation · Zbl 05452215 · doi:10.1109/4235.797969
[88] Zitzler , E. Laumanns , M. Thiele , L. 2001 SPEA2: Improving the strength Pareto evolutionary algorithm
[89] Zitzler, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2002) pp 666– (2002)
[90] Zitzler, Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation 7 (2) pp 117– (2003) · Zbl 05452216 · doi:10.1109/TEVC.2003.810758
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.