Lagrangian matheuristics for the Quadratic Multiple Knapsack Problem

The Quadratic Multiple Knapsack Problem (QMKP) is a challenging combinatorial optimization problem combining the well-known Quadratic Knapsack Problem with the Multiple Knapsack Problem. After a long stream of research devoted to metaheuristic approaches for large-scale instances, only recently some authors started to study the mathematical properties of the QMKP and proposed exact solution methods for benchmark instances of smaller size. In this paper, we propose the first matheuristic approach for solving the QMKP approximately. The proposed method exploits the strength of a Lagrangian relaxation for the natural quadratic formulation of the QMKP to derive heuristic solutions. Postoptimization local search procedures are embedded in the final framework. Experimental studies show that the resulting deterministic matheuristic approach consistently delivers solutions of very good quality in short computing times.