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


TD2 Quadratic Assignment and Knapsack Optimization
June 10, 2021  2:45 PM
2 - LV Kantorovich

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.