Empirical Performance Models (EPMs)

Bioinformatics, and Empirical & Theoretical Algorithmics Laboratory (ß-Lab)
Department of Computer Science
The University of British Columbia

Abstract

Empirical performance models can be used to predict the performance of algorithms on previously unseen input, including previously unseen problem instances, previously untested parameter settings, or both.

People

Frank Hutter, Research Group Lead (eq. Assistant Prof., University of Freiburg)
Lin Xu, Ph.D. candidate (UBC)
Holger Hoos, Professor (UBC)
Kevin Leyton-Brown, Associate Professor (UBC)

Papers

Our newest take on empirical performance models is described in our AIJ paper:
Frank Hutter, Lin Xu, Holger Hoos, Kevin Leyton-Brown: Algorithm Runtime Prediction: Methods and Evaluation [link to publication]
Here is the online appendix for that paper. An early version of this paper is also available on the arXiv preprint server.

Frank Hutter, Holger Hoos, and Kevin Leyton-Brown.
Identifying Key Algorithm Parameters and Instance Features using Forward Selection [pdf] [bib]

Data

Here is a zip file with the algorithm performance data underlying our AIJ submission. It includes the runtimes and features for our 35 benchmark distributions, as well as the runtime matrices for CPLEX and Spear.

Software

Here is a zip file with the Matlab code we used in our experiments. Note that this zip file does not include the source code for neural networks, approximate Gaussian processes, or SPORE-FoBa due to licensing restrictions.
The main file for experiments for the feature space is epm_experiments.m; the main file for experiments in the configuration space & the joint space is epm_matrix_experiments.m; see the README.TXT for their usage.

Here is our feature computation code for SAT, feature computation code for MIP, and feature computation code for TSP. If you use these features, please cite the AIJ paper above.
We also have a modified version of the SAT feature computation code, which only computes some quite cheap features, which we used to generate features for the Configurable SAT Solver Competition (CSSC). For TSP, you might also want to obtain the feature computation code of Smith-Miles and van Hemert.

Our submission to LION-7 extends the methodology of EPMs to perform forward selection for identifying key parameters and features. Here is the extended code; the data remains unchanged from above.

Please send any questions, concerns or comments to Frank Hutter