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 (16)
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 ⋮ On a cube and subspace projections ⋮ Knapsack: connectedness, path, and shortest-path ⋮ 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 ⋮ Bi-dimensional assignment in 5G periodic scheduling ⋮ Expectation analysis for bounding solutions of the 0-1 knapsack problem ⋮ Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits
Uses Software
Cites Work
- 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
- 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
This page was built for publication: Knapsack problems -- an overview of recent advances. I: Single knapsack problems
