Hybrid Heuristic Algorithm for the Multidimensional Knapsack Problem


ATILGAN C., NURİYEV U.

4th International Conference on Problems of Cybernetics and Informatics (PCI), Baku, Azerbaijan, 12 - 14 September 2012 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/icpci.2012.6486459
  • City: Baku
  • Country: Azerbaijan
  • Keywords: Knapsack problem, Boolean variables, hybrid heuristic, greedy algorithm, core approach
  • Dokuz Eylül University Affiliated: Yes

Abstract

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.