Frugal Algorithm Selection for Combinatorial Search
Journal of Artificial Intelligence Research · 23.07.2026 · 86
DOI: 10.1613/jair.1.21266 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 23.07.2026. Verfasst von Erdem Kus und 4 weiteren Autor:innen.
Abstract (Originalsprache)
Background
Algorithms to solve combinatorial search and optimisation problems typically exhibit complementary performance – on problem instances where one fails, another shines. Selecting the best algorithm for each problem instance, rather than relying on a single algorithm, is crucial for optimal performance. This is known as the Algorithm Selection Problem, which is usually solved by training Machine Learning models that predict the performance of available algorithms. However, the labelling cost, i.e., the cost of collecting the training data to build such models, can be extremely high, as it involves running algorithms on all training instances.
Objectives
Rather than following the traditional approach of exhaustively running all algorithms on all training instances to train algorithm selection models, we propose a more frugal approach using active learning to intelligently decide which algorithms to run on which problem instances, thus reducing the labelling cost to build algorithm selection systems.
Methods
We find that standard active learning strategies perform poorly in algorithm selection settings, where labelling costs are inherently non-uniform due to the highly variable runtimes of algorithms across problem instances. Therefore, we propose novel active learning strategies for algorithm selection that leverage a dynamic time limit mechanism, together with auxiliary models for predicting timeouts and algorithm runtimes, to decide which algorithm runs strike the best balance between cost and informativeness.
Results
The proposed active learning strategies significantly outperform traditional approaches in terms of frugality, achieving competitive performance at substantially lower labelling cost. Our results demonstrate that we can save up to 90% of the labelling cost associated with generating training data for algorithm selection models without loss in algorithm selection performance.
Conclusions
Our Frugal Algorithm Selection framework, which leverages a dynamic time limit mechanism, prediction uncertainty, and the auxiliary models for timeout and runtime prediction, can dramatically reduce labelling cost without compromising predictive performance. This allows the training of algorithm selection systems to be more efficient for combinatorial optimisation problems.
Zitieren
APA
Kus, E., Akgün, Ö., Dang, N., Miguel, I., & Kotthoff, L. (2026). Frugal Algorithm Selection for Combinatorial Search. Journal of Artificial Intelligence Research, 86. https://doi.org/10.1613/jair.1.21266
Vancouver
Kus E, Akgün Ö, Dang N, Miguel I, Kotthoff L. Frugal Algorithm Selection for Combinatorial Search. Journal of Artificial Intelligence Research. 2026;86. doi:10.1613/jair.1.21266
BibTeX
@article{Kus2026,
author = {Kus, Erdem and Akgün, Özgür and Dang, Nguyen and Miguel, Ian and Kotthoff, Lars},
title = {Frugal Algorithm Selection for Combinatorial Search},
journal = {Journal of Artificial Intelligence Research},
year = {2026},
volume = {86},
doi = {10.1613/jair.1.21266}
}
EUVIMED