Abstract

Multidimensional knapsack problem (MKP) is very important and NP-hard. A strategy of mimetic profit/weight ratio (P/W-Rt) is proposed and accordingly, a fast particle swarm optimization algorithm is proposed. The most important merit of this strategy is that it can effectively solve MKP with arbitrary number of constraints under similar computing costs as one dimensional KP. Experiments illustrate the robust performance, efficiency, and computing costs independence with instance scale.

Paper Details