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

Year 2018, Volume: 8 Issue: 1, 89 - 98, 01.01.2018

Faruk Bulut Furkan İbrahim İnce

Abstract

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çok mühendislik alanına uygulanmaktadır. Bu çalışmada, Tam sayılı Programlama yöntemine sezgisel ve açgözlü bir yaklaşım eklenerek çok bilinen 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ılarak alan 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

Keywords

Dal & Sınır algoritması, Sezgisel arama, Yığın

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

Abstract

Tam sayılı programlama, bir çeşit optimize edilmiş Lineer Programlama LP 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. LP birçok mühendislik alanına uygulanmaktadır. Bu çalışmada, LP yöntemine sezgisel bir yaklaşım eklenerek çok bilinen ve birçok mühendislik probleminin kaynağı olan sırt çantası problemine uygulanmıştır. Yapılan deneysel uygulamalarda önerilen yöntemin özyinelemeli, kesmeli ve optimize edilmiş yöntemlere göre daha az hesaplana zamanı içerisinde sonuç verdiği gözlemlenmiştir.

Keywords

Branch & Bound Algorithm, Heuristic search, Heap

References

• 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 NP- Completeness 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.