A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems

Multidimensional knapsack problem (MKP) is known to be a NP-hard problem, more specifically a NP-complete problem, which cannot be resolved in polynomial time up to now. MKP can be applicable in many management, industry and engineering fields, such as cargo loading, capital budgeting and resource allocation, etc. In this article, using a combinational permutation constructed by the convex combinatorial value (M_j=(1-lambda ) u_j+ lambda x^mathrm{LP}_j) of both the pseudo-utility ratios of MKP and the optimal solution (x^mathrm{LP}) of relaxed LP, we present a new hybrid combinatorial genetic algorithm (HCGA) to address multidimensional knapsack problems. Comparing to Chu’s GA (J Heuristics 4:63–86, 1998), empirical results show that our new heuristic algorithm HCGA obtains better solutions over 270 standard test problem instances.