  We combine the fields of heuristic optimization and optimal stopping. We
propose a strategy for benchmarking randomized optimization algorithms that
minimizes the expected total cost for obtaining a good solution with an optimal
number of calls to the solver. To do so, rather than letting the objective
function alone define a cost to be minimized, we introduce a further
cost-per-call of the algorithm. We show that this problem can be formulated
using optimal stopping theory. The expected cost is a flexible figure of merit
for benchmarking probabilistic solvers that can be computed when the optimal
solution is not known, and that avoids the biases and arbitrariness that affect
other measures. The optimal stopping formulation of benchmarking directly leads
to a real-time, optimal-utilization strategy for probabilistic optimizers with
practical impact. We apply our formulation to benchmark simulated annealing on
a class of MAX2SAT problems. We also compare the performance of a D-Wave 2X
quantum annealer to the HFS solver, a specialized classical heuristic algorithm
designed for low tree-width graphs. On a set of frustrated-loop instances with
planted solutions defined on up to N = 1098 variables, the D-Wave device is two
orders of magnitude faster than the HFS solver, and, modulo known caveats
related to suboptimal annealing times, exhibits identical scaling with problem
size.
