Features for the 0-1 knapsack problem based on inclusionwise maximal solutions

DOI10.1016/j.ejor.2023.04.023arXiv2211.09665OpenAlexW4366285839MaRDI QIDQ6168585

Jorik Jooken, Patrick de Causmaecker, Pieter Leyman

Publication date: 11 July 2023

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

Full work available at URL: https://arxiv.org/abs/2211.09665

zbMATH Keywords

combinatorial optimizationpacking0-1 knapsack probleminstance space analysisproblem instance hardness

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithm AS 136: A K-Means Clustering Algorithm
• 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
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• The TSP phase transition
• The multidimensional 0-1 knapsack problem: an overview.
• Unbounded knapsack problem: Dynamic programming revisited
• Instance spaces for machine learning classification
• Measuring instance difficulty for combinatorial optimization problems
• Where are the hard knapsack problems?
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• A new class of hard problem instances for the 0-1 knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Combinatorial Landscapes
• Efficiency of Local Search with Multiple Local Optima
• 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
• The Knapsack Problem with Conflict Graphs
• Performance Prediction and Preselection for Optimization and Heuristic Solution Procedures
• A New Algorithm for the 0-1 Knapsack Problem
• Hard Knapsack Problems
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A Minimal Algorithm for the Bounded Knapsack Problem
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Statistical analysis of local search landscapes
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Discrete-Variable Extremum Problems

This page was built for publication: Features for the 0-1 knapsack problem based on inclusionwise maximal solutions