Structured Procrastination with Confidence
This is an implementation of Structured Procrastination with Confidence, an algorithm configuration procedure described in the paper Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration.
Algorithm configuration methods optimize the performance of a parameterized heuristic algorithm on a given distribution of problem instances. Recent work introduced an algorithm configuration procedure ("Structured Procrastination") that provably achieves near optimal performance with high probability and with nearly minimal runtime in the worst case. It also offers an anytime property: it keeps tightening its optimality guarantees the longer it is run. Unfortunately, Structured Procrastination is not adaptive to characteristics of the parameterized algorithm: it treats every input like the worst case. Follow-up work ("LeapsAndBounds") achieves adaptivity but trades away the anytime property. This paper introduces a new algorithm, "Structured Procrastination with Confidence", that preserves the near-optimality and anytime properties of Structured Procrastination while adding adaptivity. In particular, the new algorithm will perform dramatically faster in settings where many algorithm configurations perform poorly. We show empirically both that such settings arise frequently in practice and that the anytime property is useful for finding good configurations quickly.
Python 2.7, pickle (for saving results), matplotlib (for generating plots).
The saved runtimes, simulated environment, and general experimental framework are all taken from this repo, which is an implementation of LeapsAndBounds, another algorithm configuration procedure (see also CapsAndRuns, a followup work).
Running the Code
Download the repo and unzip the data (
measurements.dump) into the root folder. There are three configuration procedures to be run:
leapsandbounds. They are run by calling
at the command line. For example, calling
will run the structured procrastination procedure.
To produce the main plot (Figure 2 from the paper) call
Runtime Variation in Practice
To produce the plots demonstrating runtime variation in practice call
Note that this requires Python 3.6.