A Review on Single-Problem Multi-Attempt Heuristic Optimization
This work addresses a practical gap for practitioners in optimization who need to allocate computational resources effectively for single-problem scenarios, but it is incremental as it synthesizes and organizes existing methods rather than introducing new ones.
The paper tackles the problem of efficiently selecting sequential heuristic alternatives for optimizing a single problem with multiple attempts, by reviewing and unifying existing strategies from algorithm selection, parameter tuning, multi-start, and resource allocation into a common framework and taxonomy.
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. The sequential selection of which alternative to try next is crucial for efficiently identifying the one that provides the best possible solution across multiple attempts. Despite the relevance of this problem in practice, it has not yet been the exclusive focus of any existing review. Several sequential alternative selection strategies have been proposed in different research topics, but they have not been comprehensively and systematically unified under a common perspective. This work presents a focused review of single-problem multi-attempt heuristic optimization. It brings together suitable strategies to this problem that have been studied separately through algorithm selection, parameter tuning, multi-start and resource allocation. These strategies are explained using a unified terminology within a common framework, which supports the development of a taxonomy for systematically organizing and classifying them.