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.
Lagrangian matheuristics for the Quadratic Multiple Knapsack Problem
Galli L.
;
2022-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
qmkp_DAM.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
324.21 kB
Formato
Adobe PDF
|
324.21 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.