A k-means binarization framework applied to multidimensional knapsack problem

摘要

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.