Empirical Scaling Analyzer (ESA)

Introduction

Empirical Scaling Analyzer (ESA) is a tool that takes a file of solver runtimes (sample) as input, automatically fits and evaluates parametric models, and generate a PDF report for the analysis results (sample). The models are fitted using standard numerical methods, and are challenged by extrapolation using a bootstrap approach. For detailed information about the methodology, please refer to the papers below.

Upload your runtime file below to give it a try!

The On-line Tool

Runtime file:

Models to fit: exponential: a*b^n
square-root exponential: a*b^sqrt(n)
polynomial: a*n^b

Algorithm name:

Instance name:

# support sizes: A value of 0 instructs ESA to use ~60% of the data as support

# bootstrap samples:

Statistic:

For the default settings and the sample runtime file, ESA should complete within 10 minutes. The time required is roughly linear in the number of bootstrap samples, and the time required to fit the models is the most important factor affecting ESA's processing time.

Papers

Z. Mu and H. H. Hoos. Empirical Scaling Analyser: an automated system for empirical analysis of performance scaling. GECCO Companion, 2015. (PDF_File, Poster)
Z. Mu and H. H. Hoos. On the empirical time complexity of random 3-SAT at the phase transition. IJCAI, 2015. (PDF_File, Slides, Poster)
H. H. Hoos and T. Stützle. On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem. European Journal of Operational Research, 238(1):87-94, 2014. (PDF_File)
H. H. Hoos. A bootstrap approach to analysing the scaling of empirical run-time data with problem size. Technical report, Technical Report TR-2009-16, University of British Columbia, 2009. (PDF_File)