Understanding instance hardness for optimisation algorithms: Methodologies, open challenges and post-quantum implications

Abstract

This paper reviews efforts to characterise the hardness of optimisation problem instances, and to develop improved methodologies for empirical testing of the strengths and weaknesses of algorithms, based on comprehensive and unbiased sets of test instances whose hardness can be understood. Using the Travelling Salesperson Problem (TSP) as an illustrative example throughout the paper, efforts during the 20th century to solve optimisation problems with both exact and heuristic algorithms are briefly reviewed. From the early 21st century however, with a growing number of available algorithms (from nature-inspired to quantum), the focus has naturally shifted to exploring how the characteristics ..