A k-means binarization framework applied to multidimensional knapsack problem

José García, BRODERICK CRAWFORD LABRIN, RICARDO JAVIER SOTO DE GIORGIS, Carlos Castro, Fernando Paredes

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

The multidimensional knapsack problem (MKP) is one of the widely known integer programming problems. The MKP has received significant attention from the operational research community for its large number of applications. Solving this NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. In this paper we present a k-means transition ranking (KMTR) framework to solve the MKP. This framework has the property to binarize continuous population-based metaheuristics using a data mining k-means technique. In particular we binarize a Cuckoo Search and Black Hole metaheuristics. These techniques were chosen by the difference between their iteration mechanisms. We provide necessary experiments to investigate the role of key ingredients of the framework. Finally to demonstrate the efficiency of our proposal, MKP benchmark instances of the literature show that KMTR competes with the state-of-the-art algorithms.

Original languageEnglish
Pages (from-to)357-380
Number of pages24
JournalApplied Intelligence
Volume48
Issue number2
DOIs
StatePublished - 1 Feb 2018

Keywords

  • Binarization
  • Data mining
  • k-means
  • Metaheuristics
  • Multidimensional knapsack problem

Fingerprint Dive into the research topics of 'A k-means binarization framework applied to multidimensional knapsack problem'. Together they form a unique fingerprint.

Cite this