Roberto Amadini

Peter J Stuckey

Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers

Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving Constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for Constraint Optimization Problems (COPs). Unlike CSPs, sequential execution of optimization solvers can communicate information in the form of bounds to improve the performance of the following solvers. We provide a hybrid and flexible portfolio approach that combines static and dynamic time splitting for solving a given COP. Empirical evaluations show the approach is promising and sometimes even able to outperform the best solver of the porfolio.

Introduction and Related Work

One of the main uses of Constraint Programming (CP) is to model and solve Constraint Satisfaction Problems (CSP) [START_REF] Mackworth | Consistency in Networks of Relations[END_REF]. Solving CSPs is hard, and there are plenty of approaches that can be used to tackle them. One of the more recent trend in this research area-especially in the SAT field-is trying to solve a given problem by using a portfolio approach [START_REF] Gomes | Algorithm portfolios[END_REF][START_REF] Rice | The Algorithm Selection Problem[END_REF].

An algorithm portfolio is a general methodology that exploits a number of different algorithms in order to get an overall better algorithm. A portfolio of CP solvers can therefore be seen as a particular solver, the portfolio solver, that exploits a collection of m > 1 different constituent solvers s 1 , . . . , s m in order to obtain a globally better CP solver. When a new unseen instance i arrives, the portfolio solver tries to predict which are the best constituent solvers s 1 , . . . , s k (k ≤ m) for solving i and then runs such solver(s) on i. This solver selection process is clearly a fundamental part for the success of the approach and it is usually performed by exploiting Machine Learning techniques.

There has been a significant body of work in using portfolios to leverage and combine a number of different solvers in order to get an overall better solver [START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF][START_REF] Kotthoff | Algorithm Selection for Combinatorial Search Problems: A Survey[END_REF]. A particular case of portfolio approach consists in scheduling (even in parallel) a subset of the constituent solvers within a certain time window (see for instance [START_REF] Amadini | SUNNY: a Lazy Portfolio Approach for Constraint Solving[END_REF][START_REF] Audemard | PeneLoPe, a Parallel Clause-Freezer Solver[END_REF][START_REF] Hamadi | ManySAT: a Parallel SAT Solver[END_REF][START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF][START_REF] Omahony | Using case-based reasoning in an algorithm portfolio for constraint solving[END_REF]24]. This would seem to be a winning strategy, in particular due to the fact that often the solving time of a satisfaction problem is either relatively short or very long. It hence naturally handles the heavy tailed nature of solving.

Surprisingly, most of the focus of algorithm portfolios has been on constraint satisfaction problems. In practice most of the combinatorial problems of interest are Constraint Optimization Problems (COPs), where we are interested in finding a solution which minimizes as much as possible a given objective function. As pointed out also in [START_REF] Smith-Miles | Cross-disciplinary perspectives on meta-learning for algorithm selection[END_REF], there is a lack of use of meta-learning for algorithm selection: to the best of our knowledge, COP portfolios are mostly developed just for some specific optimization problems like Knapsack, Most Probable Explanation, Set Partitioning, Travel Salesman Problem [START_REF] Guo | A machine learning approach to algorithm selection for NP-hard optimization problems: a case study on the MPE problem[END_REF][START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF][START_REF] Telelis | Combinatorial Optimization through Statistical Instance-Based Learning[END_REF] or for example to properly tune the parameters of a single COP solver [START_REF] Kadioglu | ISAC -Instance-Specific Algorithm Configuration[END_REF][START_REF] Xu | Hydra-MIP: Automated Algorithm Configuration and Selection for Mixed Integer Programming[END_REF].

It is hence natural to ask how to create a scheduling algorithm portfolio for COPs. A crucial difference from CSPs arises because a COP solver may yield sub-optimal partial solutions before finding the best one (and possibly proving its optimality). This means that one solver can transmit useful bounds information to another if they are scheduled sequentially. This key feature is the basis of our work. Indeed, in a portfolio scenario, a partial solution found by a solver s 1 is a token of knowledge that s 1 can pass to another solver s 2 in order to prune its search space and therefore possibly improve its solving process. In this paper, we thus address the problem of boosting optimization by exploiting the sequential cooperation of different COP solvers. To do so, we will introduce the notion of solving behaviour for taking into account the anytime performance of the solvers.

A work related to this paper is [START_REF] Carchrae | Low-knowledge algorithm control[END_REF], in which algorithm control techniques are used to share bounds information between the scheduled solvers without, however, explicitly rely on the solvers behaviours (as in our technical definition). In [START_REF] Malitsky | Boosting sequential solver portfolios: Knowledge sharing and accuracy prediction[END_REF] the authors provide a generic approach to knowledge sharing, based on the communication of learned clauses and cuts information, which is suitable for sequential SAT solvers but is less likely to be useful when solvers are very disparate in nature. Finally, [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] reports an empirical evaluation of different portfolio approaches applied to COPs, without however taking into account the anytime performance of the solvers as well as the possible bounds communication between them.

Paper Structure. In Section 2 we give the technical definitions of solving behaviour and timesplit solver; then, in Section 3, we provide and evaluate TimeSplit: an algorithm aimed to determine the best time splitting according to already known behaviours. By exploiting the results of TimeSplit in Section 4 we introduce TPS, a generic and flexible portfolio approach that relies on two steps: when a new unseen problem arrives, a static solver schedule (computed off-line) is run first, while a dynamic schedule is executed then by possibly exploiting the best solution found in the first stage. In Section 5 we describe the methodology and the results achieved by TPS, using the SUNNY [START_REF] Amadini | SUNNY: a Lazy Portfolio Approach for Constraint Solving[END_REF][START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] algorithm as a baseline for computing and evaluating different portfolio approaches. Finally, in Section 6 we conclude by providing some possible future directions.

Let us fix a dataset of minimization3 problems ∆, a universe of COP solvers Σ (which can include a particular portfolio Π ⊆ Σ) and a solving time window [0, T ]. We wish to determine the best sequence of solvers in Σ to run on p and for how long to run each solver within the interval [0, T ] in order obtain the best result for instance p. Ideally we aim to improve the best solver of Σ for the instance p.

We define the (solving) behaviour of each solver s ∈ Σ applied to a problem p ∈ ∆ over time [0, T ] as a sequence of pairs B(s, p) = [(t 1 , v 1 ), . . . , (t n , v n )] where t i ∈ [0, T ] is the time when s finds a solution, and v i is the objective value of such a solution. Note that we can consider the pairs ordered so that

t 1 < • • • < t n while v 1 > • • • > v n since
we assume the solving process is monotonic (we can omit the non-monotonic entries if any). For example, consider the behaviours B(s 1 , p) = [ [START_REF] Decat | KRR Software: MinisatID[END_REF]40), (50, 25), (100, [START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF]] and B(s 2 , p) = [(800, 45), (900, 10)] illustrated in Figure 1a with a timeout of T = 1000 seconds. The best value v * = 10 is found by s 2 after 900 seconds, but it takes 800 seconds to find its first solution (v = 45). Meanwhile, s 1 finds a better value (v = 40) after just 10 seconds and even better values in just 100 seconds. So, the question is: what happens if we "inject" the upper bound 40 from s 1 to s 2 ? Considering that starting from v = 45 the solver s 2 is able to find v * in 100 seconds (from 800 to 900), hopefully starting from any better (or equal) value v ′ ≤ 45 the time needed by s 2 to find v * is no more than 100 seconds. Note that from a graphical point of view what we would like to do is therefore to "shift" the curve of s 2 towards the left from t = 800 to 10, by exploiting the fact that after 10 seconds s 1 can suggest to s 2 the upper bound v = 40. The cooperation between s 1 and s 2 would thereby reduce by ∆t = 790 seconds the time needed to find v * , and moreover would allow us to exploit the remaining ∆t seconds for finding better solutions or even proving the optimality of v * . However, note that the virtual behaviour may not occur: it may be that s 2 calculates important information in the first 800 seconds required to find the solution v * = 10, and therefore the injection of v = 40 could be useless (if not harmful!).

Given a problem p ∈ ∆ and a schedule σ = [(s 1 , t 1 ), . . . , (s k , t k )] of k solvers we define the corresponding timesplit solver as a particular solver such that: i) first, runs s 1 on p for t 1 seconds; ii) then, for i = 1, . . . , k -1, runs s i+1 on p for t i+1 seconds possibly exploiting the best solution found by the previous solver s i in t i seconds. We will use the notation σ to indicate the base of timesplit solver σ where we omit the last solver in the schedule, i.e. σ = [(s 1 , t 1 ), . . . , (s k-1 , t k-1 )]. Intuitively, if s k is the last solver of the schedule, σ is the timesplit solver that ideally contributes to improve s k .

As an example, in Figure 1a the ideal timesplit solver would be defined by σ = [(s1, 10), (s2, 990)], but note that there are cases in which the timesplit solver is actually a single solver, since the best solver is not virtually improvable by any other: this happens when every solution found by the best solver is also the best solution found so far (e.g., see Figure 1b). Moreover, there may be also cases in which splitting the time window in more than two slots (even alternating the same solvers) may ideally lead to better performances. Indeed, the "overall" best solver at the time edge T might no longer be the best one at a previous time t < T . For example, in Figure 1c the best solver at time t ≥ 800 is s 1 , at time 400 ≤ t < 800 is s 3 while for t ≤ 400 is s 2 ; in Figure 1d the best solver is s 1 if t < 400 or t ≥ 800, while for 400 ≤ t < 800 is s 2 .

Splitting Selection and Evaluation

Once we have informally hypothesized the potential benefits of timesplit solvers, some questions naturally arise. First, which metric(s) is reasonable to formally define the "best solver"? Furthermore, how do we split the time window between solvers for determining the (virtually) best timesplit solver? Finally, to what extent do timesplit solvers act like the virtual timesplit solvers? In order to answer these questions, we fixed some proper metrics, defined a splitting algorithm and empirically evaluated the assumptions previously introduced.

Evaluation Metrics

In order to evaluate the performances of different COP solvers (and thus formally define the notion of best solver) we examine a number of metrics for grading a solver s on a problem p over a time limit T . Analogous to the usual metric for CSP solvers, let proven(s, p) = 1 if solver s finds and proves the optimal solution (including proving unsatisfiability or unboundedness) for problem p in T seconds, and 0 otherwise. A slightly better metric measures optimization time, i.e. the time to find an optimal solution. Let otime(s, p) = t if s finds and proves the optimal solution of p in time t, and otime(s, p) = T if proven(s, p) = 0. Unfortunately, both these metrics are rather poor at discriminating: for many optimization problems no solver may be able to prove optimality.

The score function introduced in [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] gives to each solver a score in [0.25, 0.75] proportional to the distance between the best solution it finds and the best known solution. An additional reward (score = 1) is given if proven(s, p) = 1 while a punishment (score = 0) is given if no solution is found without proving unsatisfiability. Let val(s, p, t) = min ({+∞} ∪ {v | (t ′ , v) ∈ B(s, p), t ′ ≤ t}) be the (possible) best objective value found by solver s for instance p at time t. Let V p = {val(s, p, T ) ∈ Z | s ∈ Σ} be the set of all the objective values found by any solver s at the time limit T . The score of solver s on a problem p (at the time limit T ) is a value score(s, p) ∈ {0, 1} ∪ [0.25, 0.75] such that:

score(s, p) =              0 if val(s, p, T ) = +∞; else 1 if proven(s, p) = 1; else 0.75 if val(s, p, T ) = min V p = max V p ; else 0.75 -0.5 • val(s, p, T ) -min V p max V p -min V p
Under this measure, a better solver has a higher score. While more discriminatory than the previous measures, the score measure is still only considers the result at the time limit T , without considering how it was reached (i.e. the behaviour).

In this work we introduce a new metric able to estimate the anytime solver performance. Let W p = {val(s, p, t) ∈ Z | s ∈ Σ, t ∈ [0, T ]} be the set of all the solutions found by any solver at any time, so min W p is the best solution found for problem p and max W p is the worst one

. If B(s, p) = [(t 1 , v 1 ), . . . , (t n , v n )]
is the behaviour of solver s on problem p, we define the (solving) area of s on p as:

area(s, p) = t 1 + n i=1 0.25 + 0.5 • val(s, p, t i ) -min W p max W p -min W p (t i+1 -t i )
where t n+1 = otime(s, p). As the name implies, area is a normalized measure of the area under a solver behaviour. This metric is similar to the primal integral [START_REF] Berthold | Measuring the impact of primal heuristics[END_REF] used for measuring impact of heuristics for MIP solvers, but differs since the primal integral assumes the optimal solution is known, while area also differentiates between finding and proving a solution optimal. The area measure folds in a number of measures of the strength of an optimization algorithm: the quality of the best solution found, how quickly any solution is found, whether optimality is proven, and how quickly good solutions are found. Even though the ideal goal is to find the best objective value and hopefully proving its optimality, area allows us to discriminate much more between solvers, since we capture the tradeoff between speed and solution quality. Two solvers which eventually reach the same best solution (without proving optimality) are indistinguishable with the other measures, but we would almost certainly prefer the solver that finds the solution(s) faster. Furthermore, consider two solvers that prove optimality at the same instant t < T : while both will have otime = t, area will reward the solver in [0, t] that finds better solutions faster. Finally, we can now define the best solver of Σ for a given problem p as the solver s ∈ Σ which minimizes (w.r.t. the lexicographic ordering) the set of triples (1score(s, p), otime(s, p), area(s, p)) i.e., the solver that finds the best solution within the time limit T , breaking ties using minimum optimization time first, and then minimum area (i.e., giving priority to the solvers that prove optimality in less time, or at least that quickly find sub-optimal solutions).

TimeSplit Algorithm

Our goal is now to find a suitable timesplit solver for instance p which can improve upon the best solver for p. The algorithm TimeSplit described with pseudo-code in Listing 1.1 encodes what was informally explained earlier (see Figure 1). Given as input a problem p, a portfolio Π ⊆ Σ, and the timeout T , the basic idea of TimeSplit is to start from the behaviour of the best solver s 2 ∈ Π for p and then examine other solvers behaviours looking for the maximum ideal "left shift" toward another solver s 1 ∈ Π \ {s 2 }. Then, starting from s 1 , this process is iteratively repeated until no other shift is found. The best solver of Π is assigned to s 2 via function best solver in line 2, while line 3 set the current schedule σ to [(s 2 , T )]. In line 4 auxiliary variables are initialized: tot shift keeps track of the sum of all the shifts identified, max shift is the current maximum shift that s 2 can perform, split time is the time instant from which s 2 will start its execution, while split solver is the solver that has to be run before s 2 until split time instant. The while loop enclosed in lines 5-18 is repeated until no more shifts are possible (i.e., max shift = 0). The three nested loops starting at lines 7-9 find two pairs (t 1 , v 1 ) and (t 2 , v 2 ) such that s 2 can virtually shift to another solver s 1 , i.e., such that in the current solving window [0, split time] we have that at time t 1 < t 2 solver s 1 finds a value v 1 better than or equal to v 2 .

If the actual shift ∆t = t 2 -t 1 is greater than max shift, in lines 11-13 the auxiliary variables are updated accordingly. At the end of each such loop, if at least one shift has been detected (max shift > 0) the current schedule σ needs to be updated. In line 15, the allocated time of the current first solver of σ (i.e., s 2 ) is decreased by an amount of time max shift + split time (note that first(σ) is a reference to the first element of σ, while snd returns the second element of a pair, i.e. the allocated time in this case). This is because split time seconds will be allocated to split solver (line 16: push front inserts an element on top of the list) while max shift seconds corresponding to the ideal shift will be later donated to the 'overall' best solver of Π (i.e., the last solver of σ) via tot shif t variable. At this stage, the search for a new shift is restricted to the time interval [0, split time] in which the new best solver s 2 will be split solver (line 18). Once out of the while loop (no more shifts are possible) the total amount of all the shifts found is added to the best solver (line 19: last(σ) is a reference to the last element of σ) and the final schedule is finally returned in line 20.

Listing 1.1: TimeSplit Algorithm.

1 TimeSplit(p, Π, T ) : 2 s2 = best solver(p, Π, T ) 3 σ = [(s2, T )] 4 tot shift = 0 ; max shift = 1 ; split time = T ; split solver = s2 5 while max shift > 0 : 6 max shift = 0 7 for (t2, v2) in {(t, v) ∈ B(s2, p) | t ≤ split time} : 8 for s1 in Π \ {s2} : 9 for (t1, v1) in {(t, v) ∈ B(s1, p) | t < t2 ∧ v ≤ v2} : if t2 -t1 > max shift : max shift = t2 -t1 split time = t1 split solver = s1 if max shift > 0 :
first(σ).snd -= max shift + split time push front(σ, (split solver , split time)) tot shif t += max shift s2 = split solver last(σ).snd += tot shift return σ

TimeSplit Evaluation

In order to experimentally verify the correctness of our assumptions of the behaviour of timesplit solvers, we tested TimeSplit by considering a portfolio Π constructed from the solvers of the MiniZinc 1.6 suite [21] (i.e., CPX, G12/FD, G12/LazyFD, and G12/MIP) with some additional solvers disparate in their nature, namely: Gecode [START_REF]GECODE -An open, free, efficient constraint solving toolkit[END_REF] (CP solver), MinisatID [START_REF] Decat | KRR Software: MinisatID[END_REF] (SAT-based solver), Chuffed (Lazy Clause CP solver), and G12/Gurobi (MIP solver). We retrieved and filtered an initial dataset ∆ of 4864 MiniZinc COPs from MiniZinc 1.6 benchmarks and the MiniZinc Challenges 2012/13 and then ran TimeSplit using a solving timeout of T = 1800 seconds. In particular, we ran and compared two versions of the algorithm: the original one and a variant (denoted TS-2 in what follows) in which we imposed a maximum size of 2 solvers for each schedule σ. This is because splitting [0, T ] in too many slots can be counterproductive in practice: excessive fragmentation of the time window may produce time slots that are too short to be useful. Once executed these algorithms, in order to evaluate their significance we discarded all the "degenerate" instances for which the potential total shift was minimal (less than 5 seconds). We then ended up with a reduced dataset ∆ ′ ⊂ ∆ of 596 instances. We ran timesplit solvers defined by the schedule returned by each algorithm on every instance of ∆ ′ . In addition, we added as a baseline the Virtual Best Solver (VBS) i.e. a fictitious portfolio solver that always choose the best solver for every instance according to a given metric. Finally, we evaluated and compared the average performance in terms of the above mentioned metrics: score, proven, otime, area.

Table 1 shows the average results for each approach. As can be seen, the performances are rather close. On average, VBS is still the best solver if we focus on score metric (i.e., considering only the values found at the time limit T ). Regarding proven and otime metrics, we can observe a substantial equivalence: VBS is slightly better in terms of percentage of optima proven, while it is worse than TimeSplit and TS-2 if we consider the average time to prove optimality. Conversely, looking at area the situation appears to be more clearly defined: on average, VBS is substantially worse than both TimeSplit and TS-2. This means that, even if the virtual behaviour does not always occur, often the time splitting we propose is able to find good partial solutions more quickly than the best solver of Π. Focusing just on the two versions of TimeSplit, we can also note that these are substantially equivalent: this confirms the hypothesis that limiting the algorithm to schedule only two solvers is a reasonable choice (TS-2 seems slightly better than TimeSplit on average). Indeed, among all the instances of ∆ ′ , only for 53 of them TimeSplit has produced a schedule with more than two solvers. Table 2 shows instead how many times the approach on the i-th row is better than the one on the j-th column. In this case we can note that TimeSplit and TS-2 perform better than VBS: indeed, in the cases in which the score is the same for both the approaches, often the timesplit solvers take less time to find a (partial) solution. Note that for 375 problems (62.92% of ∆ ′ ) at least one between TimeSplit and TS-2 is better than the VBS. Let ∆ * be the set of such instances, and considering the base σ(p) of each schedule σ(p) returned by the best approach between TimeSplit and TS-2 for each instance of p ∈ ∆ * , we noticed an interesting fact: the time allocated to σ(p) is usually pretty low. Figure 2 reports the distribution of such each times. As can be seen, almost all the times are concentrated in the lower part of the graph: even if the maximum value is 1363 seconds, the mean is less than a minute (54.18 seconds to be precise) while the median value is significantly lower (9 seconds).

The results of Section 3.3 show that in a non-negligible number of cases the benefits of using a timesplit solver are tangible. Unfortunately, in such experiments for every instance we already knew the corresponding runtimes of each solver of the portfolio. The main motivation of this work is instead to try to predict and run the best timesplit solver for a new unseen instance. Regrettably, given runtime prediction of a solver is a non-trivial task, predicting the detailed solver behaviour on a new test instance is even harder. Indeed, in our case we can not simply limit ourselves to guess the best solver for a new instance, but we should instead predict a suitable timesplit solver [(s 1 , t 1 ), . . . , (s k , t k )]. Moreover, even if in most cases the TimeSplit algorithm works pretty well, on the others we noticed a considerable number of instances for which this algorithm is ineffective (or even harmful). Therefore, a successful strategy should be able not only to predict a proper timesplit solver, but also to distinguish between the instances for which the timesplit is actually useful and those where it is counterproductive. Furthermore, another interesting observation that has emerged from the results of Section 3.3 is that often for the "significant" timesplit solvers is sufficient to run the base of the schedule for a relatively low number of seconds in order to allow an effective improvement of the best solver.

On the basis of these observations and motivations, what we propose is therefore a generic and hybrid framework that we called Timesplit Portfolio Solver The underlying idea of TPS is to exploit for the first C seconds a fixed schedule calculated a priori, whose purpose is to produce as many good sub-optimal solutions as possible. If after C seconds the optimality is still not proven, in the remaining T -C seconds the algorithm D(p) tries to predict which is the best (timesplit) solver for p, that will be executed taking advantage of any upper bound provided by S. Since TPS is a general model that can be arbitrarily specialized, in the rest of the Section we explain in more detail what choices we made and what algorithms we used to define and evaluate (variants of) TPS.

Static Splitting

Drawing inspiration from what was done in [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF] for SAT problems, we decided to compute a static schedule of solvers according to the outcomes of TimeSplit on a given set of training instances. While in [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF] the authors solve a Resource Constrained Set Covering Problem (RCSCP) in order to get a schedule that maximizes the number of training instances that can be solved within a time limit of C = 180 seconds, in our case the objective is different. What we would like is indeed to compute a schedule that may act as a good base for the solver(s) who will be executed in the remaining T -C seconds. To do this, we first identify by means of TimeSplit algorithm the set ∆ * of all the training instances for which a timesplit solver outperforms the VBS. Let σ(p) = [(s p,1 , t p,1 ), . . . , (s p,k , t p,k )] be the schedule returned by TimeSplit on each p ∈ ∆ * . We look for a schedule S that maximizes the number of time slots t p,i ∈ σ(p) for i = 1, . . . , k -1 that are covered, that is the portfolio solver allocates at least t p,i seconds to solver s p,i . Again, note that we consider the base σ(p) instead of σ(p) since at this stage we are not interested in choosing the best solver: we want to determine an effective timesplit solver able to quickly find suitable sub-optimal solutions. However, a nice side-effect of this approach is that it also may be able to solve quickly those instances that are extremely difficult for some solvers but very easy for others.

For each p ∈ ∆ * , we define ∇ p = {(s p,i , t) | (s p,i , t p,i ) ∈ σ(p), t i ≤ t ≤ C} as the set of all the pairs (s p,i , t) that cover the time slot t p,i within C seconds. Named Π * = p∈∆ * {s ∈ Π : (s, t) ∈ ∇ p } the set of the solvers of the portfolio that appear in at least a ∇ p , and fixed C = T /10, we solve the following problem:

min   (C + 1) p∈∆ * yp + s∈Π * t∈[0,C] t xs,t   s.t. yp + (s,t)∈∇p xs,t ≥ 1 ∀p ∈ ∆ * s∈Π * t∈[0,C] t xs,t ≤ C yp, xs,t ∈ {0, 1} ∀p ∈ ∆ * , ∀s ∈ Π * , ∀t ∈ [0, C]
For each pair (s, t) there is a binary variable x s,t that will be equal to one if and only if in S the solver s will run for t seconds. For each problem p, the binary variable y p will be one if and only if S cannot cover any time slot of σ(p). Constraint y p + x s,t ≥ 1 imposes that instance p is covered (possibly setting y p = 1 in the worst case) while t x s,t ≤ C ensures that S will not exceed the time limit C. The objective is thus to minimize the number of uncovered instances first (by means of C + 1 coefficient for each y p ), and the total time of S then (using t coefficient for each x s,t ).

Note that the solution of the problem defines an allocation ξ = {(s, t) : x s,t = 1} and not actually a schedule: we still have to define the execution order of the solvers. Since the interaction between different solvers is not easily predictable, and neither generalizable, we decided to use a simple and reasonable heuristic: we get the schedule S by sorting each (s, t) ∈ ξ by increasing allocated time t.

Dynamic Splitting

Once defined the static part of TPS, we want to determine an algorithm D(p) able to predict for a new unseen instance p a proper (timesplit) solver to run for T -C seconds after [(S, C)]. Inspired by the results of [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF], we made use of the SUNNY algorithm [START_REF] Amadini | SUNNY: a Lazy Portfolio Approach for Constraint Solving[END_REF][START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF]. The reasons behind this choice are essentially two. First, even if originally designed for CSP portfolios [START_REF] Amadini | SUNNY: a Lazy Portfolio Approach for Constraint Solving[END_REF], the adaption of SUNNY for COPs turns out to perform well according to the results of [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF]. Second, SUNNY is not

p1 p2 p3 Total s1
(1, 150) (0.25, 1000) (0.75, 1000) (2, 2150) s2 (0, 1000)

(1, 10) (0, 1000) (1, 2010) s3

(1, 100) (0.75, 1000) (0.7, 1000) (2.45, 2100) s4 (0.75, 1000) (0.75, 1000) (0.25, 1000) (1.75, 3000) Table 3: Pairs (score, otime) of each solver s i for every problem p j . limited to predict a single solver but selects instead a schedule of the constituent solvers: in other terms, it implicitly returns a timesplit solver.

SUNNY is a new lazy algorithm portfolio originally tailored for CSPs: given a CSP p and a portfolio Π, it uses a k-NN algorithm to select from a set of training instances a subset N (p, k) of the k instances closer to p according to the Euclidean distance. Then, on-the-fly, it computes a schedule of solvers by considering the smallest sub-portfolio S ⊆ Π able to solve the maximum number of instances in the neighborhood N (p, k) and by allocating to each solver of S a time proportional to the number of solved instances in N (p, k). In [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] SUNNY was adapted in order to deal with COPs: this variant selects the sub-portfolio S ⊆ Π that maximizes the score in the neighborhood and allocates to each solver a time in [0, T ] proportional to its total score in N (p, k). In particular, while in the CSP version SUNNY allocates to a backup solver 4 an amount of time proportional to the number of instances not solved in N (p, k), in the COP version it assigns to it a slot of time proportional to k -h where h is the maximum score achieved by the sub-portfolio S. While for CSPs the final schedule is obtained by sorting the solvers by increasing solving time, for COPs the sorting is done by using increasing otime. In a nutshell, the underlying idea behind SUNNY is to minimize the probability of choosing the wrong solvers(s) by exploiting instance similarities in order to get the smallest possible schedule of solvers. Padding the uncovered instances of N (p, k) with the backup solver has the purpose of filling the "gray area" between the best sub-portfolio found and a virtual solver always able to find the optimal solution with the (hopefully) most reliable solver of Π. Of course, this is an arbitrary choice that biases the schedule toward the backup solver. But experimental results have proven the effectiveness of this approach.

Example 1. Let us suppose that Π = {s 1 , s 2 , s 3 , s 4 }, the backup solver is s 3 , T = 1000 seconds, k = 3, N (p, k) = {p 1 , p 2 , p 3 }, and the scores/optimization times are defined as listed in Table 3. The minimum size sub-portfolio that reaches the highest score h = 1 + 1 + 0.75 = 2.75 is {s 1 , s 2 }. On the basis of the sum of the scores reached by s 1 and s 2 in N (p, k) (resp. 2 and 1, see the last column of Table 3) we then determine a slot size of t = T /(2+1+(k-h)) = 307.69 seconds and assign t 1 = 2 * t = 615.38 seconds to s 1 and t 2 = 1 * t = 307.69 seconds to s 2 . The remaining t 3 = 1000 -(t 1 + t 2 ) = 76.93 seconds are finally allocated to the backup solver s 3 . The final schedule [(s 2 , t 2 ), (s 3 , t 3 ), (s 1 , t 1 )] is then obtained by sorting s 1 , s 2 , s 3 by their total optimization time in N (p, k) (i.e., 2010, 2100, and 2150 respectively: see the last column of Table 3).

In order to measure the performances of the TPS described in Sections 4.1 and 4.2, in the following referred to as sunny-tps, we considered a solving timeout of T = 1800 seconds, a threshold of C = 180 seconds, the portfolio Π = {Chuffed, CPX, G12/FD, G12/LazyFD, G12/Gurobi, G12/MIP, Gecode, MinisatID} and the dataset ∆ of 4864 MiniZinc instances introduced in Section 3.3.

We evaluated sunny-tps using a 10-fold cross validation [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]: ∆ was randomly partitioned in 10 disjoint folds ∆ 1 , . . . , ∆ 10 treating in turn one fold ∆ i as the test set TS i (i = 1, . . . , 10) and the union of the remaining folds j =i ∆ j as the training set TR i . For each training set TR i we then computed a corresponding static schedule [(S i , 180)] as explained in Section 4.1, and for every instance p ∈ TS i we computed and executed the timesplit solver [(S i , 180), (D i (p), 1620)] where D i (p) is the schedule returned by SUNNY algorithm for problem p using a reduced solving window of T -C = 1620 seconds.

Note that, for computing D i (p), SUNNY has to retrieve the k instances of TR i closest to p. In order to do so, a proper set of features has to be extracted from p (and each instance of TR i ). Instead of using the whole set of 155 features extracted by the mzn2feat tool described in [START_REF] Amadini | Features for Building CSP Portfolio Solvers[END_REF][START_REF] Amadini | An Enhanced Features Extractor for a Portfolio of Constraint Solvers[END_REF] (as in [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF]) we decided to select a proper subset of them by exploiting the new extractor mzn2feat-1.0. 5 This tool is a new version of mzn2feat designed to be more portable, light-weight, flexible, and independent from the particular machine on which it is run as well as from the specific global redefinitions of a given solver. Indeed, mzn2feat-1.0 does not compute features based on graph measures (since this process could be very time/space consuming), solver specific features (like global constraint redefinitions) and dynamic features (to decouple the extractor from a particular solver and from the given machine on which it is executed). In more detail, mzn2feat-1.0 extracts in total 95 features: the variables [START_REF] Xu | Hydra-MIP: Automated Algorithm Configuration and Selection for Mixed Integer Programming[END_REF], domains [START_REF] Kotthoff | Algorithm Selection for Combinatorial Search Problems: A Survey[END_REF], constraints [START_REF] Xu | Hydra-MIP: Automated Algorithm Configuration and Selection for Mixed Integer Programming[END_REF], and solving [START_REF]GECODE -An open, free, efficient constraint solving toolkit[END_REF] features are exactly the same of mzn2feat; the objective features (8) are the 12 objective features of [START_REF] Amadini | An Enhanced Features Extractor for a Portfolio of Constraint Solvers[END_REF] except the 4 features that involve graph measures; finally, the global constraints features are just 4 and no longer bound to the Gecode solver, namely: the number of global constraints n, the number of different global constraints m, the ratio m/n and the ratio n/c where c is the total number of constraints of the problem. We finally removed all the constant features and scaled them in [-1, 1], obtaining thus a reduced set of 88 features.

As in Section 2, we evaluated the average performance of sunny-tps in terms of score, proven, otime, area by varying the neighbourhood size k in {10, 15, 20}. Finally, we compared sunny-tps vs. the following approaches:

-SBS: is the overall Single Best Solver of Π according to the given metric; 6 -VBS: is the Virtual Best Solver of Π defined as in Section 3.3;

5 Available at http://www.cs.unibo.it/ ~amadini/mzn2feat-1.0.tar.bz2 6 Regarding the score, otime, and area metrics the single best solver of Π turned out to be CPX, while for the proven metric it is Chuffed. According to these results, we elected CPX as the backup solver of Π. sunny-ori: is the original SUNNY algorithm evaluated in [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF], that is a portfolio solver in which the selected solvers are executed independently (i.e., without any bounds communication) in the time window [0, T ] without the "warm start" provided by S for the first C seconds; sunny-com: is a portfolio solver that acts basically as sunny-ori, with the only exception that solvers execution is not independent: the best value found by a solver within its time slot is subsequently exploited by the following solver of the schedule.

The universe of all the (timesplit) solvers we used for our empirical evaluation was therefore Σ = Π ∪ {SBS, VBS, sunny-com, sunny-ori, sunny-tps}. It is worth nothing that, while in [START_REF] Amadini | An Empirical Evaluation of Portfolios Approaches for Solving CSPs[END_REF][START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] the evaluation was based on simulations of the portfolio approaches according to the already computed behaviours of every solver of Π on every instance of ∆, in this work all the approaches have been actually run and evaluated. Indeed, as shown also in Section 3.3, in this case we can not make use of simulations since the side effects of bounds communication are unpredictable in advance.

Test Results

The average score results (in percent) by varying the k parameter are reported in Figure 3a. The plot clearly shows a common pattern: SBS, sunny-ori, sunny-com, sunny-tps, and VBS are respectively sorted by increasing score for every value of k. In general, we can see a rather sharp separation between the various approaches: this witnesses the effectiveness of bounds communication for reaching a better score or, in other terms, for improving the objective value (possibly proving its optimality). For example, the percentage difference between sunny-ori and sunny-com ranges between 2.83% and 3.45%. Furthermore, running the static schedule for the first 180 seconds (and therefore shrinking the dynamic schedule of sunny-com in the remaining 1620 seconds) seems to be advantageous: sunny-tps is always better than SBS, sunny-ori, and sunny-com.

The peak performance (86.91%) is reached with k = 15, but the difference with k = 10 and 20 is minimal (0.73% and 0.59% respectively). Considering k = 15, sunny-tps has an average score higher than SBS by 10.55%, and lower than VBS by 6.9%. Moreover, in 82 cases (1.69% of ∆) it scores better than VBS. When considering the proven metric (Figure 3b) the performance difference between the different SUNNY approaches is not so pronounced. Indeed, sunny-ori, sunny-com, and sunny-tps are pretty close: for every k, the percentage difference between the worst and the best SUNNY approach ranges between 0.45% and 1.13%. In this case we can say that the remarkable difference in performance between the portfolio solvers and the SBS is mainly due to the SUNNY algorithm rather than the bounds communication. In other words, passing the bound is not so effective if we just focus on proving optimality. A possible explanation is that communicating an upper bound can be useful to find a better solution (see Figure 3a) but ineffective when it comes to prove optimality. In these cases probably the time needed by a solver to compute information for completing the search process can not be offset by the mere knowledge of an objective bound. Nonetheless, the plot shows how the "warm start" provided by the static schedule is helpful: in fact, the performance of sunny-tps is always better than the other approaches. The peak performance (k = 15) is 72.06%, about 10.36% more than SBS and only 3.74% less than VBS. For 27 instances (0.56% of ∆) sunny-tps is able to prove the optimality while VBS is not.

Let us now focus on optimization time. In Figure 4a we see, in contrast to all the score and proven results that appear to be pretty robust by varying k, a slight discrepancy between k = 10 and k > 10. This delay time in proving optimality is due to the scheduling order of the constituent solvers. However, for k = 15 the results improve and for k = 20 are substantially the same. The peak performance is achieved with k = 15 (272.61 seconds), 105.07 less than SBS and 145.9 more than VBS; in 53 cases (1.09% of ∆) sunny-tps is able to prove the optimality in less time than VBS.

The area results depicted in Figure 4b clearly show the benefits of bounds communication. First, note that sunny-ori is always worse than SBS: this is because each solver scheduled by sunny-ori is executed independently, and therefore for every solver the search is always (re-)started from scratch without exploiting previously found solutions. sunny-com significantly improves sunny-ori, even if its average area is very close to SBS (even worse for k = 10). On the other hand, the fixed schedule run by sunny-tps often allows one to quickly find partial solutions and thus to noticeably outperform both sunny-ori and sunny-com. Like the otime metric, the average area is not so close to VBS (the peak perfor-mance, with k = 15, is 272.61 seconds: 132.77 seconds more than VBS, and 114.9 less than SBS), but sunny-tps outperforms VBS in 110 cases (2.26% of ∆).

Conclusions and Future Work

In this work we addressed the problem of boosting optimization by exploiting the sequential cooperation of different COP solvers. Exploiting the fact that finding good solutions early can significantly improve optimization solvers, we first provided a proper TimeSplit algorithm that relies on the behaviour of different solvers on an instance for determining a good timesplit solver for this instance (i.e., ideally able to outperform the best solver of a portfolio). Our results show that on average the actual timesplit solver does perform similarly to (and sometimes even better than) the Virtual Best Solver of the portfolio. We therefore exploited the results of TimeSplit in order to define the Timesplit Portfolio Solver (TPS), a generic and hybrid framework that combines a static schedule (computed off-line and run for a limited time) as well as a dynamic schedule (computed on-line by means of a proper prediction algorithm and run in the remaining time) for solving a new unseen instance by exploiting the bounds communication between the scheduled solvers. In particular, on the one hand, we determined the static schedule by solving a Set Covering problem according to the results of TimeSplit on a set of training instances, and, on the other, we defined the dynamic selection by exploiting the SUNNY algorithm [START_REF] Amadini | SUNNY: a Lazy Portfolio Approach for Constraint Solving[END_REF][START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF]. Empirical results shows that this idea can be beneficial and sometimes even able to outperform the Virtual Best Solver according to different metrics that we introduced (namely, score, proven, otime, and area) in order to evaluate the performance of different (portfolio) solvers.

We see this work a cornerstone for portfolio approaches to solving Constraint Optimization Problems. Clearly bounds communication should be taken into account in this case. It is natural to think of extensions to this work, for example, one may try to maximize the ideal shift by considering all the constituent solvers instead of focusing just on improving the best one. Moreover, the nature of TPS naturally allows one to instantiate its generic schema with new algorithms and techniques (perhaps by simply adapting the most successful portfolio approaches of the SAT and CSP fields). For instance, one might study how to select the set of features to improve solver selection. Note that, contrary to [START_REF] Amadini | An Empirical Evaluation of Portfolios Approaches for Solving CSPs[END_REF][START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF], for example, significant experimentation is required since it is clearly not predictable in a deterministic way what the side effects of transmitting bounds from a solver to another are. Finally, other interesting directions concerns the study of parallel timesplit solvers as well as the communication of not only the objective bounds but also other additional information (such as for instance cuts which is common in SAT portfolios).

Fig. 1 :

 1 Fig. 1: Examples of solving behaviours and corresponding time splitting σ.

Fig. 2 :

 2 Fig. 2: Times allocated to σ(p).

  (TPS). When a new instance p arrives, we compute and run on p a corresponding timesplit solver TPS(p) = [(S, C), (D(p), T -C)], where [(S, C)] is a static timesplit solver pre-computed off-line that will run for C < T seconds, while for the remaining T -C seconds we execute a dynamic timesplit solver [(D(p), T -C)] computed on-line by means of a given prediction algorithm D(p)

  score results (in percent).

  proven results (in percent).

  otime results (in seconds).

  area results (in seconds).

Table 1 :

 1 Average performances.

		score proven otime	area		VBS TimeSplit TS-2
	VBS	82.40% 34.73% 1298.67 478.05	VBS	-	222	232
	TimeSplit 80.49% 33.67% 1263.74 347.91	TimeSplit 373	-	40
	TS-2	80.60% 33.89% 1259.98 343.97	TS-2	364	13	-

Table 2 :

 2 Pairwise Comparisons.

We can convert a maximization problem to a minimization problem by simply negating the objective function.

A backup solver is a special solver of the portfolio (typically, its single best solver ) aimed to handle exceptional circumstances (e.g.,premature failures of other solvers).

Acknowledgments NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program. This work was partially supported by Asian Office of Aerospace Research and Development grant 12-4056.