L. Galli, S. Martello, C. Rey, P. Toth
The Quadratic Multiple Knapsack Problem (QMKP) generalizes, simultaneously, two well-known combinatorial optimization problems that have been intensively studied in the literature: the (single) Quadratic Knapsack Problem and the Multiple Knapsack Problem. Owing to its many practical applications, that range from project management to capital budgeting to product-distribution system design, as well as to its mathematical structure borrowing from well-studied combinatorial problems, the problem has received increasing attention in the literature over the last fifteen years, mostly concentrating on exponential-size formulations and meta-heuristic approaches. QMKP is strongly NP-hard and very difficult to solve in practice. We propose effective matheuristic algorithms, based on Lagrangian relaxation and on the optimal solution of Integer Linear Programming models. Computational results on small-size benchmark instances and on new randomly generated medium-size instances are reported. These results show the good performance of the proposed algorithms, which are able to determine, within reasonable computing times, either optimal or nearly optimal solutions.
Keywords: Quadratic Multiple Knapsack, Lagrangian Relaxation, Matheuristic
Scheduled
TD2 Quadratic Assignment and Knapsack Optimization
June 10, 2021 2:45 PM
2 - LV Kantorovich
