Knapsack Problems

Thirteen years have passed since the seminal book on knapsack problems by Martello and Toth appeared. On this occasion a former colleague exclaimed back in 1990: "How can you write 250 pages on the knapsack problem?" Indeed, the definition of the knapsack problem is easily understood even by a non-expert who will not suspect the presence of challenging research topics in this area at the first glance. However, in the last decade a large number of research publications contributed new results for the knapsack problem in all areas of interest such as exact algorithms, heuristics and approximation schemes. Moreover, the extension of the knapsack problem to higher dimensions both in the number of constraints and in the num­ ber of knapsacks, as well as the modification of the problem structure concerning the available item set and the objective function, leads to a number of interesting variations of practical relevance which were the subject of intensive research during the last few years. Hence, two years ago the idea arose to produce a new monograph covering not only the most recent developments of the standard knapsack problem, but also giving a comprehensive treatment of the whole knapsack family including the siblings such as the subset sum problem and the bounded and unbounded knapsack problem, and also more distant relatives such as multidimensional, multiple, multiple-choice and quadratic knapsack problems in dedicated chapters.

Contenu

1 Introduction.- 1.1 Introducing the Knapsack Problem.- 1.2 Variants and Extensions of the Knapsack Pr©blem.- 1.3 Single-Capacity Versus All-Capacities Problem.- 1.4 Assumptions on the Input Data.- 1.5 Performance of Algorithms.- 2. Basic Algorithmic Concepts.- 2.1 The Greedy Algorithm.- 2.2 Linear Programming Relaxation.- 2.3 Dynamic Programming.- 2.4 Branch-and-Bound.- 2.5 Approximation Algorithms.- 2.6 Approximation Schemes.- 3. Advanced Algorithmic Concepts.- 3.1 Finding the Split Item in Linear Time.- 3.2 Variable Reduction.- 3.3 Storage Reduction in Dynamic Programming.- 3.4 Dynamic Programming with Lists.- 3.5 Combining Dynamic Programming and Upper Bounds.- 3.6 Balancing.- 3.7 Word RAM Algorithms.- 3.8 Relaxations.- 3.9 Lagrangian Decomposition.- 3.10 The Knapsack Polytope.- 4. The Subset Sum Problem.- 4.1 Dynamic Programming.- 4.1.1 Word RAM Algorithm.- 4.1.2 Primal-Dual Dynamic Programming Algorithms.- 4.1.3 Primal-Dual Word-RAM Algorithm.- 4.1.4 Horowitz and Sahni Decomposition.- 4.1.5 Balancing.- 4.1.6 Bellman Recursion in Decision Form.- 4.2 Branch-and-Bound.- 4.2.1 Upper Bounds.- 4.2.2 Hybrid Algorithms.- 4.3 Core Algorithms.- 4.3.1 Fixed Size Core.- 4.3.2 Expanding Core.- 4.3.3 Fixed Size Core and Decomposition.- 4.4 Computational Results: Exact Algorithms.- 4.4.1 Solution of All-Capacities Problems.- 4.5 Polynomial Time Approximation Schemes for Subset Sum.- 4.6 A Fully Polynomial Time Approximation Scheme for Subset Sum.- 4.7 Computational Results: FPTAS.- 5. Exact Solution of the Knapsack Problem.- 5.1 Branch-and-Bound.- 5.1.1 Upper Bounds f©r (KP).- 5.1.2 Lower Bounds for (KP).- 5.1.3 Variable Reduction.- 5.1.4 Branch-and-Bound Implementations.- 5.2 Primal Dynamic Programming Algorithms.- 5.2.1 Word RAM Algorithm.- 5.2.2 Horowitz and Sahni Decomposition.- 5.3 Primal-Dual Dynamic Programming Algorithms.- 5.3.1 Balanced Dynamic Programming.- 5.4 The Core Concept.- 5.4.1 Finding a Core.- 5.4.2 Core Algorithms.- 5.4.3 Combining Dynamic Programming with Tight Bounds.- 5.5 Computational Experiments.- 5.5.1 Difficult Instances.- 5.5.2 Difficult Instances with Large Coefficients.- 5.5.3 Difficult Instances With Small Coefficients.- 6. Approximation Algorithms for the Knapsack Problem.- 6.1 Polynomial Time Approximation Schemes.- 6.1.1 Improving the PTAS for (KP).- 6.2 Fully Polynomial Time Approximation Schemes.- 6.2.1 Scaling and Reduction of the Item Set.- 6.2.2 An Auxiliary Vector Merging Problem.- 6.2.3 Solving the Reduced Problem.- 6.2.4 Putting the Pieces Together.- 7. The Bounded Knapsack Problem.- 7.1 Introduction.- 7.1.1 Transformation of (BKP) into (KP).- 7.2 Dynamic Programming.- 7.2.1 A Minimal Algorithm for (BKP).- 7.2.2 Improved Dynamic Programming: Reaching (KP) Complexity for (BKP).- 7.2.3 Word RAM Algorithm.- 7.2.4 Balancing.- 7.3 Branch-and-Bound.- 7.3.1 Upper Bounds.- 7.3.2 Branch-and Bound Algorithms.- 7.3.3 Computational Experiments.- 7.4 Approximation Algorithms.- 8. The Unbounded Knapsack Problem.- 8.1 Introduction.- 8.2 Periodicity and Dominance.- 8.2.1 Periodicity.- 8.2.2 Dominance.- 8.3 Dynamic Programming.- 8.3.1 Some Basic Algorithms.- 8.3.2 An Advanced Algorithm.- 8.3.3 Word RAM Algorithm.- 8.4 Branch-and-Bound.- 8.5 Approximation Algorithms.- 9 Multidimensional Knapsack Problems.- 9.1 Introduction.- 9.2 Relaxations and Reductions.- 9.3 Exact Algorithms.- 9.3.1 Branch-and-Bound Algorithms.- 9.3.2 Dynamic Programming.- 9.4 Approximation.- 9.4.1 Negative Approximation Results.- 9.4.2 Polynomial Time Approximation Schemes.- 9.5 Heuristic Algorithms.- 9.5.1 Greedy-Type Heuristics.- 9.5.2 Relaxation-Based Heuristics.- 9.5.3 Advanced Heuristics.- 9.5.4 Approximate Dynamic Programming.- 9.5.5 Metaheuristics.- 9.6 The Two-Dimensional Knapsack Problem.- 9.7 The Cardinality Constrained Knapsack Problem.- 9.7.1 Related Problems.- 9.7.2 Branch-and-Bound.- 9.7.3 Dynamic Programming.- 9.7.4 Approximation Algorithms.- 9.8 The Multidimensional Multiple-Choice Knapsack Problem.- 10. Multiple Knapsack Problems.- 10.1 Introduction.- 10.2 Upper Bounds.- 10.2.1 Variable Reduction and Tightening of Constraints.- 10.3 Branch-and-Bound.- 10.3.1 The MTM Algorithm.- 10.3.2 The Mulknap Algorithm.- 10.3.3 Computational Results.- 10.4 Approximation Algorithms.- 10.4.1 Greedy-Type Algorithms and Further Approximation Algorithms.- 10.4.2 Approximability Results for (B-MSSP).- 10.5 Polynomial Time Approximation Schemes.- 10.5.1 A PTAS for the Multiple Subset Problem.- 10.5.2 A PTAS for the Multiple Knapsack Problem.- 10.6 Variants of the Multiple Knapsack Problem.- 10.6.1 The Multiple Knapsack Problem with Assignment Restrictions.- 10.6.2 The Class-Constrained Multiple Knapsack Problem.- 11. The Multiple-Choice Knapsack Problem.- 11.1 Introduction.- 11.2 Dominance and Upper Bounds.- 11.2.1 Linear Time Algorithms for the LP-Relaxed Problem.- 11.2.2 Bounds from Lagrangian Relaxation.- 11.2.3 Other Bounds.- 11.3 Class Reduction.- 11.4 Branch-and-Bound.- 11.5 Dynamic Programming.- 11.6 Reduction of States.- 11.7 Hybrid Algorithms and Expanding Core Algorithms.- 11.8 Computational Experiments.- 11.9 Heuristics and Approximation Algorithms.- 11.10 Variants of the Multiple-Choice Knapsack Problem.- 11.10.1 Multiple-Choice Subset Sum Problem.- 11.10.2 Generalized Multiple-Choice Knapsack Problem.- 11.10.3 The Knapsack Sharing Problem.- 12. The Quadratic Knapsack Problem.- 12.1 Introduction.- 12.2 Upper Bounds.- 12.2.1 Continuous Relaxation.- 12.2.2 Bounds from Lagrangian Relaxation of the Capacity Constraint.- 12.2.3 Bounds from Upper Planes.- 12.2.4 Bounds from Linearisation.- 12.2.5 Bounds from Reformulation.- 12.2.6 Bounds from Lagrangian Decomposition.- 12.2.7 Bounds from Semidefinite Relaxation.- 12.3 Variable Reduction.- 12.4 Branch-and-Bound.- 12.5 The Algorithm by Caprara, Pisinger and Toth.- 12.6 Heuristics.- 12.7 Approximation Algorithms.- 12.8 Computational Experiments Exact Algorithms.- 12.9 Computational Experiments Upper Bounds.- 13. Other Knapsack Problems.- 13.1 Multiobjective Knapsack Problems.- 13.1.1 Introduction.- 13.1.2 Exact Algorithms for (MOKP).- 13.1.3 Approximation of the Multiobjective Knapsack Problem.- 13.1.4 An FPTAS for the Multiobjective Knapsack Problem.- 13.1.5 A PTAS for (MOd-KP).- 13.1.6 Metaheuristics.- 13.2 The Precedence Constraint Knapsack Problem (PCKP).- 13.2.1 Dynamic Programming Algorithms for Trees.- 13.2.2 Other Results for (PCKP).- 13.3 Further Variants.- 13.3.1 Nonlinear Knapsack Problems.- 13.3.2 The Max-Min Knapsack Problem.- 13.3.3 The Minimizatio…