Introduction

Given a collection of algorithms, the Algorithm Selection (AS) problem basically consists in identifying which of them is the best one for solving a given problem. Initially proposed by Rice in 1976 [9], in the last decade AS has attracted some attention [7,10]. In particular, the original notion of AS has been extended by the definition of Algorithm Portfolio (AP) [6]. In a nutshell, AP approaches exploit a portfolio {A 1 , . . . , A m } of different algorithms to get a globally better algorithm. They go beyond the original notion of AS introduced by Rice since APs perform the algorithm selection case-by-case instead of in advance. When a new, unseen problem p comes, an AP approach tries to predict which is (or which are) the best constituent algorithm(s) A i1 , A i2 , . . . , A i k , with 1 ≤ i j ≤ m, for solving p and then runs such algorithm(s) on p. Scheduling k > 1 algorithms can reduce the risk of selecting only one algorithm -maybe the wrong oneand possibly enables the knowledge sharing between the scheduled algorithms. However, note that the boundary between AS and AP is fuzzy: these two related problems are often considered as equivalent. For this reason, with a little abuse of notation, in the following we will only use the AS notation for indicating both AS and AP problems.

SUNNY is an algorithm selector tailored for Constraint Programming (CP), where the algorithms to be selected correspond to different constraint solvers. Originally conceived for solving Constraint Satisfaction Problems (CSPs) only [1], it has been later on adapted for dealing with Constraint Optimisation Problems (COPs) [3]. SUNNY is also the algorithm that underpins sunny-cp [4], a constraint solver exploiting a portfolio of different constituent solvers for solving both CSPs and COPs.

In this paper we present a preliminary evaluation of SUNNY on different AS benchmarks taken from the Algorithm Selection library (ASlib) [5]. We show that SUNNY can be applied also outside the CP domain, reaching promising performance in different fields such as Answer-Set Programming (ASP), Quantified Boolean Formula (QBF), or the Container Pre-marshalling Problem. Conversely, for the Boolean Satisfiability (SAT) problems of ASlib there is still a performance gap with the best AS approaches.

The SUNNY [1] algorithm was originally introduced for constraint solving. Fixed a solving timeout τ and a portfolio A of algorithms, SUNNY exploits instances similarity to produce a sequential schedule σ = [(A 1 , t 1 ), . . . , (A h , t h )] where algorithm A i ∈ A has to run for t i seconds and h i=1 t i = τ . For any input problem x, SUNNY uses a k-Nearest Neighbours (k-NN) algorithm to select from a training set of known instances the subset N (x, k) of the k instances closer to the feature vector of x according to the Euclidean distance. Basically, the feature vector of x is a collection F (x) ∈ R d of numerical attributes that characterise x (e.g., statistics over the variables or the constraints of x). Starting from the N (x, k) instances SUNNY relies on three heuristics to compute the schedule σ: H sel , for selecting the most promising algorithms {A 1 , . . . , A h } ⊆ A to run; H all , for allocating to each A i ∈ A a certain runtime t i ∈ [0, τ ] for i = 1, . . . , h; H sch , for scheduling the sequential execution of the algorithms according to their presumed speed. The heuristics H sel , H all , and H sch depends on the application domain. For CSPs, H sel selects the smallest sub-portfolio S ⊆ A that solves the most instances in N (x, k), by using the runtime for breaking ties. H all allocates to each A i ∈ S a time t i proportional to the instances that S can solve in N (x, k), by using a special backup solver for covering the instances of N (x, k) not solvable by any solver. Finally, H sch sorts the solvers by increasing solving time in N (x, k). For COPs the approach is similar, but different evaluation metrics are used. We conclude the section by showing an example of how SUNNY works on a given CSP; for more details about SUNNY we refer the interested reader to [1,3].

Example 1 Let x be a CSP, A = {A 1 , A 2 , A 3 , A 4 } a portfolio, A 3 the backup solver, τ = 1800 seconds the solving timeout, N (x, k) = {x 1 , ..., x 5 } the k = 5 neighbours of x, and the runtimes of solver A i on problem x j defined as in Table 1. In this case, the smallest sub-portfolios that solve the most instances (4 to be precise) in N (x, k) are {A 1 , A 2 , A 3 }, {A 1 , A 2 , A 4 }, and {A 2 , A 3 , A 4 }. The heuristic H sel selects S = {A 1 , A 2 , A 4 } because these solvers are faster in solving the instances in N (x, k). Since A 1 and A 4 solve 2 instances, A 2 solves 1 instance and x 1 is not solved by any solver, the time window [0, τ ] is partitioned in 2 + 2 + 1 + 1 = 6 slots: 2 assigned to A 1 and A 4 , 1 slot to A 2 , and 1 to the backup solver A 3 . Finally, H sch sorts the solvers by increasing solving time. The final schedule produced by SUNNY is therefore σ = [(A 4 , 600), (A 1 , 600), (A 3 , 300), (A

Evaluation

To evaluate SUNNY on different scenarios we exploited the Algorithm Selection library (ASlib). ASlib provides standardised format and data for representing AS scenarios allowing the comparison of different AS approaches. Each ASlib scenario contains: an algorithm space A = {A 1 , . . . , A m }; a problem space X = {x 1 , . . . , x n }; a feature space F d = {F 1 , . . . , F n } where F j ∈ R d is the feature vector of the problem x j ; a performance space P τ = {P 1,1 , . . . , P m,n } where P i,j ∈ R measures the performance of algorithm A i on problem x j within a timeout of τ seconds. ASlib contains 13 heterogeneous scenarios1 as summarised in Table 2. The scenarios differ in the number of algorithms m, problems n, features d, and in the time limits τ . For every scenario, the runtime is used as performance measure: if algorithm A solves problem x in t < τ seconds the runtime RunTime(A, x) of A on x is t. Otherwise, RunTime(A, x) = τ . Each scenario of the ASlib is evaluated with a 10-fold cross validation: X is partitioned in 10 subsets X 1 , . . . , X 10 called folds, treating in turn a fold X i as the test set and the union j =i X j of the other folds as the training set. Adapting SUNNY to ASlib scenarios was rather straightforward. Fixed a training set X tr ⊆ X and a corresponding feature space F tr , we normalised the feature vectors by removing all the constant features of F tr and scaling them in the range [−1, 1]. Then, for each unknown problem x / ∈ X tr , SUNNY computes the neighbourhood N (x, k) ⊆ X tr and the resulting schedule σ = [(a 1 , t 1 ), . . . , (a h , t h )] exactly as explained in Section 2. Following the methodology of [4], we set k = |X tr | and the backup solver as the algorithm of A having the lower average RunTime in X tr .

Table 3 shows for each scenario the Fraction of Solved Instances (FSI) of SUNNY. As the name underlines, the FSI of an AS approach is the ratio between the number of instances it solves and all the instances of the scenario. SUNNY is compared against the state-of-the-art AS approaches reported in [5] (viz., ISAC, SNNAP, aspeed, claspfolio, claspfolio-pre, zilla, and LLAMA) and two additional baselines: the Single Best Solver (SBS ), i.e., the algorithm in A with highest FSI, and the Virtual Best Solver (VBS ), i.e., the oracle approach that for every x ∈ X always select the algorithm A ∈ A for which RunTime(A, x) is minimal. We can see that SUNNY is the best approach for the QBF scenario, and that for all the non-SAT scenarios it is rather close to the best performance. Conversely, for the SAT benchmarks its performance is quite poor. The FSI metric is commonly used for comparing different AS approaches due to its simplicity and significance. However, it does not take into account the time needed to solve a problem. To capture also the timing aspects of the resolution, the Penalised Average Runtime (PAR) measure is often used. PAR k represents the average time taken to solve the problems by giving a penalisation of k × τ seconds for the instances not solved within the timeout τ .

Table 4 shows the results considering the average PAR 10 score. In this case the SBS is the single algorithm having the lower PAR 10 score. Not surprisingly, PAR 10 is strongly anti-correlated to FSI and the results of 4 somehow reflect what observed in Table 3. However, some differences arise. For instance, in addition to QBF, by considering PAR 10 SUNNY is the best approach also for the PROTEUS scenarios. This means that in this scenario aspeed solves few instances more than SUNNY, but SUNNY is on-average faster.

In this work we presented an evaluation of SUNNY algorithm on different Algorithm Selection (AS) scenarios coming from the Algorithm Selection library (ASlib). Despite SUNNY is tailored for constraint solving, its adaptation to AS appears to be promising also in other fields such as Answer-Set Programming (ASP), Quantified Boolean Formula (QBF), or the Container Pre-marshalling Problem. Conversely, for the Boolean Satisfiability (SAT) problems there is still a performance gap with the best approaches.

We would like to remark that in this evaluation we used the default SUNNY approach without leveraging its settings to fit the different scenarios. As a future work we would like to try to improve the performance of SUNNY by using well-known techniques like pre-solving, parameters tuning, and feature selection. It would be interesting to consider also different scenarios, like optimisation and planning problems. Indeed, the ASlib currently contains a limited number of scenarios for which the only metric is the runtime. It would be nice also to perform a deeper study to better understand the SUNNY performance (and in particular why SUNNY is not so good for the SAT benchmarks).

We strongly encourage the submission of new scenarios and new algorithm selectors to the ASlib in order to foster the study and the comparison of new and better AS approaches. For instance, since SUNNY turns out to be the best approach for QBF, it would be interesting to consider a comparison with the multi-engine solver AQME [8].

We are currently implementing SUNNY as an automated algorithm selector for ASlib scenarios, with the aim of enrolling it to the next ICON Challenge on Algorithm Selection. Moreover, we are also interested in studying how SUNNY can be optimally parallelised to run its algorithms simultaneously on multiple cores. A preliminary investigation on the SUNNY parallelisation for CSPs and COPs is presented in [2].