Improving Performance of Algorithm Selection Pipelines on Large Instance Sets via Dynamic Reallocation of Budget
Quentin Renau & Emma Hart
What the paper says
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.
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.