Comparıson of Classıc And Greedy Heurıstıc Algorıthm Results in Integer Programmıng: Knapsack Problems

Abstract

This paper focus on comparing the differences and similarities between the results obtained from Greedy and classical algorithms for integer linear programming (ILP) problems. For this purpose, the solution of the problems related to different 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 obtained from Greedy algorithm are compared for the problems considered here. In this context, the results obtained from algorithms are found to be the same for small-sized pure and 0-1 binary Knapsack problems. Since packet programs are limited in dimension and number of constraints, it becomes difficult to obtain appropriate results from classical algorithms as the dimension of the problem grows. However, Greedy algorithm gives the appropriate results regardless of the dimension and the number of constraints.

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.