SavedAdd your journal

Journals / Karaelmas Fen ve Mühendislik Dergisi / 2018 / Cilt: 8 - Sayı: 1

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

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

FARUK BULUT
İBRAHİM FURKAN İNCE
Pages
89–98
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Tam sayılı programlama, bir çeşit optimize edilmiş Lineer Programlama LP olarak adlandırılan doğrusal programlama yöntemidir.
📊
Key Findings & Data:Amaç doğrusal programlamada meydana gelebilecek gerçekçi olmayan sonuçları ortadan kaldırmaktır.
💡
Conclusion & Impact: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.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Dal & Sınır algoritması · Sezgisel arama · Yığın

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.

Özet

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

🔖

Cite This Article

BULUT, F., İNCE, İ. F. (2018). A New Approach to 0/1 Knapsack Problem with Greedy and Heuristic Searches in Integer Programming. Karaelmas Fen ve Mühendislik Dergisi, Cilt: 8 - Sayı: 1, 89–98. https://ajindex.com/articles/197766

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (11)

  1. Bosch, R., Michael, T. 2014. Integer programming. Search methodologies. Springer USA, 67-92.
  2. 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.
  3. Brusco, MJ., Stahl, S. 2006. Branch-and-bound applications in combinatorial data analysis. Springer Science & Business Media. Bulut, F. 2018.
  4. Study of BB, Branch&Bound, https://sites.google. com/site/bulutfaruk/study-of-bb Erişim tarihi: Ocak 30, 2018.
  5. Chekuri, C., Khanna, S. 2005. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comp., 35(3): 713-728.
  6. Conforti, M., Cornuéjols, G., Zambelli, G. 2014. Integer Programming Models. Integer Programming. Springer International Publishing, pp. 45-84.
  7. 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.
  8. 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.
  9. Hochbaum, DS. 1995. A nonlinear knapsack problem. Opr. Res. Let., 17(3): 103-110.
  10. Kellerer, H., Pferschy, U., Pisinger, D. 2004. Introduction to NP- Completeness of knapsack problems. In Knapsack problems. Springer Berlin Heidelberg. pp. 483-493.
  11. 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.