Tutorial: Instance Space Analysis for Rigorous and Insightful Algorithm Testing

Algorithm testing often consists of reporting on-average performance across a suite of well-studied benchmark instances. Therefore, the conclusions drawn from testing depend on the choice of benchmarks. Hence, test suites should be unbiased, challenging, and contain a mix of synthetic and real-world-like instances with diverse structure. Without diversity, the conclusions drawn future expected algorithm performance are necessarily limited. Moreover, on-average performance often disguises the strengths and weaknesses of an algorithm for particular types of instances. In other words, the standard benchmarking approach has two limitations that affect the conclusions: (a) there is no mechanism to assess whether the selected test instances are unbiased and diverse enough; and (b) there is little opportunity to gain insights into the strengths and weaknesses of algorithms, when hidden by on-average performance metrics. This tutorial introduces Instance Space Analysis (ISA), a visual methodology for algorithm evaluation that reveals the relationships between the structure of an instance and its impact on performance. ISA offers an opportunity to gain more nuanced insights into algorithm strengths and weaknesses for various types of test instances, and to objectively assess the relative power of algorithms, unbiased by the choice of test instances. A space is constructed whereby an instance is represented a point in a 2d plane, with algorithm footprints being the regions of predicted good performance of an algorithm, based on statistical evidence. From this broad instance space, we can assess the diversity of a chosen test set. Moreover, through ISA we can identify regions where additional test instances would be valuable to support greater insights. By generating new instances with controllable properties, an algorithm can be �stress-tested� under all possible conditions. The tutorial makes use of the on-line tools available at the Melbourne Algorithm Test Instance Library with Data Analytics (MATILDA) and provides access to its MATLAB computational engine. MATILDA also provides a collection of ISA results and other meta-data available for downloading for several well-studied problems from optimization and machine learning, from previously published studies.