Efficient Online Automated Algorithm Selection in the Face of Data-Drift in Optimisation Problem Instances

In many real-world problems, instances arrive in a stream which is likely to experience drift in the instance space over time. If a classical algorithm selector is trained offline, i.e., on an initial part of the instance stream, downstream performance is often negatively impacted due to drift in the instance data. To overcome this limitation of classical algorithm selectors, we propose a novel online automated algorithm selection framework that first uses instance features to detect drift, and then periodically retrains a selector if drift occurs, ensuring continuity of performance in face of data-drift. To further improve both the effectiveness and efficiency of retraining, we also propose a process to continuously gather new training samples on the fly. Empirical comparison using a bin-packing scenario under three different drift scenarios shows that our framework is efficient in terms of the computational effort required to train a selector while maintaining good performance with respect to accuracy compared to several baselines.