Simulated annealing is a well-established general purpose optimiser that is often used for simulation optimisation. Parallelising it is non-trivial, as the algorithm is inherently sequential. This paper revisits the idea of speculative computation, in which several iterations of simulated annealing are executed in parallel, each based on speculation on the outcome of the previous iterations, and backtracking if the speculation was wrong. The paper extends the idea to the case of stochastic problems, for which several replications of the simulation have to be run to obtain a reliable estimate of a solution’s quality. We show how to find optimal speculation policies via dynamic programming, and that the optimal policies can be different from those found with the typically used greedy heuristic. We also examine how the results depend on correctly estimating the acceptance probability. Empirical results demonstrate the speed-up that can be gained via speculative execution in different settings.

This paper proposes a simulated annealing variant for optimization problems in which the solution quality can only be estimated by sampling from a random distribution. The aim is to find the solution with the best expected performance, as, e.g., is typical for problems where solutions are evaluated using a stochastic simulation. Assuming Gaussian noise with known standard deviation, we derive a fully sequential sampling procedure and decision rule. The procedure starts with a single sample of the value of a proposed move to a neighboring solution and then continues to draw more samples until it is able to make a decision to accept or reject the move. Under constraints of equilibrium detailed balance at each draw, we find a decoupling between the acceptance criterion and the choice of the rejection criterion. We derive a universally optimal acceptance criterion in the sense of maximizing the acceptance probability per sample and thus the efficiency of the optimization process. We show that the choice of the move rejection criterion depends on expectations of possible alternative moves and propose a simple and practical (albeit more empirical) solution that preserves detailed balance. An empirical evaluation shows that the resulting approach is indeed more efficient than several previously proposed simulated annealing variants.