Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis
From MaRDI portal
Publication:2027074
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
performance evaluationalgorithm portfoliosalgorithm selectioninstance difficulty0-1 knapsack probleminstance generationinstance space analysis
Related Items (8)
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
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
This page was built for publication: Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis