A k-means binarization framework applied to multidimensional knapsack problem

José García, Broderick Crawford, Ricardo Soto, Carlos Castro, Fernando Paredes

Research output: Contribution to journalArticlepeer-review

64 Scopus citations


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
Issue number2
StatePublished - 1 Feb 2018


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


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

Cite this