Where are the hard knapsack problems?

DOI10.1016/j.cor.2004.03.002zbMath1116.90089OpenAlexW2127172809WikidataQ58826454 ScholiaQ58826454MaRDI QIDQ1772862

Publication date: 21 April 2005

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2004.03.002

zbMATH Keywords

Dynamic programming Knapsack problem Branch-and-bound Test instances

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (65)

Implicit cover inequalities ⋮ A New Lagrangian Based Branch and Bound Algorithm for the 0-1 Knapsack Problem ⋮ An exact algorithm for large knapsack sharing problems ⋮ Dual mean field search for large scale linear and quadratic knapsack problems ⋮ Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time ⋮ On a resource-constrained scheduling problem with application to distributed systems reconfiguration ⋮ Integer optimization with penalized fractional values: the knapsack case ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Network meta-analysis: a statistical physics perspective ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Exact algorithms for the 0-1 time-bomb knapsack problem ⋮ Matheuristics for the flowshop scheduling problem with controllable processing times and limited resource consumption to minimize total tardiness ⋮ An efficient algorithm for capacitated assortment planning with stochastic demand and substitution ⋮ Decomposition approaches for recoverable robust optimization problems ⋮ Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic ⋮ Smallest covering regions and highest density regions for discrete distributions ⋮ Exact solution of the robust knapsack problem ⋮ Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem ⋮ Multivariable Branching: A 0-1 Knapsack Problem Case Study ⋮ Generalized Restless Bandits and the Knapsack Problem for Perishable Inventories ⋮ Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems ⋮ Balance in resource allocation problems: a changing reference approach ⋮ Using 3D-printing in disaster response: the two-stage stochastic 3D-printing knapsack problem ⋮ Analysis of divide-and-conquer strategies for the \(0-1\) minimization knapsack problem ⋮ A novel reformulation for the single-sink fixed-charge transportation problem ⋮ An improved binary quantum-behaved particle swarm optimization algorithm for knapsack problems ⋮ Bounds on the objective value of feasible roundings ⋮ Branch \& Learn with Post-hoc correction for Predict+Optimize with unknown parameters in constraints ⋮ A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints ⋮ Computing Optimized Path Integrals for Knapsack Feasibility ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Resource management in device-to-device communications ⋮ A branch and bound algorithm for robust binary optimization with budget uncertainty ⋮ Dynamic programming based algorithms for the discounted \(\{0-1\}\) knapsack problem ⋮ A multi-period renewal equipment problem ⋮ A hybrid quantum inspired harmony search algorithm for 0-1 optimization problems ⋮ A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem ⋮ Using dual feasible functions to construct fast lower bounds for routing and location problems ⋮ The multi-band robust knapsack problem -- a dynamic programming approach ⋮ Complexity results and exact algorithms for robust knapsack problems ⋮ Evolution of new algorithms for the binary knapsack problem ⋮ An incomplete \(m\)-exchange algorithm for solving the large-scale multi-scenario knapsack problem ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ A branch-and-bound algorithm for hard multiple knapsack problems ⋮ Generating hard instances for robust combinatorial optimization ⋮ Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis ⋮ Orbital shrinking: theory and applications ⋮ Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation ⋮ Hard multidimensional multiple choice knapsack problems, an empirical study ⋮ The multi-Handler knapsack problem under uncertainty ⋮ Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search ⋮ Towards a new strategy for solving fuzzy optimization problems ⋮ Stationary probability density of stochastic search processes in global optimization ⋮ Minimizing the weighted number of tardy jobs on a single machine: strongly correlated instances ⋮ Formulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problem ⋮ Reinforcement learning for the knapsack problem ⋮ Constrained Multiagent Markov Decision Processes: a Taxonomy of Problems and Algorithms ⋮ Hard combinatorial problems and minor embeddings on lattice graphs ⋮ Time-Constrained Restless Bandits and the Knapsack Problem for Perishable Items (Extended Abstract) ⋮ Evolving test instances of the Hamiltonian completion problem ⋮ Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems ⋮ Statistical mechanics analysis of generalized multi-dimensional knapsack problems

Uses Software

Knapsack

Cites Work

This page was built for publication: Where are the hard knapsack problems?