sunny-as2: Enhancing SUNNY for Algorithm Selection (Extended Abstract)

Tong Liu, Roberto Amadini, Maurizio Gabbrielli, Jacopo MauroIJCAI 2022 · DOI

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-as2 actively 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-as2 co-learns the optimal k value 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-as2 employs 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-fk as a flavor that jointly learns both the optimal feature subset and the neighborhood size k. 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-as2 variants (especially sunny-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-fk achieved the best average performance, outperforming sunny-as and other variants.
  • sunny-as2-k was particularly effective in scenarios where k-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-as2 achieved the highest average closed gap and was the best approach in specific scenarios (Bado and Sora).
  • The paper notes that using greedy-SUNNY for training and SUNNY for 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-SUNNY does 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-as2 to optimization problems where solution quality, not just runtime, is a critical factor.

Summary updated

BibTeX
@inproceedings{liu2022sunny,
  author = {Tong Liu and Roberto Amadini and Maurizio Gabbrielli and Jacopo Mauro},
  title = {{sunny-as2: Enhancing SUNNY for Algorithm Selection (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/804},
}
Figure