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.

Dell'Amico, M., Delorme, M., Iori, M., Martello, S. (2019). Mathematical models and decomposition methods for the multiple knapsack problem. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 274(3), 886-899 [10.1016/j.ejor.2018.10.043].

Mathematical models and decomposition methods for the multiple knapsack problem

Martello, Silvano
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.
2019
Dell'Amico, M., Delorme, M., Iori, M., Martello, S. (2019). Mathematical models and decomposition methods for the multiple knapsack problem. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 274(3), 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  
Handle_MKP.pdf

Open Access dal 01/11/2020

Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 330.43 kB
Formato Adobe PDF
330.43 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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