Mathematical models and decomposition methods for the multiple knapsack problem

Mauro Dell'Amico, Maxence Delorme*, Manuel Iori, Silvano Martello

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)886-899
Number of pages14
JournalEuropean Journal of Operational Research
Volume274
Issue number3
DOIs
Publication statusPublished - 1 May 2019
Externally publishedYes

Keywords

  • Combinatorial optimization
  • Decomposition methods
  • Exact algorithms
  • Multiple knapsack problem
  • Pseudo-polynomial formulations

Fingerprint Dive into the research topics of 'Mathematical models and decomposition methods for the multiple knapsack problem'. Together they form a unique fingerprint.

Cite this