Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis

DOI10.1016/j.cor.2020.105184OpenAlexW3111603006MaRDI QIDQ2027074

Jeffrey Christiansen, Kate A. Smith-Miles, Mario Andrés Muñoz

Publication date: 21 May 2021

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

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

zbMATH Keywords

performance evaluationalgorithm portfoliosalgorithm selectioninstance difficulty0-1 knapsack probleminstance generationinstance space analysis

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items

A new class of hard problem instances for the 0-1 knapsack problem ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Instance space analysis and algorithm selection for the job shop scheduling problem ⋮ Features for the 0-1 knapsack problem based on inclusionwise maximal solutions ⋮ Relating instance hardness to classification performance in a dataset: a visual approach ⋮ Evolving test instances of the Hamiltonian completion problem ⋮ Statistical mechanics analysis of generalized multi-dimensional knapsack problems

Uses Software

• Knapsack
• SPOT
• GitHub
• outselect
• MATILDA
• InstanceSpace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• InstanceSpace
• Towards objective measures of algorithm performance across instance space
• Generating new test instances by evolving in instance space
• Matroidal relaxations for 0-1 knapsack problems
• Simple but efficient approaches for the collapsing knapsack problem
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• Instance spaces for machine learning classification
• Tolerance analysis for 0-1 knapsack problems
• Measuring instance difficulty for combinatorial optimization problems
• Where are the hard knapsack problems?
• Testing heuristics: We have it all wrong
• On normalization and algorithm selection for unsupervised outlier detection
• Core Problems in Knapsack Algorithms
• The Generation of Experimental Data for Computational Testing in Optimization
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
• Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
• A hard knapsack problem
• A New Algorithm for the 0-1 Knapsack Problem
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• Needed: An Empirical Science of Algorithms
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations