Statistical Regimes and Runtime Prediction
Publication Type:
Refereed Conference Meeting Proceeding
Abstract:
The last decade has seen a growing interest in solver portfolios, automated
solver configuration, and runtime prediction methods. At their core, these
methods rely on a deterministic, consistent behaviour from the underlying
algorithms and solvers. However, modern state-of-the-art solvers have elements
of stochasticity built in such as randomised variable and value selection,
tie-breaking, and randomised restarting. Such features can elicit dramatic
variations in the overall performance between repeated runs of the solver,
often by several orders of magnitude. Despite the success of the aforementioned
fields, such performance variations in the underlying solvers have largely been
ignored.
Supported by a large-scale empirical study employing many years of industrial
SAT Competition instances including repeated runs, we present statistical and
empirical evidence that such a performance variation phenomenon necessitates a
change in the evaluation of portfolio, runtime prediction, and automated
configuration methods. In addition, we demonstrate that this phenomenon can have
a significant impact on empirical solver competitions. Specifically, we show
that the top three solvers from the 2014 SAT Competition could have been ranked in
any permutation. These findings demonstrate the need for more statistically
well-founded regimes in empirical evaluations.
Conference Name:
International Joint Conference on Artificial Intelligence
Proceedings:
Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015
Digital Object Identifer (DOI):
10.XXX
Publication Date:
25/07/2015
Conference Location:
Argentina
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
Yes
Publication document: