CAIAC

Frank was the recipient of the 2010 CAIAC Best Dissertation Award. Below is the abstract from his thesis Automated Configuration of Algorithms for Solving Hard Computational Problems, completed in October 2009 at the Computer Science Department of the University of British Columbia under the supervision of Holger Hoos and co-supervision of Kevin Leyton-Brown and Kevin Murphy. You may also download pdf copies of his full thesis and slides from his presentation at the AI 2010 Graduate Student Symposium.

Thesis Abstract

The best-performing algorithms for many hard computational problems are highly parameterized. Selecting the best heuristics and tuning their parameters is often a diffcult, tedious, and unsatisfying task. This thesis studies the automation of this important part of algorithm design: the configuration of discrete algorithm components and their continuous parameters to construct an algorithm with desirable empirical performance characteristics.

Automated configuration procedures can facilitate algorithm development and can also be applied by end users to optimize performance for new instance types. The use of such procedures separates high-level cognitive tasks carried out by humans from tedious low-level tasks that machines can carry out better and cheaper.

We introduce two alternative algorithm configuration frameworks: iterated local search in parameter configuration space and sequential optimization based on response surface models. Our local search approach is the first to handle the many degress of freedom typical of state-of-the-art algorithms for solving hard computational problems in AI, such as the propositional satisfiability problem (SAT). Our model-based approach is the first to predict an algorithm's performance for unseen parameter configurations and instances. Based on random forests and approximate Gaussian process models, it significantly outperforms previous model-based techniques and extends them in ways crucial for general algorithm configuration: it handles categorical parameters, multiple instances, and tens of thousands of data points.

Using our procedures-to the best of our knowledge still the only ones applicable to these complex configuration tasks-we configured state-of-the-art tree search and local search algorithms for SAT, thereby substantially improving the state of the art for a broad range of problems. For example, we achieved a 100- fold speedup for certain types of SAT-encoded software verification instances. We also configured CPLEX, the most widely-used commercial optimization tool for solving mixed integer programs (MIP). Our general approach sped up CPLEX for a broad range of problems (up to 50-fold for instances from computational sustainability), clearly outperforming the special-purpose CPLEX tuning tool.

Based on these results, we believe that general automated algorithm configuration procedures, such as ours, will play an increasingly crucial role in the design of high-performance algorithms and will be widely used in academia and industry.