Active learning to optimise time-expensive algorithm selection
This work addresses algorithm selection for time-expensive problems, providing a practical incremental improvement for researchers and practitioners in optimization.
The paper tackles the problem of selecting the best algorithm for hard optimization problems like Boolean Satisfiability, where running all solvers to create labeled data is time-expensive, and develops an active learning framework that achieves equal or higher performance with less training data.
Hard optimisation problems such as Boolean Satisfiability typically have long solving times and can usually be solved by many algorithms, although the performance can vary widely in practice. Research has shown that no single algorithm outperforms all the others; thus, it is crucial to select the best algorithm for a given problem. Supervised machine learning models can accurately predict which solver is best for a given problem, but they require first to run every solver in the portfolio for all examples available to create labelled data. As this approach cannot scale, we developed an active learning framework that addresses this problem by constructing an optimal training set, so that the learner can achieve higher or equal performances with less training data. Our work proves that active learning is beneficial for algorithm selection techniques and provides practical guidance to incorporate into existing systems.