EUVIMEDEUVIMED entdecken
Crossref

Frugal Algorithm Selection for Combinatorial Search

Erdem Kus, Özgür Akgün, Nguyen Dang, Ian Miguel, Lars Kotthoff

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →