Stress-testing Algorithms, Solvers, and Models via Instance Space Analysis

Our society is critically dependent on reliable algorithms, especially optimisation algorithms to support complex decision making, but establishing trust is a growing concern. How do we know that our algorithmic choices – whether it be a heuristic or exact solver, or a model, or parameter configurations  – are reliable in practice? This vexing issue relies on testing algorithms with enough unbiased test instances to gain insights into strengths and weaknesses under various conditions. This talk will provide a brief introduction to Instance Space Analysis as a methodology that provides a mathematically rigorous foundation for “stress-testing” algorithms. ISA exposes the strengths and weaknesses of algorithms and supports the generation of rich and diverse test problems to understand algorithm reliability under a variety of conditions. The methodology has been made available via an online tool (matilda.unimelb.edu.au) that has been adopted worldwide by researchers in many fields, and is supporting industry partners keen to avoid disasters when deploying critical algorithms. The webinar will use several case studies from timetabling and bin packing to highlight how insights into performance of heuristics, MIP models or solvers can be obtained by generating and testing diverse instances with ISA.