Frugal algorithm selection : cost-aware active learning for efficient training data collection in algorithm selection

Algorithms for combinatorial optimisation problems exhibit complementary strengths: an algorithm that performs well on one problem instance may perform poorly on another. The Algorithm Selection Problem addresses this challenge by selecting the most suitable algorithm for each instance. Machine learning approaches have achieved strong performance in algorithm selection by learning predictive models from historical performance data. However, constructing such training data is computationally expensive, as it requires executing every candidate algorithm on every training instance. Active learning offers a principled approach for reducing this expense by selecting only the most informative algorithm--instance runs for evaluation. However, conventional active learning methods assume uniform labelling cost, an assumption that does not hold in algorithm selection, where evaluation costs can vary from milliseconds to timeout executions. This thesis introduces Frugal Algorithm Selection (FAS), a cost-aware active learning framework with two components. The first component, comprising the frugality mechanisms timeout prediction and dynamic time limits, reduces unnecessary cost during labelling. The second component, cost-aware selection strategies, integrates informativeness, predicted cost, and the estimated penalty of incorrect selection through lexicographic and Pareto-based criteria. The thesis further investigates how alternative learning formulations and query granularities affect frugality, comparing pairwise classification with multi-class classification, pairwise regression, and single-algorithm regression. The framework is evaluated on 24 benchmark scenarios spanning main, challenging algorithm selection benchmarks, and synthetic settings. Results demonstrate that Frugal Algorithm Selection reduces labelling cost by between 80% and 97% on standard benchmark scenarios while maintaining competitive algorithm selection performance. The experimental analysis further reveals that learning formulation plays a significant role under limited budgets: multi-class classification, despite weaker performance under exhaustive training, becomes competitive in low-budget settings. These findings demonstrate that effective Frugal Algorithm Selection depends not only on selection strategy, but also on the choice of learning formulation and the associated query granularity.