firstname.lastname@example.org | www.cs.ubc.ca/~hutter/
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.
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
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
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