COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS
Yıl: 2019 Cilt: 5 Sayı: 1 Sayfa Aralığı: 34 - 42 Metin Dili: İngilizce DOI: 10.22531/muglajsci.469475 İndeks Tarihi: 09-07-2020
COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS
Öz: This paper focus on comparing the differences and similarities between the results obtained from Greedy and classicalalgorithms for integer linear programming (ILP) problems. For this purpose, the solution of the problems related todifferent models with the purpose function and constraints has been provided by developing a software (Java Program)which solves the Knapsack problems (KP) with Greedy algorithm. Both the classical algorithm and the results obtainedfrom Greedy algorithm are compared for the problems considered here. In this context, the results obtained from algorithmsare found to be the same for small-sized pure and 0-1 binary Knapsack problems. Since packet programs are limited indimension and number of constraints, it becomes difficult to obtain appropriate results from classical algorithms as thedimension of the problem grows. However, Greedy algorithm gives the appropriate results regardless of the dimension andthe number of constraints.
Anahtar Kelime: TAMSAYILI PROGRAMLAMADA KLASİK VE GREEDY SEZGİSEL ALGORiTMALARININ KARŞILAŞTIRILMASI: SIRT ÇANTASI PROBLEMLERİ
Öz: Bu çalışmada, tamsayılı doğrusal programlama (TDP) problemleri için Greedy ve klasik algoritmalardan elde edilen sonuçlar arasındaki fark ve benzerlikler karşılaştırılmıştır. Bu amaçla, Sırt Çantası Problemlerini (SÇP) Greedy algoritmasıyla çözen bir yazılım (Java Program) geliştirerek, amaç fonksiyonu ve kısıtları verilmiş farklı modellere ilişkin problemlere çözüm sağlanmıştır. Dikkate alınan problemler için hem klasik algoritma hem de Greedy algoritmasından elde edilen sonuçlar karşılaştırılmıştır. Bu bağlamda, küçük boyutlu saf ve 0-1 binary sırt çantası problemleri için algoritmalardan elde edilen sonuçlar aynı bulunmuştur. Paket programlar boyut ve kısıt sayısı ile sınırlı olduğundan problemin boyutu büyüdükçe klasik algoritmalar için uygun sonuç elde etmek zorlaşmaktadır. Ancak, Greedy algoritması, boyut ve kısıt sayısını dikkate almaksızın uygun sonuç vermektedir.
Anahtar Kelime: Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
- [1] Bakır, M.A. and Altunkaynak, B., Tamsayılı Programlama Teori, Modeller ve Algoritmaları, Nobel Yayın Dağıtım, Ankara, 2003.
- [2] Başkaya, Z., Tamsayılı Programlama Algoritmaları ve Bilgisayar Uygulamalı Problem Çözümleri, Başak Matbaacılık, Ankara, 2005.
- [3] Güler, A., Tamsayılı Programlama Problemleri İçin Garanti Değerli Algoritmalar, Ege University, Graduate School of Natural and Applied Sciences, Master Thesis, İzmir, 2008.
- [4] Akçay, Y., Li, H. and Xu, S.H, “Greedy Algorithm for the General Multidimensional Knapsack Problems”, Annals of Operations Research, 150, 17-29, 2007.
- [5] Liu, L., “Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method”, Advanced Materials Research, 282-283, 570-573, 2011.
- [6] Lv, J., Wang, X., Huang, M., Cheng, H. and Li, F., “Solving 0-1 Knapsack Problem by Greedy Degree and Expectation Efficiency”, Applied Soft Computing, 41, 94-103, 2016.
- [7] Zhou, Y., Chen, X. and Zhou, G., “An Improved Monkey Algorithm for a 0-1 Knapsack Problem”, Applied Soft Computing, 38, 817-830, 2016.
- [8] Bulut, F. and İnce, İ.F., “Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0-1 Sırt Çantası Problemine Yeni Bir Bakış”, Karaelmas Fen ve Mühendislik Dergisi, 8(1), 89- 98, 2018.
- [9] Winston, W.L., Operations Research Applications and Algorithms, Canada, 2004.
- [10] Taha, H., Yöneylem Araştırması, Literatür Yayıncılık, İstanbul, 2000.
- [11] Hillier, F. S. and Lieberman, G. J., Introduction to Operations Research, McGraw-Hill, New York, 2001.
- [12] Schrijver, A., Theory of Linear and Integer Programming, A Wiley-Interscience Publication, Amsterdam, 1999.
- [13] Keskintürk, T., Topuk, N. and Özyeşil, O., “Araç Rotalama Problemleri İle Çözüm Yöntemlerinin Sınıflandırılması ve Bir Uygulama”, The Journal of Business Science, 3(2), 77- 107, 2015.
- [14] Sağır, M., Öztürk, A. and Öztürk, Ö., Yöneylem Araştırması- 2, Anadolu Üniversitesi Açıköğretim Yayınları, Eskişehir, 2013.
- [15] Yıldırım, T., Kalaycı, C.B. and Mutlu, Ö., “Gezgin Satıcı Problemi İçin Yeni Bir Meta Sezgisel: Kör Fare Algoritması”, Pamukkale University Journal of Engineering Sciences, 22(1), 64-70, 2016.
- [16] Pearl, J., Heuristics Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publishing Company, 1984.
- [17] Durmuş, B., Tamsayılı Programlamada Klasik ve Greedy Sezgisel Algoritma Sonuçlarının Karşılaştırılması, Muğla Sıtkı Koçman University, Graduate School of Natural and Applied Sciences, Master Thesis, Muğla, 2018.
- [18] Alwan, H.O. and Farhan, N.M., “Load Restoration Methodology Considering Renewable Energies and Combined Heat and Power Systems”, International Journal of Engineering and Technology, 7(2.6), 130-134, 2018.
- [19] Gorski, J., Paquete, L. and Pedrosa, F., “Greedy Algorithms for a Class of Knapsack Problems with Binary Weights”, Computers and Operations Research, 39, 498-511, 2012.
| APA | Durmuş B, ISÇI GÜNERI O, İNCEKIRIK A (2019). COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. , 34 - 42. 10.22531/muglajsci.469475 |
| Chicago | Durmuş Burcu,ISÇI GÜNERI OZNUR,İNCEKIRIK Aynur COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. (2019): 34 - 42. 10.22531/muglajsci.469475 |
| MLA | Durmuş Burcu,ISÇI GÜNERI OZNUR,İNCEKIRIK Aynur COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. , 2019, ss.34 - 42. 10.22531/muglajsci.469475 |
| AMA | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. . 2019; 34 - 42. 10.22531/muglajsci.469475 |
| Vancouver | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. . 2019; 34 - 42. 10.22531/muglajsci.469475 |
| IEEE | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A "COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS." , ss.34 - 42, 2019. 10.22531/muglajsci.469475 |
| ISNAD | Durmuş, Burcu vd. "COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS". (2019), 34-42. https://doi.org/10.22531/muglajsci.469475 |
| APA | Durmuş B, ISÇI GÜNERI O, İNCEKIRIK A (2019). COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. Mugla Journal of Science and Technology, 5(1), 34 - 42. 10.22531/muglajsci.469475 |
| Chicago | Durmuş Burcu,ISÇI GÜNERI OZNUR,İNCEKIRIK Aynur COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. Mugla Journal of Science and Technology 5, no.1 (2019): 34 - 42. 10.22531/muglajsci.469475 |
| MLA | Durmuş Burcu,ISÇI GÜNERI OZNUR,İNCEKIRIK Aynur COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. Mugla Journal of Science and Technology, vol.5, no.1, 2019, ss.34 - 42. 10.22531/muglajsci.469475 |
| AMA | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. Mugla Journal of Science and Technology. 2019; 5(1): 34 - 42. 10.22531/muglajsci.469475 |
| Vancouver | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS. Mugla Journal of Science and Technology. 2019; 5(1): 34 - 42. 10.22531/muglajsci.469475 |
| IEEE | Durmuş B,ISÇI GÜNERI O,İNCEKIRIK A "COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS." Mugla Journal of Science and Technology, 5, ss.34 - 42, 2019. 10.22531/muglajsci.469475 |
| ISNAD | Durmuş, Burcu vd. "COMPARISON OF CLASSIC AND GREEDY HEURISTIC ALGORITHM RESULTS IN INTEGER PROGRAMMING: KNAPSACK PROBLEMS". Mugla Journal of Science and Technology 5/1 (2019), 34-42. https://doi.org/10.22531/muglajsci.469475 |
