Improving Performance of Algorithm Selection Pipelines on Large Instance Sets via Dynamic Reallocation of Budget

Special Issue PPSN 2024: Algorithm-selection (AS) methods are essential in order to obtain the best performance from a portfolio of solvers. When considering large sets of instances that either arrive in a stream or in a single batch, there is significant potential to save the function evaluation budget on some instances and reallocate it to others, thereby improving overall performance. We propose an AS pipeline which (1) identifies easy instances which are solved using the single best solver, avoiding the need to run a selector; (2) curtails runs on both easy and hard instances if they become stalled in the search space and/or are predicted to remain in a stalled state thereby saving budget; (3) reallocates budget saved from both previous steps to downstream instances, using an intelligent strategy to predict which instances will benefit most from extra function evaluations. Experiments using the BBOB dataset in two settings (batch and streaming) show that augmenting an AS pipeline with strategies to save and reallocate budget obtains significantly better results in both settings compared to a standard pipeline.