Journal article

Revisiting where are the hard knapsack problems? via Instance Space Analysis

Kate Smith-Miles, Jeffrey Christiansen, Mario Andres Munoz

Computers & Operations Research | PERGAMON-ELSEVIER SCIENCE LTD | Published : 2021

Abstract

In 2005, David Pisinger asked the question “where are the hard knapsack problems?”. Noting that the classical benchmark test instances were limited in difficulty due to their selected structure, he proposed a set of new test instances for the 0–1 knapsack problem with characteristics that made them more challenging for dynamic programming and branch-and-bound algorithms. This important work highlighted the influence of diversity in test instances to draw reliable conclusions about algorithm performance. In this paper, we revisit the question in light of recent methodological advances – in the form of Instance Space Analysis – enabling the strengths and weaknesses of algorithms to be visualis..

View full abstract

Grants

Awarded by Australian Research Council


Funding Acknowledgements

We are grateful to the two reviewers and editors for their valuable suggestions. Funding was provided by the Australian Research Council through grant FL140100012. The authors are grateful to Samuel Fairchild for his assistance with feature calculations, and Dr. Neelofar for her work on the development of the MATILDA online tool for Instance Space Analysis available at https://matilda.unimelb.edu.au