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