A Review on Single-Problem Multi-Attempt Heuristic Optimization

In certain real-world optimization scenarios, practitioners are not interested in solving multiple problems but rather in finding the best solution to a single, specific problem. When the computational budget is large relative to the cost of evaluating a candidate solution, multiple heuristic alternatives can be tried to solve the same given problem, each possibly with a different algorithm, parameter configuration, initialization, or stopping criterion. In this practically relevant setting, the sequential selection of which alternative to try next is crucial for efficiently identifying the best possible solution across multiple attempts. However, suitable sequential alternative selection strategies have traditionally been studied separately across different research topics and have not been the exclusive focus of any existing review. As a result, the state-of-the-art remains fragmented for practitioners interested in this setting, with surveys either covering only subsets of relevant strategies or including approaches that rely on assumptions that are not feasible for the single-problem case. This work addresses the identified gap by providing a focused review of single-problem multi-attempt heuristic optimization. It brings together suitable strategies for this setting that have been studied separately through algorithm selection, parameter tuning, multi-start, and resource allocation. These strategies are described using a unified terminology within a common framework, which supports the construction of a taxonomy for systematically organizing and classifying them. The resulting comprehensive review facilitates both the identification and the development of strategies for the single-problem multi-attempt setting in practice.