Competitive Decision Algorithm for Multiple-Choice Knapsack Problem Based on Reduction
Xiong Xiao-hua, Ma Liang, Ning Ai-bing · 2010
The multiple-choice knapsack problem (MCKP) is a classified NP-hard optimization problem, which is a generalization of the simple knapsack problem (KP). Hence algorithms for finding the exact solution of MCKP are not suitable for application in real-time decision-making applications. This paper presents a competitive decision algorithm (CDA) for MCKP. CDA is newly proposed meta-heuristic algorithm for solving complex optimization problems. It investigates natural selection process in the real world by recognizing that an entity with more resources has a high chance to survive. It uses the characteristics that competition builds optimization and the result of competition hinges on decision-making. On the other hand CDA is easy to combine with the properties of problem itself. We present an algorithm CDAMCKP to solve MCKP. At the start of the algorithm, we analysis several properties of MCKP and integrate them with the CDA to reduce the scale of original problem. The performance of the algorithm is evaluated on a set of medium and large scale instances, all of them are randomly generated. Extensive computational experience illustrates the efficiency of the algorithm and one example and its result are presented.