TL;DR
This paper introduces sunny-as2, an improved algorithm selection (AS) system that enhances the original SUNNY approach by incorporating wrapper-based feature selection and optimizing neighborhood size. sunny-as2 demonstrates competitive performance against state-of-the-art AS methods, offering a more robust and efficient way to choose the best solver for a given problem instance.
What Problem Does This Paper Address?
In many computational tasks, a single algorithm might not be the best choice for all problem instances. Instead, a "portfolio" of different algorithms (solvers) can be used, and the challenge lies in selecting the most appropriate solver for a specific, unseen problem instance. This is known as per-instance Algorithm Selection (AS). The SUNNY approach tackled this by identifying similar past instances (neighbors) and choosing solvers based on their performance on those neighbors. However, the original SUNNY had limitations in generalizing to diverse problem domains and could be computationally expensive. This paper addresses these limitations by proposing sunny-as2, an enhanced version designed for generic AS scenarios, aiming for better performance, robustness, and efficiency.
Methods
sunny-as2 builds upon the SUNNY framework with several key enhancements:
- Wrapper-Based Feature Selection: Instead of relying on pre-defined features,
sunny-as2actively learns which features are most informative for selecting solvers. This is done using a wrapper-based approach, where feature subsets are evaluated based on their impact on performance. - Neighborhood Size Configuration: The original SUNNY used a fixed heuristic for determining the number of nearest neighbors (
k).sunny-as2co-learns the optimalkvalue alongside the features, allowing for a more tailored approach to each AS scenario. - Greedy Solver Selection (greedy-SUNNY): To speed up the training phase,
sunny-as2employs a "greedy-SUNNY" variant. This approach iteratively adds solvers to a portfolio, prioritizing those that solve the most instances in a neighborhood, making the training process more efficient without significantly sacrificing performance. - Integrated Learning: The paper presents
sunny-as2-fkas a flavor that jointly learns both the optimal feature subset and the neighborhood sizek. This integrated approach aims to capture complex interactions between features and neighborhood selection.
Datasets
The experiments were conducted using scenarios from the ASlib (Algorithm Selection library) benchmark. The paper mentions using 12 ASlib scenarios for evaluating sunny-as2 against sunny-as and other approaches. Additionally, Table 3 refers to instances from the 2017 AS competition.
Key Insights and Ideas
- The Power of Co-Learning: Jointly learning the feature subset and the neighborhood size (
k) is more effective than optimizing them independently. This suggests that the optimal set of features and the relevant neighborhood size are interdependent. - Greedy Solver Selection is Sufficiently Good: Using a greedy approach (
greedy-SUNNY) for solver selection during training significantly speeds up the process and, surprisingly, often leads to better or comparable performance compared to the original SUNNY's more complex scheduling. This is crucial for scenarios with many algorithms where full training can be prohibitive. - Feature Selection Matters: While
k-value selection is important, feature selection also contributes positively to performance, indicating that not all available instance features are equally useful for AS. - Wrapper-Based is Better: Wrapper-based feature selection, which evaluates features in the context of the learning algorithm, proves more effective than simpler filter-based methods for this AS task.
Key Results
sunny-as2variants (especiallysunny-as2-fk) demonstrate competitive performance against state-of-the-art AS approaches, as measured by the "closed gap" metric.- In experiments on 12 ASlib scenarios,
sunny-as2-fkachieved the best average performance, outperformingsunny-asand other variants. sunny-as2-kwas particularly effective in scenarios wherek-value selection was crucial, achieving peak performance in 7 out of 12 scenarios.- When compared to other AS approaches on the 2017 AS competition instances,
sunny-as2achieved the highest average closed gap and was the best approach in specific scenarios (Bado and Sora). - The paper notes that using
greedy-SUNNYfor training andSUNNYfor testing often yields the best results, highlighting the trade-off between training speed and final prediction accuracy.
Limitations and Future Work
- Greedy-SUNNY's Sub-optimality: The paper acknowledges that
greedy-SUNNYdoes not guarantee finding the absolute minimal set of solvers that solve the most instances in a neighborhood. - Performance Variability: While not detailed in this extended abstract, the authors mention that further analysis of performance variability and insights into SUNNY can be found in a related, more extensive publication.
- Future Directions: The authors suggest exploring alternative AI-driven solver selection mechanisms and extending
sunny-as2to optimization problems where solution quality, not just runtime, is a critical factor.
Summary updated