Using surrogate information to solve the multidimensional multi-choice knapsack problem

In this paper we present a new heuristic for solving the multidimensional multi-choice knapsack problem called MMKP. The main idea is to explore both sides of the feasibility border that consists in alternating both constructive and destructive phases in a strategic oscillating manner. Performance analysis of the method shows the merits of using surrogate constraint information as choice rules for solving this problem class. A constraint normalization method is also used to strengthen the surrogate constraint information in order to improve the computational results. Numerical results show that the performance of this approach is competitive with previously published results.