Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar

Proje Grubu: TÜBİTAK MAG Proje Sayfa Sayısı: 0 Proje No: 215M844 Proje Bitiş Tarihi: 15.10.2018 Metin Dili: Türkçe

Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar

Öz:
Günümüzde karmaşık sistemlerde, karar vericiler çoğu zaman birbiri ile çelişen çok amaçlı optimizasyon problemleri ile karşı karşıyadır. Bu problemlerde, genellikle tek bir anlamlı çözüm yoktur. Baskın çözümleri, yani en az bir amaç fonksiyonundan ödün vermeden herhangi bir amaç fonksiyonunda iyileştirme yapılması mümkün olmayan çözümleri bulmak önemlidir. Ancak, baskın çözüm sayısının problem büyüklüğü arttıkça üssel büyümesi nedeniyle; gerçek hayat problemlerinde tüm baskın çözümleri bulmak zor olduğu gibi karar verici açısından da her zaman pratik bir yaklaşım değildir. Bu projede, Çok Amaçlı Tamsayı Problemleri (ÇATP) için farklı yaklaşımlar geliştirilmiş ve web tabanlı bir karar destek sistemi tasarlanmıştır. Bu kapsamda, ilk olarak tüm baskın çözümleri etkin bir şekilde bulan bir algoritma tasarlanmıştır. Daha sonra, yoğunluk analizinde kullanılacak bir ölçü tanımlanmış ve bu yoğunluk ölçüsü kullanılarak ÇATP'ler için ortak dağılım özellikleri elde edilmiştir. Bu özelliklerden faydanılarak, verilen herhangi bir ÇATP için baskın çözümlerin amaç fonksiyonları uzayında olası yerlerini ve dağılımını tahmin eden bir yöntem geliştirilmiştir. Bu bulgular kullanılarak, baskın nokta kümesini iyi temsil eden çözümler üreten algoritmalar geliştirilmiştir. Mevcut algoritmalardan farklı olarak, bu algoritmalar hem baskın nokta kümesinin dağılım özelliklerini hem de karar vericinin tercihlerini yansıtacak altkümeler üretecek şekilde tasarlanmıştır. Farklı ÇATP'ler üzerinde deneyler yapılarak; temsili baskın nokta kümesi üretmek için geliştirilen algoritmaların performansı değerlendirilmiş ve sonuçlarla algoritmaların iyi çalıştığı gösterilmiştir. Proje kapsamında, internet tabanlı ve tüm araştırmacıların erişimine açık araçlar geliştirilmiştir. Bu kapsamda geliştirilen yazılım, karar vericinin belirttiği kalite ölçüleri doğrultusunda çözüm kümeleri üretebilmektedir. Ayrıca karar vericiye çözümlerin sunulmasında kullanılabilecek görselleştirme araçları web-tabanlı uygulama ile beraber tasarlanmış ve farklı ÇATP problemleri için oluşturulan test örneklerinin yayımlanacağı dijital bir test kütüphanesi de oluşturulmuştur.
Anahtar Kelime: görselleştirme aracı etkileşimli algoritma temsili küme baskın nokta çok amaçlı tamsayı problemi

Konular: Mühendislik, Elektrik ve Elektronik Bilgisayar Bilimleri, Yazılım Mühendisliği Bilgisayar Bilimleri, Bilgi Sistemleri Bilgisayar Bilimleri, Donanım ve Mimari
Erişim Türü: Erişime Açık
  • Boland, N., Charkhgard, H., Savelsbergh, M. 2016. "The l-shape search method for triobjective integer programming", Mathematical Programming Computation, 8 (2), 217-251.
  • 1- ÇOK AMAÇLI TAMSAYI PROGRAMLAMA PROBLEMLERİ İÇİN TEMSİLİ ÇÖZÜM ÜRETEN YAKLAŞIMLARIN VE KALİTE ÖLÇÜLERİNİN İNCELENMESİ (Makale - Diğer Hakemli Makale),
  • Boland, N., Charkhgard, H., Savelsbergh, M. 2017. "A new method for optimizing a linear func- tion over the efficient set of a multiobjective integer program", European Journal of Operational Research, 260(3), 904-919.
  • 2- A web-based solution platform for Multi-objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Ceyhan, G., Köksalan, M., Lokman, B. 2019. "Finding a representative nondominated set for multi-objective mixed integer programs", European Journal of Operational Research, 272 (1), 61-77.
  • 3- A Web Application For Solving Multi-objective Integer Programming Problems (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Dächert, K., Klamroth, K. 2015. "A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems", Journal of Global Optimization, 61 (4), 643-676.
  • 4- Representing the Nondominated Set for Multi-objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Dächert, K., Klamroth, K., Lacour, R., Vanderpooten, D. 2017. "Efficient computation of the search region in multi-objective optimization", European Journal of Operational Research, 260 (3), 841-855.
  • 5- Issues in Selecting a Representative Set for Multi-Objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Dhaenens, C., Lemesre, J., Talbi, E. G. 2010. "K-ppm: A new exact method to solve multi- objective combinatorial optimization problems", European Journal of Operational Research, 200 (1), 45-53.
  • 6- ISSUES IN SELECTING A REPRESENTATIVE SET FOR MULTI-OBJECTIVE INTEGER PROGRAMS (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),
  • Doğan, I. 2018. "Representing the Nondominated Set with a Small Subset in Multi-objective Mixed Integer Programs", Yüksek Lisans Tezi, Fen Bilimleri Enstitüsü, Orta Doğu Teknik Üniver- sitesi.
  • 7- ISSUES IN SELECTING A REPRESENTATIVE SET FOR MULTI-OBJECTIVE INTEGER PROGRAMS (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),
  • Duda, R. O., Hart, P. E., Stork, D. G. 1973. Pattern classification. New York: Wiley.
  • 8- Representing the nondominated set with a small subset in multi-objective mixed integer programs (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),
  • Ehrgott, M, Gandibleux, X. 2000. "A survey and annotated bibliography of multiobjective combi- natorial optimization", OR Spektrum, 22, 425-460.
  • Faulkenberg, S. L., Wiecek, M. M. 2010. "On the quality of discrete representations in multiple objective programming", Optimization and Engineering, 11 (3), 423-440.
  • Gettinger, J., Kiesling, E., Stummer, C., ve Vetschera, R. 2013. “A comparison of representations for discrete multi-criteria decision problems”, Decision support systems, 54 (2), 976-985.
  • Haimes, Y. 1971. "On a bicriterion formulation of the problems of integrated system identification and system optimization", IEEE transactions on systems, man, and cybernetics, 1 (3), 296-297.
  • Jorge, J. M. 2009. "An algorithm for optimizing a linear function over an integer efficient set", European Journal of Operational Research, 195 (1), 98-103.
  • Kirlik, G. Sayın, S. 2014. "A new algorithm for generating all nondominated solutions of multi- objective discrete optimization problems", European Journal of Operational Research, 232 (3), 479-488.
  • Kirlik, G. Sayın, S. 2015. "Computing the nadir point for multiobjective discrete optimization problems", Journal of Global Optimization, 62 (1), 79-99.
  • Klamroth, K., Lacour, R., Vanderpooten, D., 2015. "On the representation of the search region in multi-objective optimization", European Journal of Operational Research, 245 (3), 767-778.
  • Korhonen, P., Wallenius, J. 2008. "Visualization in the multiple objective decision-making frame- work". Multiobjective optimization. Editör: Branke, J., Deb, K., Miettinen, K. ve Slowinski, R. Berlin: Springer.
  • Köksalan, M., Lokman, B. 2009. "Approximating the nondominated frontiers of multi-objective combinatorial optimization problems", Naval Research Logistics, 56 (2), 191-198.
  • Köksalan, M., Lokman, B. 2015. "Finding nadir points in multi-objective integer programs", Jour- nal of Global Optimization, 62 (1), 55-77.
  • Köksalan, M. M. 1999. "A heuristic approach to bicriteria scheduling", Naval Research Logistics, 46 (7), 777-789.
  • 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 (3), 932-942.
  • Lokman, B. 2017. "Çok amaçli tamsayi programlama problemleri için temsili çözüm üreten yak- lasimlarin ve kalite ölçülerinin incelenmesi", Endüstri Mühendisligi Dergisi, 28 (1), 19-39.
  • Lokman, B., Köksalan, M. 2013. "Finding all nondominated points ofmulti-objective integer pro- grams", Journal of Global Optimization, 57 (2), 347-365.
  • Lokman, B., Köksalan, M. 2014. "Finding highly preferred points for multi-objective integer pro- grams", IIE Transactions, 46 (11), 1181–1195.
  • Lokman, B., Köksalan, M., Korhonen, P. J., Wallenius, J. 2016. "An interactive algorithm to find the most preferred solution of multi-objective integer programs", Annals of Operations Research, 245 (1-2), 67–95.
  • Lokman, B., Köksalan, M., Korhonen, P. J., and Wallenius, J. 2018. "An interactive approximation algorithm for multi-objective integer programs", Computers Operations Research, 96, 80–90.
  • Lotov, A., V., Miettinen, K. 2008. “Visualizing the Pareto Frontier”. Multiobjective optimization. Editör: Branke, J., Deb, K., Miettinen, K. ve Slowinski, R. Berlin: Springer.
  • Masin, M., Bukchin, Y. 2008. "Diversity Maximization Approach for Multi-objective Optimization", Operations Research, 56 (2), 411-424.
  • Özarik, S. S. 2017. "Issues in Selecting a Representative Set for Multi-objective Integer Pro- grams", Yüksek Lisans Tezi, Fen Bilimleri Enstitüsü, Orta Doğu Teknik Üniversitesi.
  • Özlen, M., Azizoglu, M. 2009. "Multi-objective integer programming: A general approach for generating all non-dominated solutions", European Journal of Operational Research, 199 (1), 25–35.
  • Özlen, M., Burton, B. A., MacRae, C. A. 2014. "Multi-objective integer programming: An im- proved recursive algorithm", Journal of Optimization Theory and Applications, 160 (2), 470–482.
  • Phelps, S. and Köksalan, M. 2003. "An interactive evolutionary metaheuristic for multiobjective combinatorial optimization", Management Science , 49 (12), 1726–1738.
  • Przybylski, A., Gandibleux, X., Ehrgott, M. 2008. "Two phase algorithms for the bi-objective assignment problem", European Journal of Operational Research, 185 (2), 509–533.
  • Przybylski, A., Gandibleux, X., Ehrgott, M. 2010. "A recursive algorithm for finding all nondom-inated extreme points in the outcome set of a multiobjective integer programme", INFORMS Journal on Computing, 22 (3), 371–386.
  • Sayın, S. 2000. "Optimizing over the efficient set using a top-down search of faces. Operations Research", 48 (1), 65–72.
  • Sayın, S. 2000. "Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming", Mathematical Programming, 87 (3), 543-560.
  • Steuer, R. E. 1986. Multiple Criteria Optimization: Theory, Computation, and Application, New York: John Wiley Sons, Inc.
  • Sylva, J., Crema, A. 2004. "A method for finding the set of non-dominated vectors for multiple objective integer linear programs", European Journal of Operational Research, 158 (1), 46-55.
  • Sylva, J., Crema, A. 2007. "A method for finding well-dispersed subsets of non-dominated vec- tors for multiple objective mixed integer linear programs", European Journal of Operational Re- search, 180 (3), 1011-1027.
  • Zitzler, E., Thiele, L. 1999. "Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach", IEEE transactions on Evolutionary Computation, 3 (4), 257–271.
APA LOKMAN B, KÖKSALAN M (2018). Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. , 1 - 0.
Chicago LOKMAN Banu,KÖKSALAN Mustafa Murat Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. (2018): 1 - 0.
MLA LOKMAN Banu,KÖKSALAN Mustafa Murat Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. , 2018, ss.1 - 0.
AMA LOKMAN B,KÖKSALAN M Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. . 2018; 1 - 0.
Vancouver LOKMAN B,KÖKSALAN M Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. . 2018; 1 - 0.
IEEE LOKMAN B,KÖKSALAN M "Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar." , ss.1 - 0, 2018.
ISNAD LOKMAN, Banu - KÖKSALAN, Mustafa Murat. "Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar". (2018), 1-0.
APA LOKMAN B, KÖKSALAN M (2018). Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. , 1 - 0.
Chicago LOKMAN Banu,KÖKSALAN Mustafa Murat Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. (2018): 1 - 0.
MLA LOKMAN Banu,KÖKSALAN Mustafa Murat Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. , 2018, ss.1 - 0.
AMA LOKMAN B,KÖKSALAN M Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. . 2018; 1 - 0.
Vancouver LOKMAN B,KÖKSALAN M Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar. . 2018; 1 - 0.
IEEE LOKMAN B,KÖKSALAN M "Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar." , ss.1 - 0, 2018.
ISNAD LOKMAN, Banu - KÖKSALAN, Mustafa Murat. "Çok Amaçlı Tamsayı Problemlerinde Baskın Çözümler Üzerine: Analizler, Yaklaşımlar ve Uygulamalar". (2018), 1-0.
  • 1- ÇOK AMAÇLI TAMSAYI PROGRAMLAMA PROBLEMLERİ İÇİN TEMSİLİ ÇÖZÜM ÜRETEN YAKLAŞIMLARIN VE KALİTE ÖLÇÜLERİNİN İNCELENMESİ (Makale - Diğer Hakemli Makale),
  • 2- A web-based solution platform for Multi-objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • 3- A Web Application For Solving Multi-objective Integer Programming Problems (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • 4- Representing the Nondominated Set for Multi-objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • 5- Issues in Selecting a Representative Set for Multi-Objective Integer Programs (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • 6- ISSUES IN SELECTING A REPRESENTATIVE SET FOR MULTI-OBJECTIVE INTEGER PROGRAMS (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),
  • 7- ISSUES IN SELECTING A REPRESENTATIVE SET FOR MULTI-OBJECTIVE INTEGER PROGRAMS (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),
  • 8- Representing the nondominated set with a small subset in multi-objective mixed integer programs (Tez (Araştırmacı Yetiştirilmesi) - Yüksek Lisans Tezi),