AI Summary & Key Takeaways
AI InsightIn 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.
📌 3 Key Takeaways
Abstract
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.
Özet
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.