Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış

İNCE, İBRAHİM FURKAN; BULUT, Faruk

Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış

Faruk BULUT, (İstanbul Rumeli Üniversitesi)

İbrahim Furkan İNCE (Kyungsung University)

Karaelmas Fen ve Mühendislik Dergisi

13 0

Yıl: 2018 Cilt: 8 Sayı: 1 Sayfa Aralığı: 89 - 98 Metin Dili: Türkçe İndeks Tarihi: 02-02-2020

Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış

Öz:

Tam sayılı programlama, bir çeşit optimize edilmiş Lineer Programlama olarak adlandırılan doğrusal programlama yöntemidir. Amaçdoğrusal programlamada meydana gelebilecek gerçekçi olmayan sonuçları ortadan kaldırmaktır. Tam sayılı Programlama birçokmühendislik alanına uygulanmaktadır. Bu çalışmada, Tam sayılı Programlama yöntemine sezgisel ve açgözlü bir yaklaşım eklenerek çokbilinen ve birçok mühendislik uygulamasının kaynağı olan “sırt çantası” problemine uygulanmıştır. Ayrıca Yığın veri yapısı kullanılarakalan karmaşıklığı en aza indirilmiş ve daha hızlı sonuçlara ulaşılmıştır. Yapılan deneysel uygulamalarda önerilen yöntemin özyinelemeli,kesmeli ve optimize edilmiş yöntemlere göre daha az hesaplama zamanı içerisinde sonuç verdiği gözlemlenmiştir.

Anahtar Kelime:

Konular: Bilgisayar Bilimleri, Yazılım Mühendisliği

A New Approach to 0/1 Knapsack Problem with Greedy and Heuristic Searches in Integer Programming

Öz:

Integer programming is a type of optimized Linear Programming method. The goal is to get rid of unrealistic results that might occur in the linear programming process. Integer Programming is applied to many engineering fields. In this study, a new heuristic and greedy approach to the conventional Integer Programming method is proposed to the well-known knapsack problem, which is accepted as the source of many engineering problems. Heap data structure, additionally, is used in order to decrease both space complexity and implementation time. In the experimental applications, it is observed that the proposed method yields less computational time than the recursive, pruned, and optimized methods.

Anahtar Kelime:

Konular: Bilgisayar Bilimleri, Yazılım Mühendisliği

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

Bosch, R., Michael, T. 2014. Integer programming. Search methodologies. Springer USA, 67-92.
Brucker, P., Jurisch, B., Sievers, B. 1994. A branch and bound algorithm for the job-shop scheduling problem. Disc. App. Math. 49(1):107-127.
Brusco, MJ., Stahl, S. 2006. Branch-and-bound applications in combinatorial data analysis. Springer Science & Business Media.
Bulut, F. 2018. Study of BB, Branch&Bound, https://sites.google. com/site/bulutfaruk/study-of-bb Erişim tarihi: Ocak 30, 2018.
Chekuri, C., Khanna, S. 2005. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J.. Comp., 35(3): 713-728.
Conforti, M., Cornuéjols, G., Zambelli, G. 2014. Integer Programming Models. Integer Programming. Springer International Publishing, pp. 45-84.
Cormen, TH., Leiserso, CE. 2009. Introduction to algorithms. MIT press. ISBN-13: 978-0262033848, Cambridge.
Cornuéjols, G. 2007. Revival of the Gomory cuts in the 1990’s. An. Op. Res., 149(1), 63-66.
Delling, D., Sanders, P., Schultes, D., Wagner, D. 2009. Algorithmics of large and complex networks: design, analysis, and simulation. Springer, New York.
Fisher, ML. 2004. The Lagrangian relaxation method for solving integer programming problems. Man. Sci., 50(12): 1861-1871. Hochbaum, DS. 1995. A nonlinear knapsack problem. Opr. Res. Let., 17(3): 103-110.
Kellerer, H., Pferschy, U., Pisinger, D. 2004. Introduction to NPCompleteness of knapsack problems. In Knapsack problems. Springer Berlin Heidelberg. pp. 483-493.
Khuri, S., Bäck, T., Heitkötter, J. 1994. The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 ACM symposium on Applied computing. pp. 188-193. Arizona.
Kong, M., Tian, P., Kao, Y. 2008. A new ant colony optimization algorithm for the multidimensional knapsack problem. Comp. Op. Res., 35(8): 2672-2683.
Li, J., Xiu-xia S. 2008. A Route Planning’s Method for Unmanned Aerial Vehicles Based on Improved A-Star Algorithm [J]. Acta Armamentarii, 7: 788-792.
Martello, S., Pisinger, D., Toth P. 2000. New trends in exact algorithms for the 0–1 knapsack problem. European J. Op. Res.123(2):325-332.
Martello, S., Pisinger, D., Toth, P. 1999. Dynamic programming and strong bounds for the 0-1 knapsack problem. Mang. Sci., 45(3): 414-424.
Mitzenmacher, M., Upfal, E. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge university press.
Ohlsson, M., Peterson, C., Söderberg, B. 2008. Neural networks for optimization problems with inequality constraints: the knapsack problem. Nrl. Ntw., 5(2).
Pisinger, D. 2005. Where are the hard knapsack problems?. Comp. Op. Res. 32(9):2271-2284.
Puchinger, J., Raidl, G. R., Pferschy, U. 2010. The multidimensional knapsack problem: Structure and algorithms. INFORMS J. Comp., 22(2): 250-265.
Ross, SM. 2014. Introduction to stochastic dynamic programming. Academic Press, New York, USA.
Taha, HA. 2014. Integer Programming: Theory, Applications, and Computations. Academic Press, New York.
Vanderbei, RJ. 2015. Linear Programming Book, Publisher: Springer, New York.
Zhang, W. 1999. State-space search: Algorithms, complexity, extensions, and applications. Springer Science & Business Media.
Zou, D., Gao, L., Li, S., Wu, J. 2011. Solving 0–1 knapsack problem by a novel global harmony search algorithm. App. So. Comp., 11(2): 1556-1564.

APA	BULUT F, İNCE İ (2018). Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış. , 89 - 98.
Chicago	BULUT Faruk,İNCE İBRAHİM FURKAN Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış. (2018): 89 - 98.
MLA	BULUT Faruk,İNCE İBRAHİM FURKAN Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış. , 2018, ss.89 - 98.
AMA	BULUT F,İNCE İ Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış. . 2018; 89 - 98.
Vancouver	BULUT F,İNCE İ Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış. . 2018; 89 - 98.
IEEE	BULUT F,İNCE İ "Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış." , ss.89 - 98, 2018.
ISNAD	BULUT, Faruk - İNCE, İBRAHİM FURKAN. "Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış". (2018), 89-98.

APA	BULUT F, İNCE İ (2018). 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.
Chicago	BULUT Faruk,İNCE İBRAHİM FURKAN 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, no.1 (2018): 89 - 98.
MLA	BULUT Faruk,İNCE İBRAHİM FURKAN 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, vol.8, no.1, 2018, ss.89 - 98.
AMA	BULUT F,İNCE İ 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. 2018; 8(1): 89 - 98.
Vancouver	BULUT F,İNCE İ 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. 2018; 8(1): 89 - 98.
IEEE	BULUT F,İNCE İ "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, ss.89 - 98, 2018.
ISNAD	BULUT, Faruk - İNCE, İBRAHİM FURKAN. "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 (2018), 89-98.