Çok amaçlı sırt çantası problemleminin çözümüne yeni bir yaklaşım: konik skalerleştirme
Sırt çantası problemi (knapsack problem-SÇP), Yöneylem Araştırması yazınında oldukça iyi bilinen kombinatorik problemlerden birisidir. Yazında birçok farklı tipi olan SÇP genellikle tek amaçlı olarak incelenmiştir. Ancak gerçek hayatta pek çok problem çok amaçlı yapıdadır. Sözgelimi kârın en büyük ve riskin en küçük olmasının istendiği yatırım probleminde olduğu gibi, birbiriyle çelişen iki ya da daha fazla amacın var olduğu durumlarda, problemi çok amaçlı olarak ele almak gerekmektedir. Çok amaçlı SÇP’nin matematiksel modelinde doğrusal amaç fonksiyonları ve doğrusal bir kısıt olmasına rağmen, 0-1 tamsayı değişkenlerin varlığı nedeniyle uygun çözüm alanı dışbükey değildir. Uygun çözüm alanının dışbükey olmadığı durumlarda Pareto etkin çözümlerin belirlenmesi ciddi bir sorun oluşturmaktadır. 2001 yılında Gasimov tarafından geliştirilen konik skalerleştirme yöntemi, dışbükeylik koşulu gerektirmemekte ve çok geniş bir problem sınıfına başarıyla uygulanabilmektedir. Bu çalışmada konik skalerleştirme yönteminin çok amaçlı sırt çantası probleminde başarıyla kullanılabileceği, klasik ağırlıklandırma yöntemiyle elde edilmesi mümkün olmayan içbükey Pareto etkin çözümlerin bu yöntemle rahatlıkla bulunabileceği, yazından alınan büyük boyutlu test problemleri üzerinde gösterilmiştir.
A new solution approach for multi objective knapsack problem: conic scalarization
Knapsack problem (KP) is one of the well-known combinatorial optimization problems in the operational research literature. Although there are many studies on the knapsack problem with different constraints and objectives in the literature, KP has been studied with single objective function, in general. However, most of the problems have multi objective structure, in real life. For instance, if there exist two or more objectives which conflict each others, like maximization of the profit and minimization of the risk in an investment problem, the 0-1 multi-objective knapsack problem occurs. Although the mathematical model of the knapsack problem has a linear constraint and a linear objective function, feasible region is not a convex set due to existing 0-1 integer variables. Determining the Pareto efficient solutions for the problems having non convex feasible region is a crucial problem. On the other hand, the conic scalarization, which was developed by Gasimov in 2001, can be applied successfully to the wide range of problem class since it does not require convexity condition. In this study, it is shown on test instances taken from the literature, that the conic scalarization approach can be successfully used for solving a large scale multi objective knapsack problem and the concave Pareto-efficient solutions which can not be found by using classical weighted method can be easily obtained by using conic scalarization approach.
___
- 1. Abboud, N.J., Sakawa, M., Inuiguchi, M. 1997. “A Fuzzy Programming Approach to Multiobjective Multidimensional 0–1 Knapsack Problems,” Fuzzy Sets and Systems, 86(1), 1-14.
- 2. Ahmed, E., Elettreby, M.F. 2006. “On Combinatorial Optimization Motivated by Biology,” Applied Mathematics and Computation, 172, 40–48.
- 3. Alanne, K. 2004. “Selection of Renovation Actions Using Multi-criteria ‘Knapsack’ Model,” Autamation in Construction, 13(3), 377-391.
- 4. Alves, M.J., Almeida, M. 2007. “MOTGA: A Multiobjective Tchebycheff Based Genetic Algorithm for the Multidimensional Knapsack Problem,” Computers & Operations Research, 34 (11), 3458-3470.
- 5. Bazgan, C., Hugot, H., Vanderpooten, D. 2009. “Solving Efficiently the 0–1 Multi-objective Knapsack Problem,” Computers & Operations Research 36, 260 – 279.
- 6. Captivo, M.E., Climaco, J., Figueira J., Martins, E., Santos, J.L. 2003. “Solving Bicriteria 0-1 Knapsack Problems Using a Labeling Algorithm,” Computers & Operations Research, 30, 1865-1886.
- 7. Chankong, V., Haimes, Y.Y. 1983. Multiobjective Decision Making: Theory and Methodology, Elsevier Science Publishing Co, New York.
- 8. Cho, K.I., Kim, S.H. 1997. “An Improved Interactive Hybrid Method for the Linear Multi-objective Knapsack Problem,” Computers & Operations Research, 24, 991-1003.
- 9. Ehrgott, M. 2005. Multicriteria Optimization, Springer- Verlag, 2nd edition.
- 10. Fleszar, K., Hindi, K.S. 2009. “Fast, Effective Heuristics for the 0-1 Multi-dimensional Knapsack Problem,” Computers & Operations Research.
- 11. Gasimov, R.N. 2001. “Characterization of the Benson Proper Efficiency and Scalarization in Nonconvex Vector Optimization,” Lecture Notes in Economics and Mathematical Systems, 507, 189-198.
- 12. Gasimov, R.N., Sipahioglu, A., Saraç, T. 2007. “A Multiobjective Programming Approach to 1.5-dimensional Assortment Problem,” European Journal of Operational Research, 179 (1) , 64-79.
- 13. Henkel, C.V., Back, T., Kok, J.N., Rozenberg, G., Spaink, H.P. 2007. “DNA Computing of Solutions to Knapsack Problems,” Biosystems, 88 (1-2), 156-162.
- 14. Jaszkiewicz, A. 2004. “On the Computational Efficiency of Multiple Objective Metaheuristics. The Knapsack Problem Case Study,” European Journal of Operational Research, 158, 2, 418-433.
- 15. Jenkins, L. 2002. “A Bicriteria Knapsack Program for Planning Remediation of Contaminated Lightstation Sites,” European Journal of Operational Research, 140, 2, 427- 433.
- 16. Kellerer, H., Pferschy, U., Pisinger, D. 2004. Knapsack Problems, Springer-Verlag, NY.
- 17. Klamroth, K, Wiecek, M. M. 2001. “A Time-dependent Multiple Criteria Single-machine Scheduling Problem,” European Journal of Operational Research, 135, 1, 17- 26.
- 18. Kumar, R., Banerjee, N. 2006. “Analysis of a Multiobjective Evolutionary Algorithm on the 0– 1 Knapsack Problem,” Theoretical Computer Science, 358, 104-120.
- 19. Laumanns, M., Thiele, L., Zitzler, E. 2006. “An Efficient, Adaptive Parameter Variation Scheme for Metaheuristics Based on the Epsilon-constraint Method,” European Journal of Operational Research 169, 932–942.
- 20. Luc, D.T. 1989. “Theory of Vector Optimization,” Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin.
- 21. Martello, S., Toth, P. 1990. Knapsack Problems: Algorithms and Computer Implementations, Wiley, Chichester, UK.
- 22. Özdemir, M.S., Gasimov, R.N. 2004. “The Analytic Hierarch Process and Multiobjective 0-1 Faculty Course Assignment,” European Journal of Operational Research, 157, 2, 398-408.
- 23. Sakawa, M., Kato, K. 2003. “Genetic Algorithms With Double Strings for 0–1 Programming Problems,” European Journal of Operational Research, 144, 3, 581-597.
- 24. Shih, H.S. 2005. “Fuzzy Approach to Multilevel Knapsack Problems,” Computers & Mathematics with Applications”, 49(7-8), 1157-1176.
- 25. Silva, C.G., Climaco, J., Figueira, J. 2006. “A Scatter Search Method for bi-criteria {0,1}-knapsack Problems,” European Journal of Operational Research, 169, 373– 391.
- 26. Silva, C.G., Figueira, J., Climaco, J. 2007. “Integrating Partial Optimization With Scatter Search for Solving Bicriteria {0,1}-knapsack Problems,” European Journal of Operational Research, 177 (3), 1656-1677.
- 27. Teghem, J., Tuyttens, D., Ulungu, E.L. 2000. “An Interactive Heuristic Method for Multi-objective Combinatorial Optimization,” Computers & Operations Research, 27 (7-8), 621-634.
- 28. Test problemleri, 2010. http://www.tik.ee.ethz.ch/sop/ download/supplementary/testProblemSuite/. Son erişim tarihi 8 Haziran 2010.
- 29. Zhang, C.W., Ong, H.L. 2004. “Solving the Biobjective zero–one Knapsack Problem by an Efficient LP-based Heuristic,” European Journal of Operational Research, 159, 3, 545-557.
- ISSN: 1300-3410
- Yayın Aralığı: Yılda 3 Sayı
- Başlangıç: 1989
- Yayıncı: TMMOB MAKİNA MÜHENDİSLERİ ODASI