Knapsack problems -- an overview of recent advances. I: Single knapsack problems
From MaRDI portal
Publication:2147010
DOI10.1016/j.cor.2021.105692OpenAlexW4210618000MaRDI QIDQ2147010
Valentina Cacchiani, Manuel Iori, Alberto Locatelli, Silvano Martello
Publication date: 22 June 2022
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2021.105692
Related Items
Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Lagrangian matheuristics for the quadratic multiple knapsack problem, Cutting and packing problems under uncertainty: literature review and classification framework, Approximating single- and multi-objective nonlinear sum and product knapsack problems, The knapsack problem with forfeit sets, LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup, Knapsack problems with position-dependent item weights or profits, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, A decomposition approach for multidimensional knapsacks with family‐split penalties
Uses Software
Cites Work
- The Subset Sum game
- An exact decomposition algorithm for the generalized knapsack sharing problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Exact solution of the robust knapsack problem
- The robust knapsack problem with queries
- A dynamic programming algorithm for the knapsack problem with setup
- Approximation algorithms for a bi-level knapsack problem
- The constrained compartmentalized knapsack problem: mathematical models and solution methods
- Tight bounds for periodicity theorems on the unbounded knapsack problem
- Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem
- Pinpointing the complexity of the interval min-max regret knapsack problem
- Clique-based facets for the precedence constrained knapsack problem
- The precedence constrained knapsack problem: separating maximally violated inequalities
- Approximation schemes for the parametric knapsack problem
- Unbounded knapsack problems with arithmetic weight sequences
- Resource allocation with time intervals
- Recoverable robust knapsacks: the discrete scenario case
- The knapsack sharing problem: an exact algorithm
- A multi-criteria approach to approximate solution of multiple-choice knapsack problem
- The multidimensional 0-1 knapsack problem -- bounds and computational aspects
- An exact algorithm for the knapsack sharing problem with common items
- Approximation schemes for knapsack problems with shelf divisions
- Knapsack polytopes: a survey
- A dynamic programming algorithm for the bilevel Knapsack problem
- An exact algorithm for the Knapsack problem with setup
- The linking set problem: a polynomial special case of the multiple-choice knapsack problem
- An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem
- The constrained compartmentalised knapsack problem
- Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
- The quadratic knapsack problem -- a survey
- Discrete optimization with interval data. Minmax regret and fuzzy approach
- Exact and heuristic solution approaches for the mixed integer setup knapsack problem
- Parallel time and space upper-bounds for the subset-sum problem
- Sensitivity analysis of the optimum to perturbation of the profit of a subset of items in the binary knapsack problem
- On the subset sum problem over finite fields
- Sensitivity of the optimum to perturbations of the profit or weight of an item in the binary Knapsack problem
- Totally greedy coin sets and greedy obstructions
- A hybrid algorithm for the unbounded knapsack problem
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Priority algorithms for the subset-sum problem
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- A cooperative local search-based algorithm for the multiple-scenario max-min knapsack problem
- Combinatorics of the change-making problem
- Knapsack problems with setups
- The multidimensional 0-1 knapsack problem: an overview.
- A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints
- The nonlinear knapsack problem - algorithms and applications
- Integer optimization with penalized fractional values: the knapsack case
- Subset sum problems with digraph constraints
- New exact approaches and approximation results for the penalized knapsack problem
- An exact approach for the 0-1 knapsack problem with setups
- A low-space algorithm for the subset-sum problem on GPU
- Exact approaches for the knapsack problem with setups
- On the product knapsack problem
- A PTAS for the time-invariant incremental knapsack problem
- Solving the multiscenario max-MIN knapsack problem exactly with column generation and branch-and-bound
- A new fully polynomial time approximation scheme for the interval subset sum problem
- A faster FPTAS for the unbounded knapsack problem
- Change-making problems revisited: a parameterized point of view
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- Approximating the 3-period incremental knapsack problem
- An improved balanced algorithm for the subset-sum problem
- An empirical analysis of exact algorithms for the unbounded knapsack problem
- On the best choice of a branching variable in the subset sum problem
- The \(k\)-subset sum problem over finite fields
- The multi-band robust knapsack problem -- a dynamic programming approach
- Tolerance analysis for 0-1 knapsack problems
- Price of fairness for allocating a bounded resource
- A new exact approach for the 0-1 collapsing knapsack problem
- A constructive periodicity bound for the unbounded knapsack problem
- Special issue on knapsack problems and applications
- Where are the hard knapsack problems?
- A polynomial-time algorithm for the change-making problem
- Optimization algorithms for the disjunctively constrained knapsack problem
- Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study
- The knapsack problem with neighbour constraints
- The symmetric quadratic knapsack problem: approximation and scheduling applications
- One-level reformulation of the bilevel Knapsack problem using dynamic programming
- Maximum-weight stable sets and safe lower bounds for graph coloring
- An exact algorithm for bilevel 0-1 knapsack problems
- A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem
- Exact methods for three-dimensional cutting and packing: a comparative study concerning single container problems
- Approximation of knapsack problems with conflict and forcing graphs
- Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis
- Exact solution techniques for two-dimensional cutting and packing
- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- The binary knapsack problem with qualitative levels
- On the Stackelberg knapsack game
- An iterative dynamic programming approach for the temporal knapsack problem
- The knapsack problem with special neighbor constraints
- Approximation issues of fractional knapsack with penalties: a note
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Analysis of divide-and-conquer strategies for the \(0-1\) minimization knapsack problem
- An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
- Approximating the product knapsack problem
- A note on upper bounds to the robust knapsack problem with discrete scenarios
- A well-solvable special case of the bounded knapsack problem
- Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
- Bi-criteria path problem with minimum length and maximum survival probability
- Irregular packing problems: a review of mathematical models
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An FPTAS for the knapsack problem with parametric weights
- Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
- The \(k\)-subset sum problem over finite fields of characteristic 2
- Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem
- A Stackelberg knapsack game with weight control
- Improved approximation algorithms for a bilevel knapsack problem
- An FPTAS for the parametric knapsack problem
- Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
- A pegging approach to the precedence-constrained knapsack problem
- A cross entropy algorithm for the Knapsack problem with setups
- Sensitivity analysis of the Knapsack sharing problem: perturbation of the weight of an item
- New upper bounds and exact methods for the knapsack sharing problem
- Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering
- Approximation and online algorithms for multidimensional bin packing: a survey
- Primal-dual algorithms for precedence constrained covering problems
- A polynomial algorithm for a continuous bilevel knapsack problem
- On approximating the incremental knapsack problem
- Heuristic and exact algorithms for the max-min optimization of the multi-scenario knapsack problem
- An optimization algorithm for a penalized knapsack problem
- Algorithms for the bounded set-up knapsack problem
- An exact algorithm for the knapsack sharing problem
- On the complexity of the continuous unbounded knapsack problem with uncertain coefficients
- An efficient algorithm for the collapsing knapsack problem
- Towards strong duality in integer programming
- The linear multiple choice knapsack problem with equity constraints
- Sensitivity analysis of a greedy heuristic for knapsack problems
- Approximate and exact algorithms for the fixed-charge knapsack problem
- An algorithm for the disjunctively constrained knapsack problem
- A faster exact method for large-scale knapsack problems with setup costs and times
- Separation algorithms for 0-1 knapsack polytopes
- Integer knapsack problems with set-up weights
- The one dimensional Compartmentalised Knapsack problem: a case study
- Lifting the knapsack cover inequalities for the knapsack polytope
- Polynomial size IP formulations of knapsack may require exponentially large coefficients
- A faster algorithm for the continuous bilevel knapsack problem
- Cover by disjoint cliques cuts for the knapsack problem with conflicting items
- On inequalities with bounded coefficients and pitch for the min knapsack polytope
- The multiobjective multidimensional knapsack problem: a survey and a new approach
- Hybrid approaches for the two-scenario max-min knapsack problem
- An improved binary search algorithm for the Multiple-Choice Knapsack Problem
- The Unbounded Knapsack Problem
- The lexicographic α-robust knapsack problem
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
- The Knapsack Problem with Conflict Graphs
- Bilevel Knapsack with Interdiction Constraints
- A Study on the Computational Complexity of the Bilevel Knapsack Problem
- A reactive local search-based algorithm for the disjunctively constrained knapsack problem
- Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
- A survey of effective heuristics and their application to a variety of knapsack problems
- A virtual pegging approach to the max–min optimization of the bi-criteria knapsack problem
- Exact Algorithms For The Setup Knapsack Problem
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
- Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights
- Improved dynamic programming and approximation results for the knapsack problem with setups
- On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
- Minmax regret combinatorial optimization problems: an Algorithmic Perspective
- Faster Pseudopolynomial Time Algorithms for Subset Sum
- Space-Efficient Approximations for Subset Sum
- Reducibility among Combinatorial Problems
- Multivariable Branching: A 0-1 Knapsack Problem Case Study
- Interdiction Games and Monotonicity, with Application to Knapsack Problems
- A Fully Polynomial Approximation Scheme for a Knapsack Problem with a Minimum Filling Constraint
- Discrete-Variable Extremum Problems
- Letter to the Editor—Comment on Dantzig's Paper on Discrete Variable Extremum Problems
- On the Robust Knapsack Problem
- The Theory and Computation of Knapsack Functions
- The Generalized Assignment Problem and Extensions
- Computing and Combinatorics
- A Bibliographical Survey On Some Well-Known Non-Standard Knapsack Problems
- Bilevel programming and price setting problems
- Bilevel programming with knapsack constraints
- Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation
- A strong integer linear optimization model to the compartmentalized knapsack problem
- An integer linear optimization model to the compartmentalized knapsack problem
- A Survey of the Generalized Assignment Problem and Its Applications
