After the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004), knapsack problems became a classical and rich research area in combinatorial optimization. The purpose of this survey, which is structured in two parts, is to cover the developments that appeared in this field after the publication of the latter volume. Part I is devoted to problems whose goal is to optimally assign items to a single knapsack. Besides the classical knapsack problems (binary, subset sum, bounded, unbounded, change-making), we review problems with special constraints (setups, multiple-choice, conflicts, precedences, sharing, compartments) as well as relatively recent fields of investigation, like robust and bilevel problems. The subsequent Part II covers multiple, multidimensional, and quadratic knapsack problems, and includes a succinct treatment of online and multiobjective knapsack problems.

Knapsack problems — An overview of recent advances. Part I: Single knapsack problems / Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 143:(2022), pp. 1-13. [10.1016/j.cor.2021.105692]

Knapsack problems — An overview of recent advances. Part I: Single knapsack problems

Iori M.;Locatelli A.;
2022

Abstract

After the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004), knapsack problems became a classical and rich research area in combinatorial optimization. The purpose of this survey, which is structured in two parts, is to cover the developments that appeared in this field after the publication of the latter volume. Part I is devoted to problems whose goal is to optimally assign items to a single knapsack. Besides the classical knapsack problems (binary, subset sum, bounded, unbounded, change-making), we review problems with special constraints (setups, multiple-choice, conflicts, precedences, sharing, compartments) as well as relatively recent fields of investigation, like robust and bilevel problems. The subsequent Part II covers multiple, multidimensional, and quadratic knapsack problems, and includes a succinct treatment of online and multiobjective knapsack problems.
2022
143
1
13
Knapsack problems — An overview of recent advances. Part I: Single knapsack problems / Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 143:(2022), pp. 1-13. [10.1016/j.cor.2021.105692]
Cacchiani, V.; Iori, M.; Locatelli, A.; Martello, S.
File in questo prodotto:
File Dimensione Formato  
CacchianiIoriLocatelliMartello2022-KP-Part-I.pdf

Accesso riservato

Descrizione: Articolo definitvo
Tipologia: Versione pubblicata dall'editore
Dimensione 454.86 kB
Formato Adobe PDF
454.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/1274238
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 45
  • ???jsp.display-item.citation.isi??? 37
social impact