Hybrid Heuristic Algorithm for the Multidimensional Knapsack Problem

ATILGAN C., NURİYEV U.

4th International Conference on Problems of Cybernetics and Informatics (PCI), Baku, Azerbaycan, 12 - 14 Eylül 2012 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/icpci.2012.6486459
  • Basıldığı Şehir: Baku
  • Basıldığı Ülke: Azerbaycan
  • Anahtar Kelimeler: Knapsack problem, Boolean variables, hybrid heuristic, greedy algorithm, core approach
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

In this work, a new hybrid heuristic algorithm for the 0/1 multidimensional knapsack problem is proposed. In the algorithm, Lagrange multipliers for every constraint are determined to reduce the problem to single dimension and some initial solutions are obtained with greedy algorithms. Then, these solutions are improved with iterative procedures. In order to test efficiency of the algorithm, computational experiments were done on some library problems in literature. It was observed that the algorithm has high efficiency in terms of solutions and time.