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 generates a PDF report for the analysis results (sample). The models are fitted to a fraction of the dataset with the smallest problem instance sizes, and are challenged by extrapolation using a bootstrap approach. For detailed information about the methodology, please refer to the papers below.

People

Running ESA

What Version Should I Use?

ESA v1 [Pushak et. al., 2020] requires that your running time dataset must be grouped into bins, where each bin contains problem instances of exactly the same size. If you cannot obtain instances in this way, you should always prefer ESA v2 [Pushak & Hoos, 2020].

If your dataset does have instances grouped into bins of the same size, then you may choose either version -- both tend produce qualitatively similar results. However, the method that each procedure uses to fit models to your dataset varies. While both methods typically produce models with quite similar training error, ESA v1 implicitly weights the larger running times more heavily than ESA v2. If you prefer to weight the larger instance sizes more heavily (e.g., because you believe the smaller instance sizes are contaminated by lower order terms or floor effects), we believe it is more principled to use a custom weighting scheme with ESA v2.

By far, the biggest difference between the performance of the two methods is the running time required by the procedures to fit the empirical performance scaling models to your running time datasets. Fitting models is cubic in the number of data points. Since ESA v2 fits directly to the full training set, whereas ESA v1 fits only to a small number of statistics of the training set, this means that ESA v2 requires substantially more time for large datasets. For 11 000 instances, ESA v2 requires a little over a full day to perform its analysis, whereas ESA v1 runs in a few minutes. For this reason, we only provide ESA v1 as an online service -- ESA v2 must be run from the command line. However, for datasets with hundreds of problem instances, ESA v2 should still complete its analysis within seconds or minutes.

Papers

Applications