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

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.