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. - STAMPA. - 143:(2022), pp. 105692.1-105692.13. [10.1016/j.cor.2021.105692]

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

Cacchiani V.
Primo
;
Martello S.
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
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. - STAMPA. - 143:(2022), pp. 105692.1-105692.13. [10.1016/j.cor.2021.105692]
Cacchiani V.; Iori M.; Locatelli A.; Martello S.
File in questo prodotto:
Eventuali allegati, non sono esposti

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/897290
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 21
social impact