SUNNY for Algorithm Selection: A Preliminary Study

Abstract

Given a collection of algorithms, the Algorithm Selection (AS) problem consists in identifying which of them is the best one for solving a given problem. In this paper we show how we adapted the algorithm selector SUNNY, originally tailored for constraint solving, to deal with general AS problems. Preliminary investigations based on the AS Library benchmarks already show some promising results: for some scenarios SUNNY is able to outperform AS state-ofthe-art approaches.

1 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 fA1; : : : ; Amg 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) Ai1 ; Ai2 ; : : : ; Aik , with 1 ij 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 one— and 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.

SUNNY

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 = [(A1; t1); : : : ; (Ah; th)] where algorithm Ai 2 A has to run for ti seconds and Pih=1 ti = . For any input problem x, SUNNY uses a kNearest 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) 2 Rd 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 : Hsel, for selecting the most promising algorithms fA1; : : : ; Ahg A to run; Hall, for allocating to each Ai 2 A a certain runtime ti 2 [0; ] for i = 1; : : : ; h; Hsch, for scheduling the sequential execution of the algorithms according to their presumed speed. The heuristics Hsel, Hall, and Hsch depends on the application domain. For CSPs, Hsel selects the smallest sub-portfolio S A that solves the most instances in N (x; k), by using the runtime for breaking ties. Hall allocates to each Ai 2 S a time ti 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, Hsch 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 = fA1; A2; A3; A4g a portfolio, A3 the backup solver, = 1800 seconds the solving timeout, N (x; k) = fx1; :::; x5g the k = 5 neighbours of x, and the runtimes of solver Ai on problem xj 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 fA1; A2; A3g, fA1; A2; A4g, and fA2; A3; A4g. The heuristic Hsel selects S = fA1; A2; A4g because these solvers are faster in solving the instances in N (x; k). 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 the solvers by increasing solving time. The final schedule produced by SUNNY is therefore = [(A4; 600); (A1; 600); (A3; 300); (A2; 300)].

x1 x2

x4 x3 3 x5 278

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 = fA1; : : : ; Amg; a problem space X = fx1; : : : ; xng; a feature space Fd = fF1; : : : ; Fng where Fj 2 Rd is the feature vector of the problem xj ; a performance space P = fP1;1; : : : ; Pm;ng where Pi;j 2 R measures the performance of algorithm Ai on problem xj 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 X1; : : : ; X10 called folds, treating in turn a fold Xi as the test set and the union Sj6=i Xj of the other folds as the training set.

Adapting SUNNY to ASlib scenarios was rather straightforward. Fixed a training set Xtr X and a corresponding feature space Ftr, we normalised the feature vectors by removing all the constant features of Ftr and scaling them in the range [ 1; 1]. Then, for each unknown problem x 2= Xtr, SUNNY computes the neighbourhood N (x; k) Xtr and the resulting schedule = [(a1; t1); : : : ; (ah; th)] exactly as explained in Section 2. Following the methodology of [ 4 ], we set k = pjXtrj and the backup solver as the algorithm of A having the lower average RunTime in Xtr.

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 2 X always select the algorithm A 2 A for 1 We considered the 1.0.1 version of ASlib. For more details, we refer the reader to [ 5 ]. 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. PARk represents the average time taken to solve the problems by giving a penalisation of k seconds for the instances not solved within the timeout .

Conclusions

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 ].

References

1. R. Amadini , M. Gabbrielli , and J. Mauro. SUNNY: a Lazy Portfolio Approach for Constraint Solving . TPLP , 14 ( 4-5 ): 509 - 524 , 2014 .

2. R. Amadini , M. Gabbrielli , and J. Mauro . A Multicore Tool for Constraint Solving . In IJCAI , 2015 . Pre-print available at: http://arxiv.org/abs/1502.03986.

3. R. Amadini , M. Gabbrielli , and J. Mauro . Portfolio approaches for constraint optimization problems . AMAI , pages 1 - 18 , 2015 .

4. R. Amadini , M. Gabbrielli , and J. Mauro . SUNNY-CP: a Sequential CP Portfolio Solver . In SAC , 2015 . Available at http://www.cs.unibo.it/˜amadini/sac_2015.pdf.

5. Algorithm Selection Library - coseal. https://code.google.com/p/coseal/ wiki/AlgorithmSelectionLibrary.

6. C. P. Gomes and B. Selman . Algorithm portfolios . Artif. Intell., 126 ( 1-2 ): 43 - 62 , 2001 .

7. L. Kotthoff . Algorithm selection for combinatorial search problems: A survey . AI Magazine , 35 ( 3 ): 48 - 60 , 2014 .

8. L. Pulina and A. Tacchella . A self-adaptive multi-engine solver for quantified boolean formulas . Constraints , 14 ( 1 ): 80 - 116 , 2009 .

9. J. R. Rice . The Algorithm Selection Problem. Advances in Computers , 15 : 65 - 118 , 1976 .

10. K . A. Smith-Miles . Towards insightful algorithm selection for optimisation using metalearning concepts . In IJCNN , pages 4118 - 4124 . IEEE, 2008 .