Parameter Setting Based on Performance Prediction: Towards an Instance-Aware Problem Solver
by Frank Hutter
The performance of stochastic local search algorithms often critically depends on fine-tuned parameters. While default parameter settings sometimes perform well across problem domains, much higher performance can often be achieved by varying the parameter settings on an instance-by-instance base.
In this talk, I show how runtime prediction can be utilised to automatically
set the continuous parameters of a local search algorithm for SAT on an
instance-by-instance base. Based on sequential Bayesian learning, our solver
learns about the types of problems it faces in practice (even if they are
unknown at development time) and, even more importantly, knows the uncertainty
associated with its predictions. This feature enables it to give reliable
estimates of runtime for instances similar to previous ones and to quantify its
incompetence for instances from entirely new problem domains.
This is joint work with Youssef Hamadi at Microsoft Research Cambridge.