A new class of hard problem instances for the 0-1 knapsack problem

DOI10.1016/j.ejor.2021.12.009zbMath1506.90226OpenAlexW4200462156MaRDI QIDQ2140267

Jorik Jooken, Pieter Leyman, Patrick de Causmaecker

Publication date: 20 May 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://lirias.kuleuven.be/handle/20.500.12942/687513

zbMATH Keywords

combinatorial optimization0-1 knapsack problemproblem instance hardness

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ 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

Uses Software

• Knapsack
• MATILDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards objective measures of algorithm performance across instance space
• Generating new test instances by evolving in instance space
• Algorithm runtime prediction: methods \& evaluation
• Yet harder knapsack problems
• A survey for the quadratic assignment problem
• Certification of an optimal TSP tour through 85,900 cities
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• A new fully polynomial time approximation scheme for the Knapsack problem
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• The TSP phase transition
• Approximation algorithms for knapsack problems with cardinality constraints
• Instance spaces for machine learning classification
• Measuring instance difficulty for combinatorial optimization problems
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Where are the hard knapsack problems?
• Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis
• The Quadratic Assignment Problem
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Knapsack Problem with Conflict Graphs
• A New Algorithm for the 0-1 Knapsack Problem
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Discrete-Variable Extremum Problems