A Feature-Free Approach to Automated Algorithm Selection

This article summarises recent work in the domain of feature-free algorithm selection that was published in the Journal of Heuristics in January 2023, with the title 'Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches'. Specifically, we consider domains in which there is implicit sequential information encapsulated in the data, e.g., in online bin-packing. We train two types of recurrent neural networks (RNN) to predict a packing heuristic in online bin-packing that use the sequence of item-sizes as input, i.e. no features are derived to describe the instance. This contrasts to typical approaches to algorithm-selection. The RNN approaches are shown to be capable of achieving within 5% of the oracle performance on between 80.88 and 97.63% of the instances, depending on the dataset. They are also shown to outperform classical machine learning models trained using derived features. In order to explain the observed result, we suggest that our methods perform well when the instances exhibit some implicit structure. To provide evidence for this, 14 new datasets with controllable levels of structure are generated, indicating that a critical threshold of structure is required before algorithm-selection delivers benefit.