ABSTRACT
Heuristic algorithms are often difficult to analyse theoretically; this holds in particular for advanced, randomised algorithms that perform well in practice, such as high-performance stochastic local search (SLS) procedures (also known as metaheuristics). Furthermore, for various reasons, the practical applicability of the theoretical results that can be achieved is often very limited. Many computational problems take the form of decision problems, in which solutions are characterised by a set of logical conditions. A decision algorithm is an algorithm that takes as an input an instance of a given decision problem and determines whether the instance is soluble, that is, whether it has a solution. In most cases, if a solution is found, that solution is also returned by the algorithm. The primary performance metric for complete (and correct) decision algorithms is typically run-time, that is, the time required for solving a given problem instance. Typically, the behaviour of heuristic algorithms is analysed on a set or ensemble of instances.
