Computer-Aided Algorithm Design: Automated Tuning, Configuration, Selection, and Beyond

Abstract

In this talk, I will introduce computer-aided algorithm design and discuss its main ingredients: design patterns, which provide ways of structuring potentially large spaces of candidate algorithms, and meta-algorithmic optimisation procedures, which are used for finding good designs within these spaces. After explaining how this algorithm design approach differs from and complements related approaches in program synthesis, genetic programming and so-called hyperheuristics, I will illustrate its success using examples from our own work in SAT-based software verification (Hutter et al. 2007), timetabling (Chiarandini, Fawcett, and Hoos 2008) and mixed integer programming (Hutter, Hoos, and Leyton-Brown 2010). Furthermore, I will argue why this approach can be expected to be particularly useful and effective for building better solvers for rich and diverse classes of combinatorial problems, such as planning and scheduling. Finally, I will outline out how programming by optimisation — a design paradigm that emphasises the automated construction of performance-optimised algorithm by means of searching large spaces of alternative designs — has the potential to transform the design of high-performance algorithm from a craft that is based primarily on experience and intuition into a principled and highly effective engineering effort.