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

1 Introduction

A meta-algorithmic way to face the disparate nature of combinatorial problems and speed-up their resolution is to use a portfolio of different algorithms (or solvers) to be selected on different problem instances. The task of identifying suitable algorithm(s) for specific instances of a problem is known as per-instance Algorithm Selection (AS).

The SUNNY [Amadini et al., 2014] portfolio approach was originally developed for Constraint Programming (CP). Given an unforeseen CP problem instance i, SUNNY retrieves the k-nearest neighbors of i and then selects the best solver(s) for these k instances, by assigning to them a time slot proportional to the number of solved instances. Finally, the selected solvers are sorted by average solving time and

i.

Afterwards, SUNNY has been extended to handle generic AS scenarios (sunny-as) without much luck: the default configuration of SUNNY did not generalize well outside the CP field. The extensions detailed in [Liu et al., 2021] significantly improve sunny-as thanks to the synergistic use of wrapper-based feature selection, neighborhood-size configuration and a greedy approach to speed-up the training phase. The empirical evaluations in [Liu et al., 2021] show that this new version, called sunny-as2, outperforms sunny-as as well as other state-of-the-art AS methods.

2 Preliminaries

Every AS problem instance is embedded in a given context or scenario. Formally, we can define an AS scenario as a triple (I,A,m) where: I is a set of instances; A is a set (or portfolio) of algorithms (or solvers) with |A| > 1; and m : I × A → R is a performance metric that we assume w.l.o.g. to be minimized. An (algorithm) selector s is a total mapping s : I → A that aims to return the best algorithm A ∈ A, according to m, for any instance i ∈ I. The AS problem consists in determining a selector s minimizing ∑ i∈I m(i, s(i)). This definition can be easily extended to selectors that, like SUNNY, schedule more than one solver.

∗The full version was published in the JAIR [Liu et al., 2021].

What makes hard AS is that the performance metric m on I is only partially known. The goal is hence to define a selector able to estimate the value of m for the instances i ∈ I where m(i, A) is unknown. A common practice is to partition I into a training set Itr, used to build a selector s, and a test set Its used to evaluate the performance of s.

A further complication arises from the (NP-)hardness of the instances in I. Typically a timeout τ is set and m is possibly extended with criteria to penalize a selector not finding any solution before τ occurs. A common practice is to use the Penalized Average Runtime (PAR) score with penalty λ > 1, penalizing unsolved instances with τ × λ. One drawback of PAR is that the values of τ and m can greatly change across different AS scenarios, thus making the absolute value of PAR hardly indicative for heterogeneous scenarios. In these cases relative metrics are better [Amadini et al., 2022].

In the AS competitions 2015 and 2017 [Lindauer et al., 2019] the closed gap score is used to measure how much a selector improves the single best solver (SBS) of the scenario w.r.t. the virtual best solver (VBS) with m = PAR10. The SBS is the best individual solver available, and its scenario mSBS = min{∑i∈I m(i, A) | A ∈ A}. The

VBS is a virtual selector always picking the best solver for a given instance, and its scenario performance is mVBS = ∑i∈I min{m(i, A) | A ∈ A}. The closed gap for a selector s is mSBS-ms mSBS-mVBS with ms = ∑i∈I m(i, s(i)). A good selector has ms close to mVBS, hence the closed gap close to 1. If instead ms is near to mSBS the closed gap tends to 0 or less.

AS scenarios typically characterize each instance i ∈ I with a corresponding feature vector F(i) ∈ Rn , so the algorithm selection for i is actually performed according to F(i). The feature selection (FS) process allows one to consider smaller feature vectors F ′ (i) ∈ Rm, derived from F(i) by projecting m ≤ n of its features. The goal is reducing the search space for fitting a model, diminishing the noise of misleading features and improving the prediction accuracy.

FS approaches can be classified in filters, wrappers. Filter methods select the features regardless of the model, trying to suppress the least interesting ones. These methods are efficient and robust to overfitting. In contrast, wrappers evaluate subsets of features possibly detecting interactions. They can be more accurate than filters, but also more exposed to overfitting and can have a much higher computational cost. 1

2.1 SUNNY

The SUNNY portfolio approach was firstly introduced by Amadini et al. [2014]. SUNNY relies on a number of assumptions: (i) a small portfolio is usually enough to achieve a good performance; (ii) solvers either solve a problem quite quickly, or cannot solve it in reasonable time; (iii) solvers perform similarly on similar instances; (iv) a too heavy training phase is often an unnecessary burden.

Given a test instance x ∈ Its, SUNNY produces a sequential schedule σ = [(A1, t1), . . . , (An, tn)] where the algorithm Ai ∈ A runs for ti seconds on x and ∑ni=1 ti = τ. The schedule is obtained as follows. First, SUNNY employs k-NN to select from Itr the subset Ik of the k instances closest to the feature vector F(x) according to the Euclidean distance. Then, it uses three heuristics to compute σ: (i) Hsel, for selecting the most effective algorithms {A1, . . . ,An} ⊆ A in Ik; (ii) Hall, for allocating to each Ai ∈ A a certain runtime ti ∈ [0, τ] for i = 1, . . . , n; (iii) Hsch, for scheduling the sequential execution of the algorithms according to their performance in Ik.

The heuristics Hsel, Hall, and Hsch are based on the performance metric, and depend on the application domain. E.g., for CSPs Hsel selects the smallest set of solvers S ⊆ A that "solves" the most instances in Ik, breaking ties with runtime; Hall allocates to each Ai ∈ S a time ti proportional to the instances that S solves in Ik, by using a special backup solver covering the instances of Ik not solvable by any solver; finally, Hsch sorts the solvers by increasing solving time in Ik.

Example 1 Let x be a CSP, A = {A1,A2,A3,A4} a portfolio, A3 the backup solver, τ = 1800s the timeout, Ik = {x1, ..., x5} the k = 5 neighbors of x, and the runtime of solver Ai on problem xj defined as in Tab. 1. In this case, the smallest set of solvers that solve most instances in Ik are {A1,A2,A3}, {A1,A2,A4}, and {A2,A3,A4}. The heuristic Hsel selects S = {A1,A2,A4} because these solvers are faster in solving the instances in Ik. Since A1 and A4 solve 2 instances, A2 solves 1 instance and x1 is not solved by any solver, the time window [0, τ] is partitioned in 2 + 2 + 1 + 1 = 6 slots: 2 assigned to A1 and A4, 1 slot to A2, and 1 to the backup solver A3. Finally, Hsch sorts in ascending order the solvers by average solving time in Ik. The final schedule produced by SUNNY is, therefore, σ = [(A4, 600), (A1, 600), (A3, 300), (A2, 300)].

1 Embedded methods integrating feature selection into the learning algorithm also exist.

SUNNY aims to avoid overfitting w.r.t. the performance of the solvers in the selected neighborhood, i.e., it tries to not be too tied to the strong assumption that the runtimes in the neighborhood faithfully reflect the runtime on the instance to solve. Clearly, the design choices of SUNNY have pros and cons. For example, the schedule in Example 1 cannot solve the instance x2 although x2 is actually in the neighborhood.

The sunny-as [Amadini et al., 2015] tool implements SUNNY algorithm to handle generic AS scenarios of ASlib library [Bischl et al., 2016]. In its optional pre-processing phase, sunny-as can perform only filter-based feature selection and select a pre-solver to be run for a short time. At runtime, it produces the schedule of solvers by following the approach explained above. The AS challenge 2015 [Lindauer et al., 2019] underlined some issues of sunny-as, especially in SAT scenarios. One reason is that sunny-as does not learn any parameter according to the input AS scenario, but it only uses default values (e.g., the neighborhood size is set to square root of its training set, rounded to the nearest integer).

3 sunny-as2

sunny-as2 is the evolution of sunny-as and its preliminary prototype attended the 2017 AS competition. 2 It introduces an integrated approach where features and k-value of the underlying k-NN are co-learned during the training step. In particular, wrapper-based FS is performed. This makes sunnyas2 "less lazy" than the original SUNNY, which only scaled the features in [-1, 1] without performing any actual training.

To improve the configuration accuracy and robustness, and to assess the quality of a parameters setting, sunny-as2 uses nested cross-validation [Loughrey and Cunningham, 2005]. The original dataset is split into five folds thus obtaining five pairs (T1, S1) . . . , (T5, S5) where the Ti are the outer training sets and the Si are the (outer) test sets, for i = 1, . . . , 5. For each Ti we then perform an inner 10-fold CV to get a suitable parameter setting. We split each Ti into further ten sub-folds T ′ i,1 , . . . , T ′ i,10 , and in turn for j = 1, . . . , 10 we use a sub-fold T ′ i,j as validation set to assess the parameter setting computed with the inner training set, which is the union of the other nine sub-folds ⋃k̸=j T ′ i,k . We then select, among the 5 configurations obtained, the one for which SUNNY achieves the best PAR10 score on the corresponding validation set. The selected configuration is used to run SUNNY on the paired test set Si.

Before explaining how sunny-as2 learns features and kvalue, we first describe greedy-SUNNY, the "greedy variant" of SUNNY introduced to speed-up the solvers' selection. SUNNY computes the smallest portfolio that maximizes the number of solved instances in a neighborhood N . The worstcase time complexity is O(2m), where m is the number of available solvers. greedy-SUNNY instead starts from S = ∅ and adds to S one solver at a time by selecting the one solving the most instances in N. These instances are then removed from N and the process is repeated until |S| = λ or N = ∅, where λ is an external threshold. 3 According to empirical experiments, it is reasonable to set a small value for λ (e.g., 3) as also suggested by the experiments in [Lindauer et al., 2016]. If λ is a constant, the worst-case time complexity of greedy-SUNNY is O(m · |N|).

2 The 2017 AS competition was named OASC challenge, while the 2015 AS competition was called ICON challenge.

3.1 Selecting Features and Neighborhood Size

sunny-as2 uses greedy-SUNNY to learn the features and/or the k-value for a given AS scenario. The user can choose among three different flavors, namely:

1. sunny-as2-k. All the features are used and only kconfiguration is performed by varying k in the range [1, maxK ] where maxK is a user-defined parameter.
2. sunny-as2-f. The k-value is fixed to its default and FS is performed. Starting from F = ∅, the feature decreasing the most the PAR10 is added, until PAR10 increases or |F| = maxF where maxF is a user-defined parameter.
3. sunny-as2-fk. The k-value and the features are configured together by running sunny-as2-f with different values of k in [1,maxK].

Algorithm 1 shows through pseudo-code how sunny-as2fk selects the features and the k-value. LEARNFK takes as input the available algorithms A, the maximum schedule size λ for greedy-SUNNY, the set of training instances I, the maximum neighborhood size maxK, the original set of features F, and the upper bound maxF on the maximum number of features to be selected. It returns the learned value bestK ∈ [1,maxK] for the neighborhood size and the learned set of features bestF ⊆ F having |bestF | ≤ maxF .

After the i-th iteration of the outer for loop (Lines 7-17) the current set of features currFeat consists of exactly i features. Each time currFeat is set, the inner for loop is executed n times to evaluate different values of k on dataset I. The evaluation is performed by GETSCORE, which returns the score (the higher, the better) of a particular SUNNY setting. By default, GETSCORE relies on greedy-SUNNY instead of the original SUNNY to have a faster solver selection.

At the end of the outer for loop, if adding a new feature could not improve the score of the previous iteration (i.e., with |currFeat|-1 features) the learning process halts. Otherwise, both the features and the k-value are updated and a new iteration begins, until the score cannot be further improved or the maximum number of features maxF is reached.

If d = min(maxF, |F|), n = min(maxK, |I|) and the worst-case time complexity of GETSCORE is γ, then the overall worst-case time complexity of LEARNFK is O(d2nγ).

From LEARNFK one can easily deduct the algorithms for learning either the k-value (for sunny-as2-k) or the selected features (for sunny-as2-f): in the first case, the outer for loop

3 As one can expect, greedy-SUNNY does not guarantee that S is the minimal set of solvers solving the most instances of N.

1: function LEARNFK(A, λ, I, maxK, F, maxF) 2: bestF ← ∅ 3: bestK ← 1 4: bestScore ← -∞ 5: while |bestF| < maxF do 6: currScore ← -∞ 7: for f ∈ F do 8: currF eat ← bestF ∪ {f } 9: for k ← 1, . . . , maxK do 10: s ← GETSCORE(A, λ, I, k, currFeat) 11: if s > currScore then 12: currScore ← s 13: currF eat ← f 14: currK ← k 15: end if 16: end for 17: end for 18: if currScore ≤ bestScore then 19: break ▷ Cannot improve best score 20: end if 21: bestScore ← currScore 22: bestF ← bestF ∪ {currF eat} 23: bestK ← currK 24: F = F - {currF eat} 25: end while 26: return bestF, bestK 27: end function

is omitted because features do not vary; in the second case, the inner loop is skipped because the value of k is constant.

4 Experiments

In this section we report part of the experiments we conducted over several configurations of sunny-as2. We omit here the sensitivity evaluations of the parameters that sunnyas2 cannot learn, i.e., the split modes for cross-validation and the limits on the numbers of features, training instances, and schedule size. Also, we skip the analysis on the performance variability of sunny-as2 and other insights on SUNNY. All this information can be found in [Liu et al., 2021].

In the following we will show how SUNNY can benefit from learning the k-value and/or the features, how greedySUNNY can improve the original SUNNY, and some comparisons of sunny-as2 against other AS approaches. 4

We first compared sunny-as2-f, sunny-as2-k, and sunny-as2-fk against the original version of sunny-as on 12 ASlib scenarios. Tab. 2 shows the average closed gap of each approach. Interestingly, there is not a dominant configuration. As also shown in Lindauer et al. [2016], a proper kconfiguration is crucial for SUNNY-indeed, sunny-as2-k achieves the peak performance in 7 scenarios out of 12. However, sunny-as2-fk has the best average performance across all the scenarios. The main reason is arguably the poor performance of sunny-as2-k in the TSP scenario. sunny-as is clearly less promising than any other variant of sunny-as2, but it is the best approach for GRAPHS. What we can conclude from Tab. 2 is that most of the performance improvement is due to the selection of the right neighborhood size k. However, feature selection also gives a positive contribution.

4 All the experiments were run on Linux machines with Intel Corei5 3.30GHz processors and 8 GB of RAM. We used a time cap of 24 hours for learning the parameters. All the ASlib scenarios are publicly available at https://github.com/coseal/aslib data

We recall that by default greedy-SUNNY is used to compute k-value and/or features on the training sets. Then, sunny-as2 sets the corresponding SUNNY parameters to the computed values when it runs on the test sets. The rationale is to speed-up the training time, so that for scenarios with a high number of algorithms (e.g., Svea) can exceed 24 hours of computation. Interestingly, we later realized that training sunny-as2 with SUNNY instead of greedy-SUNNY does not bring any substantial benefit. Surprisingly, in 8 scenarios out of 12 the performance deteriorates. We also noted that the peak performance in any scenario is achieved when SUNNY is used for testing. Using greedy-SUNNY on an unforeseen instance might therefore be useful in time-sensitive contexts where exponential-time scheduling is not acceptable but, in general, SUNNY provides a more precise scheduling.

Table 3 shows the hypothetical performance of the improved sunny-as2 in the 2017 AS competition. 5 In addition to the original competitors (viz., *Zilla, ASAP, AS-RF and the preliminary versions of sunny-as2 called sunny-as2fk-OASC and sunny-as2-k-OASC in Tab. 3) we added 3 more baselines: AutoFolio [Lindauer et al., 2015], the original SUNNY approach [Amadini et al., 2014], and an off-theshelf Random Forest approach.

Tab. 3 shows that sunny-as2 has the highest average closed gap, and it is the best approach in Bado and Sora scenarios. Unsurprisingly, its performance is quite close to the one of sunny-as2-fk-OASC. ASAP.v2 does not attain the best score in any scenario, but in general its performance is robust and effective-this confirms what reported in [Gonard et al., 2019]. AutoFolio is slightly behind ASAP.v2, nevertheless it achieves good results and it is the best approach for the Magnus scenario. As sunny-as2, also AutoFolio suffers in scenarios like Caren and Mira having a small number of instances. *Zilla and ASAP.v3 also close more than 50% of the gap between the SBS and the VBS. sunny-as2-k-OASC is instead slightly below this threshold: the performance difference w.r.t. sunny-as2-fk-OASC denotes the importance of a proper feature selection. The original SUNNY approach is even worse: this confirms the effectiveness of the improvements introduced by sunny-as2.

5 The submitted version was prototypical and slightly different.

At the bottom of the table we find the AS approaches based on Random Forest. However, it is crucial to highlight that the chosen performance metric plays a fundamental role as clearly shown in [Liu et al., 2021]. For example, replacing the closed gap score with the one adopted in the MiniZinc Challenge [Stuckey et al., 2014] literally overturns the closed-gap ranking. An in-depth discussion of this issue can be found in Amadini et al. [2022].

5 Conclusions

We experimentally learned that wrapper-based feature selection and k-configuration are quite effective for SUNNY, and perform better when integrated. Moreover, a sub-optimal greedy approach for solver selection enables a more robust, fast and effective training w.r.t. the schedule generation procedure of the original SUNNY approach. These three ingredients significantly improved the SUNNY performance for generic AS scenarios, making sunny-as2 a state-of-the-art AS approach for runtime minimization.

A natural future direction for SUNNY is the study of alternative AI-driven solver selection mechanisms, and the extension of sunny-as2 to optimization problems, for which the solution(s) quality must be taken into account.