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.

Back to the LCI Forum page