Knapsack problems.
approximation algorithmsexact algorithmsheuristicsknapsack problemNP-completenessvariants and extensions
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)
The book starts with a basic introduction to the knapsack problem, the most frequently treated integer programming problem with a single constraint, where a subset of a certain number of items, each of them with its profit and weight, must be selected so that the total profit is maximized and the total weight remains below a certain capacity. It proceeds with a discussion about the basic techniques available for the solution to this problem, which makes it useful reading for undergraduate students of computer science, mathematics and economics. The remaining chapters give an overview of the generalizations of the problem as well as the advanced algorithms for its solution. The best currently available exact algorithms, both from the point of view of complexity and the running time, as well as the approximation algorithms and heuristics are presented for a number of variations of the knapsack problem. The generalizations of the problem are illustrated by some applications. This part of the book represents good reading for graduate students of computer science and mathematics, but also for a reader willing to go into more depth of the problem. At the end of the book, the authors provide a short presentation of the NP-completeness of the knapsack problem. In conclusion, it could be said that the book is a valuable source for students, but also for researchers interested in this problem.
- scientific article; zbMATH DE number 1302173
- scientific article; zbMATH DE number 44282
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Exact methods for the knapsack problem and its generalizations
- An exact algorithm for the fixed-charge multiple knapsack problem
- A hybrid algorithm for the unbounded knapsack problem
- Bidimensional packing by bilinear programming
- Heuristics for the variable sized bin-packing problem
- Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
- A successive approximation algorithm for the multiple knapsack problem
- Approximation algorithms for orthogonal packing problems for hypercubes
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition
- Strips minimization in two-dimensional cutting stock of circular items
- Operator non-availability periods
- Knapsack problems with setups
- Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval
- An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem
- Heuristics for the 0-1 multidimensional knapsack problem
- Heuristics for container loading of furniture
- Inverse 1-center location problems with edge length augmentation on trees
- Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core
- Modified subset sum heuristics for bin packing
- An evolutionary strategy based on partial imitation for solving optimization problems
- Dual mean field search for large scale linear and quadratic knapsack problems
- Integer optimization with penalized fractional values: the knapsack case
- Subset sum problems with digraph constraints
- Exact algorithms for the minimum cost vertex blocker clique problem
- New exact approaches and approximation results for the penalized knapsack problem
- Dantzig-Wolfe decomposition approach to the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network
- Online algorithms with advice for the dual bin packing problem
- Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
- Bi-dimensional knapsack problems with one soft constraint
- Generic Pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign
- An exact approach for the 0-1 knapsack problem with setups
- A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem
- A low-space algorithm for the subset-sum problem on GPU
- Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem
- A relax-and-cut framework for large-scale maximum weight connected subgraph problems
- Exact approaches for the knapsack problem with setups
- Relaxations and heuristics for the multiple non-linear separable knapsack problem
- A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
- On the product knapsack problem
- Confidence intervals for linear unbiased estimators under constrained dependence
- The complexity of probabilistic lobbying
- Scheduling jobs with maintenance subject to load-dependent duration on a single machine
- Solving the multiscenario max-MIN knapsack problem exactly with column generation and branch-and-bound
- Online knapsack with resource augmentation
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- Knapsack with variable weights satisfying linear constraints
- Knapsack
- Approximating the 3-period incremental knapsack problem
- An improved balanced algorithm for the subset-sum problem
- Quantum-inspired wolf pack algorithm to solve the 0-1 knapsack problem
- Bridging \(k\)-sum and CVaR optimization in MILP
- Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
- Capacitated assortment and price optimization for customers with disjoint consideration sets
- Lifting of probabilistic cover inequalities
- A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
- Generating constrained length personalized bicycle tours
- Computational experiment of critical event tabu search for the general integer multidimensional knapsack problem
- A review of operations research models in invasive species management: state of the art, challenges, and future directions
- Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks
- An empirical analysis of exact algorithms for the unbounded knapsack problem
- A universally-truthful approximation scheme for multi-unit auctions
- Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
- Adaptive refinement strategies for the simulation of gas flow in networks using a model hierarchy
- On the best choice of a branching variable in the subset sum problem
- Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
- Supermodular covering knapsack polytope
- The multi-band robust knapsack problem -- a dynamic programming approach
- The packing while traveling problem
- Tolerance analysis for 0-1 knapsack problems
- Optimizing invasive species management: a mixed-integer linear programming approach
- Price of fairness for allocating a bounded resource
- A new exact approach for the 0-1 collapsing knapsack problem
- Binary decision diagrams for generating and storing non-dominated project portfolios with interval-valued project scores
- Multi-objective branch and bound
- A branch-and-bound based heuristic algorithm for convex multi-objective MINLPs
- A population-based fast algorithm for a billion-dimensional resource allocation problem with integer variables
- Impact of deadline intervals on behavior of solutions to the random sequencing jobs with deadlines problem
- Mathematical models and decomposition methods for the multiple knapsack problem
- Algorithms for communication scheduling in data gathering network with data compression
- Minimum-cost b-edge dominating sets on trees
- A constructive periodicity bound for the unbounded knapsack problem
- Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method
- Efficient algorithms for real-life instances of the variable size bin packing problem
- Special issue on knapsack problems and applications
- Problem reduction heuristic for the 0-1 multidimensional knapsack problem
- Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem
- Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem
- Solving knapsack problems on GPU
- Greedy algorithms for a class of knapsack problems with binary weights
- Shift-and-merge technique for the DP solution of the time-constrained backpacker problem
- Variable neighbourhood search for the variable sized bin packing problem
- Where are the hard knapsack problems?
- Two dimensional load balancing
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- On speed scaling via integer programming
- Sensitivity analysis to perturbations of the weight of a subset of items: the knapsack case study
- Computing knapsack solutions with cardinality robustness
- Multilevel, threshold-based policies for cargo container security screening systems
- A constraint programming approach for a batch processing problem with non-identical job sizes
- A diversified tabu search approach for the open-pit mine production scheduling problem with metal uncertainty
This page was built for publication: Knapsack problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4821303)
