A Simple Iterative Algorithm for Boolean Knapsack Problem

Nuriyeva F., Nuriye U., Ugurlu O.

International Conference on Artificial Intelligence and Applied Mathematics in Engineering (ICAIAME), Antalya, Türkiye, 20 - 22 Nisan 2019, cilt.43, ss.684-689, (Tam Metin Bildiri) identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 43
  • Doi Numarası: 10.1007/978-3-030-36178-5_57
  • Basıldığı Şehir: Antalya
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.684-689
  • Anahtar Kelimeler: Combinatorial optimization, Boolean knapsack problem, Greedy method
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

The Boolean Knapsack Problem, which has numerous real life applications, is a combinatorial optimization problem. Since the problem belongs to NP-Hard, many researchers have worked on several variants of the problem. In this paper a simple iterative algorithm based on a greedy strategy to solve the classical boolean knapsack problem is proposed. In algorithm, firstly initial solutions are generated, then a greedy criteria is used to improve these solutions. To demonstrate the performance of the proposed method, experiments are carried out with various benchmark instances of boolean Knapsack Problem. The computational results show that the proposed algorithm is functional enough to achieve acceptable results in reasonable times.