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

DOI10.1016/J.EJOR.2021.12.009zbMATH Open1506.90226OpenAlexW4200462156MaRDI QIDQ2140267FDOQ2140267

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

Recommendations

• Where are the hard knapsack problems?
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• A hard knapsack problem
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• New trends in exact algorithms for the \(0-1\) knapsack problem

zbMATH Keywords

combinatorial optimization0-1 knapsack problemproblem instance hardness

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Instance space analysis for 2D bin packing mathematical models
• Title not available (Why is that?)
• 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
• Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
• Expectation analysis for bounding solutions of the 0-1 knapsack problem
• A practical approach for dealing with hard knapsack problems using general-purpose integer programming software

Uses Software

• Knapsack
• MATILDA

This page was built for publication: A new class of hard problem instances for the 0-1 knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2140267)