We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.

Mathematical models and decomposition methods for the multiple knapsack problem / Dell'Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 274:3(2019), pp. 886-899. [10.1016/j.ejor.2018.10.043]

Mathematical models and decomposition methods for the multiple knapsack problem

Dell'Amico, Mauro;Iori, Manuel;
2019

Abstract

We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches.
31-ott-2018
274
3
886
899
Mathematical models and decomposition methods for the multiple knapsack problem / Dell'Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 274:3(2019), pp. 886-899. [10.1016/j.ejor.2018.10.043]
Dell'Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano
File in questo prodotto:
File Dimensione Formato  
VQR_1-s2.0-S0377221718309111-main.pdf

non disponibili

Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 1.07 MB
Formato Adobe PDF
1.07 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
POST PRINT_Mathematical models and decomposition methods.pdf

accesso aperto

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 330.43 kB
Formato Adobe PDF
330.43 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1168937
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 24
social impact