BibTex RIS Kaynak Göster

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

Yıl 2018, Cilt: 8 Sayı: 1, 89 - 98, 01.01.2018

Faruk Bulut Furkan İbrahim İnce

Ö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ç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

Anahtar Kelimeler

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

Kaynakça

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

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

Yıl 2018, Cilt: 8 Sayı: 1, 89 - 98, 01.01.2018

Faruk Bulut Furkan İbrahim İnce

Öz

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.

Anahtar Kelimeler

Branch & Bound Algorithm Heuristic search Heap

Kaynakça

  • 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.
Toplam 13 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Bölüm Research Article
Yazarlar

Faruk Bulut Bu kişi benim

Furkan İbrahim İnce Bu kişi benim

Yayımlanma Tarihi 1 Ocak 2018
Yayımlandığı Sayı Yıl 2018 Cilt: 8 Sayı: 1

Kaynak Göster

APA Bulut, F., & İnce, F. İ. (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.
AMA Bulut F, İ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. Ocak 2018;8(1):89-98.
Chicago Bulut, Faruk, ve Furkan İbrahim İ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, sy. 1 (Ocak 2018): 89-98.
EndNote Bulut F, İnce Fİ (01 Ocak 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.
IEEE F. Bulut ve 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, c. 8, sy. 1, ss. 89–98, 2018.
ISNAD Bulut, Faruk - İnce, Furkan İbrahim. “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 (Ocak 2018), 89-98.
JAMA Bulut F, İ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. 2018;8:89–98.
MLA Bulut, Faruk ve Furkan İbrahim İ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, c. 8, sy. 1, 2018, ss. 89-98.
Vancouver Bulut F, İ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. 2018;8(1):89-98.