Roberto Amadini

Maurizio Gabbrielli

Jacopo Mauro

Under consideration for publication in Theory and Practice of

Keywords: Algorithms Portfolio, Artificial Intelligence, Constraint Satisfaction, Machine Learning

Within the context of constraint solving, a portfolio approach allows one to exploit the synergy between different solvers in order to create a globally better solver. In this paper we present SUNNY: a simple and flexible algorithm that takes advantage of a portfolio of constraint solvers in order to computewithout learning an explicit model -a schedule of them for solving a given Constraint Satisfaction Problem (CSP). Motivated by the performance reached by SUNNY vs. different simulations of other state of the art approaches, we developed sunny-csp, an effective portfolio solver that exploits the underlying SUNNY algorithm in order to solve a given CSP. Empirical tests conducted on exhaustive benchmarks of MiniZinc models show that the actual performance of sunny-csp conforms to the predictions. This is encouraging both for improving the power of CSP portfolio solvers and for trying to export them to fields such as Answer Set Programming and Constraint Logic Programming.

Introduction

Constraint Programming (CP) is a declarative paradigm that enables expressing relations between different entities in the form of constraints that must be satisfied. One of the main goals of CP is to model and solve Constraint Satisfaction Problems (CSP) [START_REF] Mackworth | Consistency in Networks of Relations[END_REF] as well as problems like the well-known Boolean satisfiability problem (SAT), Quantified Boolean Formula (QBF), Satisfiability Modulo Theories (SMT), and Answer-Set Programming (ASP). One of the more recent trends of CP -especially in the SAT field -is trying to solve a given problem by using a portfolio approach [START_REF] Rice | The Algorithm Selection Problem[END_REF][START_REF] Gomes | Algorithm portfolios[END_REF].

A portfolio approach 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, dubbed a 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 comes, the portfolio solver tries to predict which are the best constituent solvers s 1 , . . . , s k (with 1 ≤ 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 (ML) techniques. Exploiting the fact that different solvers are better at solving different problems, portfolios have proved to be particularly effective. For example, the overall winners of international solving competitions like the SAT Competition (2013) and CSP Competition (2009) are often portfolio solvers.

Surprisingly, despite their proven effectiveness, portfolio solvers are rarely used in practice and usually restricted to the SAT field. Outside the SAT world there are indeed only few applications of portfolios: for example, [START_REF] Gebser | A Portfolio Solver for Answer Set Programming: Preliminary Report[END_REF] for ASP, [START_REF] Omahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF] for CSP, and [START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF] for optimization problems like the Traveling Salesman Problem. On the other hand, if we exclude competitive scenarios such as the SAT Competitions, even the SAT portfolio solvers are actually underutilized. As pointed out also by [START_REF] Samulowitz | Snappy: A simple algorithm portfolio[END_REF], we think that one of the main reasons for this incongruity lies in the fact that state of the art portfolio solvers usually require a complex off-line training phase and they are not suitably structured to incrementally exploit new incoming information. For instance, a state of the art SAT solver like SATzilla [START_REF] Xu | SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT[END_REF]) requires a model built by exploiting a weighted Random Forest machine learning approach while 3S [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF], ISAC [START_REF] Malitsky | Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation[END_REF], and CHSC [START_REF] Malitsky | Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering[END_REF] during their off-line phase cluster the instances of a training set or solve non-trivial combinatorial problems for computing an off-line schedule of the solvers.

In order to use these solvers a suitable set of training instances must be found and, especially, the off-line phase has to be run on all the training samples. Moreover, new information (e.g., incoming problems, solvers, features) may imply a re-running of the whole off-line process.

In the literature some approaches avoiding a heavy off-line training phase have been studied [START_REF] Wilson | Case-Based Recommender Components for Scientific Problem-Solving Environments[END_REF][START_REF] Pulina | A Multi-engine Solver for Quantified Boolean Formulas[END_REF][START_REF] Omahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF][START_REF] Nikolic | Instance-Based Selection of Policies for SAT Solvers[END_REF][START_REF] Gebruers | Making Choices Using Structure at the Instance Level within a Case Based Reasoning Framework[END_REF][START_REF] Stern | Collaborative expert portfolio management[END_REF][START_REF] Samulowitz | Snappy: A simple algorithm portfolio[END_REF]. As pointed out in the comprehensive survey by [START_REF] Kotthoff | Algorithm Selection for Combinatorial Search Problems: A Survey[END_REF], these approaches are also referred as lazy. Unfortunately, to the best of our knowledge, among these lazy approaches only CPHydra [START_REF] Omahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF] was successful enough to win a solver competition in 2008. Recently, however, Amadini et al. (2013a) showed that some non-lazy approaches derived from SATzilla [START_REF] Xu | SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT[END_REF]) and 3S [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF] have better performance than CPHydra on CSPs.

Our goal is, on one hand, bridging the gap between SAT and CSP portfolio solvers, and, on the other hand, encouraging the dissemination and the utilization in practice of portfolio solvers even in other growing fields such as, for example, the Answer-Set Programming and Constraint Logic Programming paradigms where a few portfolio approaches have been studied (see for example [START_REF] Gebser | A Portfolio Solver for Answer Set Programming: Preliminary Report[END_REF]). As a first step in this direction, in this paper we present SUNNY and sunny-csp.

SUNNY is a lazy algorithm portfolio which exploits instances similarity to guess the best solver(s) to use. For a given instance i, SUNNY uses a k-Nearest Neighbors (k-NN) algorithm to select from a training set of known instances the subset N(i, k) of the k instances closer to i. Then, it creates a schedule of solvers considering the smallest sub-portfolio able to solve the maximum number of instances in the neighborhood N(i, k). The time allocated to each solver of the subportfolio is proportional to the number of instances it solves in N(i, k). We performed a preliminary evaluation of the performance of SUNNY by exploiting a large benchmark of CSPs from each of which we extracted an exhaustive set of features (e.g., number of constraints, number of variables, domain sizes) used to estimate the instances similarity. Following the methodology of Amadini et al. (2013a), we measured the performance of SUNNY by comparing its expected behavior against the simulations of state of the art portfolio solvers, namely, CPHydra, 3S, and SATzilla.

The performance of SUNNY were promising: it overcame all the above mentioned approaches. We therefore developed sunny-csp, a new CSP portfolio solver built on the top of the SUNNY algorithm. Using the very same benchmarks and features sets, we compared the actual results of sunny-csp w.r.t. its expected performance, that is the ideal performance of the underlying SUNNY algorithm. Test results show that the difference between simulated and actual behavior is minimal, thus encouraging new insights, extensions and implementations of this simple but effective algorithm.

Paper structure. In Section 2 we describe the motivations and the algorithm underlying SUNNY while in Section 3 we explain the methodology and we report the results of our comparisons. In Section 4 we introduce the CSP portfolio solver sunny-csp as well as an empirical validation of its performance. In Section 5 we discuss the related literature while Section 6 concludes by discussing also future work.

SUNNY

One of the main empirical observations at the base of SUNNY is that usually combinatorial problems are extremely easy for some solvers and, at the same time, almost impossible to solve for others. Moreover, in case a solver is not able to solve an instance quickly, it is likely that such solver takes a huge amount of time to solve the instance. A first motivation behind SUNNY is therefore to select and schedule a subset of the solvers of a portfolio instead of trying to predict the "best" one for a given unseen instance. This strategy hopefully allows one to solve the same amount of problems minimizing the risk of choosing the wrong solver.

Another interesting consideration is that the use of large portfolios might not always lead to performance boost. In some cases the overabundance of solvers hinders the effectiveness of the considered approach. Indeed, selecting the best solver to use is more difficult when a big size portfolio is considered since there are more available choices. Despite the literature having examples of portfolios consisting of nearly 60 solvers [START_REF] Nikolic | Instance-Based Selection of Policies for SAT Solvers[END_REF], as pointed out by Amadini et al. (2013a;[START_REF] Pulina | A self-adaptive multi-engine solver for quantified boolean formulas[END_REF] usually the best results are obtained by adopting a relatively small portfolio (e.g., ten or even less solvers).

Another motivation for SUNNY is that -as witnessed for instance by the good performance reached by CPHydra, ISAC [START_REF] Kadioglu | ISAC -Instance-Specific Algorithm Configuration[END_REF]), 3S, CSHC [START_REF] Malitsky | Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering[END_REF]) -the 'similarity assumption', stating that similar instances will behave similarly, is often reasonable. It thus makes sense to use algorithms such as k-NN to exploit the closeness between different instances. As a side effect, this allows to relax the off-line training phase that, as previously stated, makes the majority of the portfolio approaches rarely used in practice.

Starting from these assumptions and driven by these motivations we developed SUNNY, a lazy portfolio approach for constraint solving.

Algorithm

Let us explain in more detail the specifications of the algorithm. SUNNY is the acronym of:

• SUb-portfolio: for a given instance, we select a suitable sub-portfolio (i.e., a subset of the constituent solvers of the portfolio) to run; • Nearest Neighbor: to determine the sub-portfolio we use a k-NN algorithm that extracts from previously seen instances the k instances that are the closest to the instance to be solved; • lazY: no explicit prediction model is built off-line.

In a nutshell, the underlying idea behind SUNNY is therefore to minimize the probability of choosing the wrong solvers(s) by exploiting instance similarities in order to quickly get the smallest possible schedule of solvers. The pseudo-code of SUNNY is presented in Listing 1. SUNNY takes as input the problem inst to be solved, the portfolio of solvers solvers, a backup solver bkup solver,1 a parameter k (≥ 1) representing the size of the neighborhood to consider, a parameter T representing the total time available for running the portfolio solver, and a knowledge base KB of known instances for each of which we assume to know the features and the runtimes for every solver of the portfolio.

When a new unseen instance inst comes, SUNNY first extracts from it a proper set of features via the function getFeatures (line 2). This function takes as input also the knowledge base KB since the extracted features need to be preprocessed in order to scale them in the range [-1, 1] and to remove the constant ones. getFeatures returns the features vector feat vect of the instance inst. In line 3, function getNearestNeigbour is used to retrieve the k nearest instances similar insts to the instance inst according to a certain distance metric (e.g., Euclidean). Then, in line 4 the function getSubPortfolio selects the minimum subset of the portfolio that allows to solve the greatest number of instances in the neighborhood, by using the average solving time for tie-breaking. 2Once computed the sub-portfolio, we partition the time window [0, T] into slots equal time slots of size T/slots, where slots is the sum of the solved instances for each solver of the sub-portfolio plus the instances of similar insts that can not be solved within the time limit T. In order to compute slots, we use the function getMaxSolved(s, similar insts, KB, T) that returns the number of instances in similar insts that a solver (or a portfolio of solvers) s is able to solve in time T. In lines 9-10 the associative array schedule, used to define the solvers schedules, is initialized. In particular, schedule[s] = t iff a time window of t seconds is allocated to the solver s.

The loop enclosed between lines 11-14 assigns to each solver of the portfolio a number of time slots proportional to the number of instances that such solver can solve in the neighborhood. In lines 15-16 the remaining time slots, corresponding to the unsolved instances, are allocated to the backup solver. Finally, line 17 returns the final schedule, obtained by sorting the solvers by average solving time in similar insts.

Example

Let us suppose that solvers = {s 1 , s 2 , s 3 , s 4 }, bkup solver = s 3 , T = 1800 seconds, k = 5, similar insts = {p 1 , ..., p 5 }, and the run-times of the problems defined by KB as listed in Table 1. The minimum size sub-portfolios that allow to solve the most instances (i.e., four instances) are {s 1 , s 2 , s 3 }, {s 1 , s 2 , s 4 }, and {s 2 , s 3 , s 4 }. SUNNY selects sub portfolio = {s 1 , s 2 , s 4 } since it has a lower average solving time (1270.4 sec., to be precise). Since s 1 and s 4 solve 2 instances, s 2 solves 1 instance and p 1 is not solved by any solver within T seconds, the time window [0, T] is partitioned in 2 + 2 + 1 + 1 = 6 slots: 2 assigned to s 1 and s 4 , 1 slot to s 2 , and 1 to the backup solver s 3 . After sorting the solvers by average solving time in the neighborhood we get the schedule illustrated in Table 2.

p 1 p 2 p 3 p 4 p 5 s 1 T T 3 T 278 s 2 T 593 T T T s 3 T T 36 1452 T s 4 T T T 122 60
Clearly, the proposed algorithm features a number of degrees of freedom. For instance, the underlying k-NN algorithm depends on the quality of the features extracted (and possibly filtered), on the choice of the k parameter, and on the distance metric adopted.

A potential weakness of SUNNY is that it could become impracticable for large portfolios. Indeed, in the worst case, the complexity of getSubPortfolio is exponential w.r.t. the portfolio size. However, the computation of this function is almost instantaneous for portfolios containing up to 15 solvers and, as later detailed, from an empirical point of view the sizes of the subportfolios are small for reasonable values of k.

Finally, let us note that the assignment of the uncovered instances of N(p, k) with the backup solver allows the assignment of some slots to (hopefully) the most reliable solver. This choice obviously biases the schedule toward the backup solver, but experimental results have proven the effectiveness of this approach.

Validation

Taking as baseline the methodology and the results of Amadini et al. (2013a) in this section we present the main ingredients and the procedure that we have used for conducting our experiments and for evaluating the portfolio approaches, as well as the obtained experimental results. We would like to point out that, in order to reduce the computational costs, the results of this Section are based on simulations. We computed the running times of all the solvers of the portfolio just once and used this information to evaluate the performance of every approach on every instance of the test set. To conduct the experiments we used Intel Dual-Core 2.93GHz computers with 3 MB of CPU cache, 2 GB of RAM, and Ubuntu 12.04 operating system. For keeping track of the solving times we considered the CPU time by exploiting the Unix time command.

Solvers, Dataset, and Features

In order to evaluate the sensitivity of the proposed approaches w.r.t. the use of different solvers, we built portfolios of different size by considering all the publicly available and directly usable solvers of the MiniZinc Challenge 2012, namely: BProlog, Fzn2smt, CPX, G12/FD, G12/Lazy-FD, G12/MIP, Gecode, izplus, MinisatID, Mistral and OR-Tools. We used all of them with their default parameters, their global constraint redefinitions when available, and keeping track of their performances within a timeout of T = 1800 seconds. 3To conduct our experiments on a dataset of instances as realistic and large as possible we considered the dataset used in Amadini et al. (2013b). This dataset was obtained by combining 1650 instances gathered from the MiniZinc 1.6 benchmarks, 6 instances from the MiniZinc challenge 2012, and 6944 instances from the International Constraint Solver Competitions (ICSC) of 2009, discarding the "easiest" instances (i.e., those solved by Gecode in less than 2 seconds) and the "hardest" ones (i.e., those for which the features extraction has required more than T /2 = 900 seconds). The benchmark thus obtained consisted of 4642 instances (3538 from ICSC, 6 from MiniZinc Challenge 2012, and 1098 from MiniZinc 1.6 benchmarks).

For every instance of the benchmark we have extracted a set of 155 different features by exploiting the tool mzn2feat (Amadini et al. 2014a). Among the extracted features, 144 were static, i.e., obtained by parsing the source problem instance while 11 were dynamic, i.e., obtained by running the Gecode solver for a short run of 2 seconds. For further details about the benchmark and the features we refer the interested reader to Amadini et al. (2013b).

Following what is usually done by the majority of current approaches, we removed all the constant features and we scaled their values in the range [-1, 1]. In this way we ended up with a reduced set of 114 features.

Portfolios Composition, Approaches, and Evaluation

After having run every solver on each instance of the benchmark, by using a timeout of T = 1800 seconds and by keeping track of all the runtimes, we built fixed portfolios of different size m = 2, . . . , 11. More specifically, for m = 2, . . . , 11 the portfolio composition was computed by considering the portfolio of size m which maximized the number of potential solved instances (possible ties were broken by minimizing the average solving time). Among all the constituent solvers, we elected MinisatID (de Cat et al. 2013) as a backup solver, since it is the one that solved the greatest number of instances within the time limit T .

For each of such portfolios we then compared the performances of SUNNY against some of the most effective portfolio approaches. As done in Amadini et al. (2013a), we reproduced the approaches of SATzilla, 3S, and CPHydra. Note that, since 3S and SATzilla are portfolio approaches tailored for SAT, we had to reimplement these approaches, adapting them to our purposes. 4 In order to reproduce the CPHydra approach, we used its original algorithm without any parameter tuning. However, since CPHydra does not scale very well w.r.t. the size of the portfolio,5 we did not consider for the simulations the time taken to compute the schedule of the solvers to use. Thus, the results of CPHydra presented in this paper can be considered only an upper bound of its real performances.

In order to validate and test every approach on each portfolio, by following a common practice we used a 5-repeated 5-fold cross validation [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]. The benchmark was randomly partitioned in 5 disjoint folds ∆ 1 , . . . , ∆ 5 treating in turn one fold ∆ i , for i = 1, . . . , 5, as the test set and the union of the remaining folds j =i ∆ j as the training set. To avoid possible overfitting problems we repeated the random generation of the folds for 5 times, thus obtaining 25 different training sets (consisting of about 3714 instances each) and 25 test sets (consisting of about 928 instances). For every instance of every test set we then computed the solving strategy proposed by the particular portfolio approach and we simulated it using a time cap of 1800 seconds. For estimating the solving time we have taken into account also the time needed for extracting the features. We finally evaluated the performances of every approach in terms of Average Solving Time (AST) and Percentage of Solved Instances (PSI). When a portfolio strategy was not able to solve an instance, we set its solving time to the time cap T .

Test Results

Before comparing SUNNY against all the other approaches, we performed a sensitivity analysis by tuning the k parameter. As depicted in Fig. 1a the robustness of SUNNY is reflected by the fact that varying the value of k in [5, 20] does not entail a huge impact in performance (i.e., less than 1% of solved instances). The peak performance (PSI = 77.81%) is reached with k = 16, while for k > 20 we observed a gradual performance degradation. For instance, by using k = 25, 50, 100, 250, 500 we get a maximum PSI of 77.59, 77.55, 77.3, 77.16, 76.56, and 72.63 respectively (see Figure 1b). Of course, the robustness of SUNNY also depends on other factors: for instance, by using different sets of solvers or instances these assessments may be no longer be true.

We then selected the version of SUNNY with k = 16 as the best one and we compared it against 3S, SATzilla, and CPHydra approaches in terms of Percentage of Solved Instances (PSI) and Average Solving Time (AST). As a baseline, we considered the performances of the Virtual Best Solver (VBS), an 'oracle' portfolio solver which always selects the best solver for a given instance. As shown in Fig. 2, SUNNY turns out to be the best among all other approaches. Indeed, it can reach peaks of 77.81% solved instances against the 76.86% of 3S, the 75.85% of SATzilla, and the 73.21% of CPHYdra. If compared with the Single Best Solver (SBS), i.e., the best constituent solver in terms of number of solved instances,6 SUNNY is able to close up to the 93.38% of the gap between it and the VBS. Moreover, the performances of SUNNY do not degrade at the increase of the portfolio size. Indeed the best performance of SUNNY, both in terms of PSI and AST, is reached using a portfolio of 11 solvers.

no presolver selection or other parameters tuning was performed. To reproduce 3S, instead of using the original column generation method [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF], we solved the scheduling problem imposing an additional constraint that requires every solver to be run for an integer number of seconds. No parameter tuning was performed even in this case. For more details we defer the interested reader to Amadini et al. (2013a). As depicted in Fig. 3a, the size of the sub-portfolios computed by SUNNY is usually small: their average is between 1.21 and 1.44. This means that it may be reasonable to limit the subportfolio size without compromising the overall performances. A further study of this issue is left as a future work.

We believe that the reasons behind the good performance of SUNNY lie in the quality of the features extracted as well as in the selection criteria of the schedules it computes. For example, Fig. 3b shows the comparison of SUNNY against two other baselines: KNN and EQU. KNN is the portfolio approach that for every instance selects the solver that solves more instances in the neighborhood, using the solving time for tie-breaking. EQU is instead an approach that simply allocates to every constituent solver of the portfolio an equal amount of time [START_REF] Pulina | A self-adaptive multi-engine solver for quantified boolean formulas[END_REF]. Fig. 3b shows that, fixing the neighborhood size to 16, the performances of these two approaches are significantly worse w.r.t. to the peak performances of SUNNY.

sunny-csp

The results so far described are based on simulations. We decided to simulate the approaches because running every portfolio solver on each fold/repetition would take a tremendous amount of time (i.e., every single approach needs to be validated on 4642 * 5 = 23210 instances). Clearly, it is legitimate to ask if these simulations are faithful. Discrepancies may arise from factors not considered in the simulation like, for instance, the presence of memory leaks, solvers erratic behaviors, or solver faults. Moreover, since some of the features are dynamic, executing again the feature extraction process may lead to slightly different features that may cause a deviance on the expected performance.

Driven by these motivations, we therefore decided to develop and test sunny-csp: a CSP portfolio built on the top of the SUNNY algorithm. sunny-csp essentially uses the pseudo-code of Listing 1 exploiting the features extractor described in Amadini et al. (2014a). Taking as ref-erence the results of Section 3, sunny-csp implements SUNNY by setting k = 16, by exploiting a portfolio of 11 solvers (i.e., all the solvers listed in paragraph 3.1), and by using MinisatID as a backup solver. If a scheduled solver prematurely terminates its execution, sunny-csp assigns the remaining time to the next scheduled solver if any, otherwise it iteratively selects the solver not yet executed that solves the greatest number of instances of the training set, until either the instance is solved or the timeout expires. In order to measure and compare the actual performance of sunny-csp w.r.t. its simulated performance we used the same training sets, the same timeout, and the same machines adopted for the simulations.

Table 3 reports a comparison between the simulated (i.e., ideal) performance of SUNNY and the actual performance of sunny-csp for each repetition and fold in terms of PSI and AST. As one can see, the real performance are very close to the expected ones. In particular, sunny-csp solves on average only 0.07% instances less than predicted (see Table 4). There are cases in which it is also better than expected (see repetition 4 of Table 4). Looking at the AST statistics (Table 5), we noted a substantial equivalence between the two approaches (even if on average sunny-csp is slightly better, a mean difference of 1.78 seconds appears quite insignificant). In conclusion we have shown that sunny-csp performance are basically equivalent to the expected peak performance of SUNNY. In particular, focusing on the individual performance of the constituent solvers we can argue that sunny-csp is on average able to solve 26.11% instances more than the Single Best Solver, with an average solving time of 382.59 seconds less.

The source code of sunny-csp, as well as of the scripts we used to conduct the experiments, is fully available and downloadable at http://www.cs.unibo.it/ ~amadini/iclp_2014.zip.

Related Work

Portfolios approaches have been used in different areas ranging from SAT to Constraint Optimization Problems (COPs) like Mixed Integer Programming, Scheduling, Most Probable Explanation (MPE) and Travel Salesman Problem (TSP). For a survey of the different portfolio approaches studied in the literature we defer the interested reader to the comprehensive surveys by [START_REF]Cross-disciplinary perspectives on meta-learning for algorithm selection[END_REF][START_REF] Kotthoff | Algorithm Selection for Combinatorial Search Problems: A Survey[END_REF][START_REF] Hutter | Algorithm Runtime Prediction: The State of the Art[END_REF] or more specifically to Amadini et al. (2013a) for CSPs, to [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF] for COPs, and to [START_REF] Gebser | A Portfolio Solver for Answer Set Programming: Preliminary Report[END_REF] for ASP. Here we focus just on the most promising sequential approaches (i.e., winners of SAT and CSP competitions) not considering, for instance, parallel portfolio approaches where more than one solver is run concurrently.

CPHydra [START_REF] Omahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF]) is currently the only CSP solver which uses a portfolio approach. For the feature extraction it uses the code of Mistral, one of its constituent solvers, extracting from every instance 36 static and dynamic features. A k-nearest neighbor algorithm is used in order to compute a schedule of solvers which maximizes the chances of solving an instance within a time-out of 1800 seconds. The schedule is computed solving an optimization problem that is NP-hard. Nevertheless, CPHydra was able to win the 2008 International CSP Solver Competition. Unfortunately, a direct comparison between CPHydra and sunny-csp is not immediately possible since CPHydra process only instances encoded in the (old) input format XCSP, it uses solvers not maintained anymore, and it does not provide an API to change the training sets used for compute the schedule. Despite the similarities between CPHydra and sunny-csp, there are however some notable differences. Apart for the simulated performance gap in terms of PSI (sunny-csp can solve almost 5% instances more than the simulation of CPHydra), CPHydra does not try to minimize the AST since -conversely to SUNNY -it doesn't use any heuristic to determine the order of the solvers to be run. 7SATzilla [START_REF] Xu | SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT[END_REF]) is a SAT solver that relies on runtime prediction models to select the solver that (hopefully) has the fastest running time on a given problem instance. Its last version [START_REF] Xu | SATzilla2012: Improved algorithm selection based on cost-sensitive classification models[END_REF], which consistently outperforms the previous ones, uses a weighted random forest approach provided with an explicit cost-sensitive loss function punishing misclassifications in direct proportion to their impact on portfolio performance. SATzilla won the 2012 SAT Challenge in the Sequential Portfolio Track.

3S [START_REF] Kadioglu | Algorithm Selection and Scheduling[END_REF]) is instead a SAT solver that conjugates a fixed-time static solver schedule with the dynamic selection of one long-running component solver. 3S solves the scalability issues of CPHydra because the scheduling is computed offline and covers only 10% of the time limit. If a given instance is not yet solved after the short runs, a designated solver is chosen at runtime (using a k-nearest neighbors algorithm) and executed. 3S originally used a portfolio of 21 SAT solvers and was the best-performing dynamic portfolio at the International SAT Competition 2011.

More recently, a brand new portfolio approach was proposed by [START_REF] Malitsky | Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering[END_REF]. This portfolio improves 3S by using its schedule for 10% of the available time and then runs for the remaining time a solver selected based on a Cost-Sensitive Hierarchical Clustering (CSHC). The CSHC solver won 2 gold medals in the last SAT competition 2013. Clearly, an evaluation of CSHC -properly adapted to CSP -is in our interest for its comparison w.r.t. SUNNY.

Unfortunately, this has not been immediately possible since the code of CSHC was not publicly available.

The ASP field present a lot of similarities w.r.t. the state of research in the CSP field. Despite the development of portfolios is not as well studied as in SAT, there exist some portfolio approaches. [START_REF] Maratea | The Multi-Engine ASP Solver me-asp[END_REF] developed ME-ASP, a multi-engine solver for propositional ASP programs that apply ML techniques in order to inductively choose the "best" constituent solver to be run. Analogously on what done by the configuration tool ISAC [START_REF] Kadioglu | ISAC -Instance-Specific Algorithm Configuration[END_REF] for SAT problems, some works try instead to exploit algorithms portfolio to optimally tune the parameters of ASP solvers. In particular, in [START_REF] Gebser | A Portfolio Solver for Answer Set Programming: Preliminary Report[END_REF] the solver clasp is improved by using Support Vector Regression for choosing a good configuration. A framework that allows to learn and use domain-specific heuristics for choice-point selection is instead presented in [START_REF] Balduccini | Learning and using domain-specific heuristics in asp solvers[END_REF] for improving the performance of SMODEL solver.

Related to SUNNY is also the work presented by [START_REF] Hoos | aspeed: ASP-based Solver Scheduling[END_REF] which devises an approach that takes advantage of the modeling and solving capacities of ASP to automatically determine a schedule from existing benchmarking data without rely on any domain-specific features.

Conclusions and Extensions

In this work we presented SUNNY, a simple yet effective algorithm portfolio that, without explicitly building and learning any specific model, allows one to compute a sequential schedule of the constituent solvers of a portfolio for solving a given CSP.

Despite its simplicity, preliminary results have shown that this approach is promising and can even outperform the state of the art CSP portfolio techniques. To get a more realistic comparison we implemented sunny-csp, a CSP portfolio solver that exploits the SUNNY algorithm in order to solve a given MiniZinc instance by using a portfolio of 11 solvers. Empirical evidences confirm both the effectiveness of SUNNY and the potential benefits of using a portfolio of solvers: indeed, sunny-csp greatly outperforms each of its constituent solvers.

In view of the promising preliminary results, the possible extensions of SUNNY are manifold. First, its flexibility and usability may naturally lead to build effective portfolios also outside the CSP domain. In fact, SUNNY may be easily adapted to other domains such as SAT and ASP. As an example, SUNNY performs well even when adapted to Constraint Optimization Problems [START_REF] Amadini | Portfolio Approaches for Constraint Optimization Problems[END_REF]. Moreover, even if in this work we focused only on sequential portfolios, the scheduling-based approach of SUNNY is well suited for the construction of parallel portfolios. An interesting future direction may be to consider the impact of choosing different features and/or distance metrics for the k-NN algorithm.

Constraint Logic Programming (CLP) can exploit the speed up of the search of solution provided by SUNNY. Indeed, by adapting the same techniques described in [START_REF] Cipriano | Compiling and executing declarative modeling languages to gecode[END_REF], from a CLP problem it is possible to derive a MiniZinc instance that can be solved by sunny-csp.

Another interesting direction is to dynamize SUNNY algorithm in order to make it an online portfolio approach. Currently, SUNNY is indeed based on a static and pre-computed knowledge base. A possible extension consists in allowing the dynamic update of the knowledge base, thus exploiting new incoming information such as new instances, solvers, or features.

Finally, we are planning to improve the usability and the portability of sunny-csp, extending it to the resolution of also optimization problems in order to possibly enrolling it to a MiniZinc Challenge.

  Minimum, maximum, and average of the PSI reached by SUNNY on all the considered portfolios, by ranging the k parameter in [1, 20].

  PSI of SUNNY with k = 16, 20, 25, 50, 100, 250.

Fig. 1 :

 1 Fig. 1: PSI of SUNNY varying the k parameter.

  Percentage of Solved Instances.

Fig. 2 :

 2 Fig. 2: Performances of SUNNY, 3S, SATzilla, and CPHYdra.

  Performances of KNN and EQU against SUNNY (k = 16).

Fig. 3 :

 3 Fig. 3: SUNNY sub-portfolio sizes and comparison against KNN and EQU.

Table 1 :

 1 Runtimes (in seconds). T indicates solver timeouts.

	S 4	S 1	S 3	S 2
	0	600	1200	1500 1800
		Time [sec.]

Table 2 :

 2 Resulting schedule of the solvers.

Table 3 :

 3 sunny-csp ideal and actual performance for each repetition and fold.

			IDEAL		ACTUAL	ACTUAL -IDEAL
	Rep. Fold	PSI	AVG	PSI	AVG	PSI	AVG
	1	1	75.78		75.24		-0.54
	1	2	78.69		78.15		-0.54
	1	3	78.77		78.77		0.00
	1	4	78.13		78.23		0.11
	1	5	78.23	77.92	78.13	77.70	-0.11	-0.22
	2	1	78.90		79.22		0.32
	2	2	76.64		76.53		-0.11
	2	3	78.77		78.77		0.00
	2	4	78.56		77.80		-0.75
	2	5	76.08	77.79	76.08	77.68	0.00	-0.11
	3	1	78.79		78.69		-0.11
	3	2	76.32		76.32		0.00
	3	3	78.56		78.13		-0.43
	3	4	78.13		78.66		0.54
	3	5	77.37	77.83	77.16	77.79	-0.22	-0.04
	4	1	78.04		78.04		0.00
	4	2	75.35		75.78		0.43
	4	3	78.66		78.56		-0.11
	4	4	78.23		78.23		0.00
	4	5	78.02	77.66	77.91	77.70	-0.11	0.04
	5	1	77.93		78.04		0.11
	5	2	78.36		78.47		0.11
	5	3	77.05		76.94		-0.11
	5	4	78.56		78.45		-0.11
	5	5	77.26	77.83	77.05	77.79	-0.22	-0.04
			Total Average 77.81 Total Average 77.73 Total Average -0.07

Table 4 :

 4 Percentage of Solved Instances.

			IDEAL		ACTUAL	ACTUAL -IDEAL
	Rep. Fold	AST	AVG	AST	AVG	AST	AVG
	1	1	610.03		618.39		8.37
	1	2	561.75		567.91		6.16
	1	3	545.77		549.88		4.11
	1	4	550.57		545.54		-5.04
	1	5	571.98	568.02	572.29	570.80	0.31	2.78
	2	1	564.72		559.29		-5.43
	2	2	577.05		581.86		4.81
	2	3	540.97		537.76		-3.21
	2	4	557.87		565.39		7.52
	2	5	608.41	569.80	602.52	569.36	-5.89	-0.44
	3	1	561.18		557.79		-3.39
	3	2	609.80		607.50		-2.30
	3	3	564.97		568.77		3.80
	3	4	556.06		542.47		-13.60
	3	5	560.65	570.53	555.87	566.48	-4.78	-4.05
	4	1	566.71		571.09		4.38
	4	2	599.00		589.31		-9.68
	4	3	551.58		549.03		-2.55
	4	4	581.12		578.40		-2.71
	4	5	552.34	570.15	549.28	567.42	-3.06	-2.73
	5	1	571.06		566.74		-4.32
	5	2	558.51		557.11		-1.41
	5	3	580.12		579.47		-0.66
	5	4	581.40		570.17		-11.23
	5	5	568.84	571.99	564.09	567.51	-4.75	-4.47
			Total Average 570.10 Total Average 568.32 Total Average -1.78

Table 5 :

 5 Average Solving Time.

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

In order to compute the average solving time, we assign to an instance not solved within the time limit T a solving time of T seconds.

We decided to use the same timeout of the International Constraint Solver Competitions.

The reproduction of SATzilla used in this paper differs from the original version[START_REF] Xu | SATzilla2012: Improved algorithm selection based on cost-sensitive classification models[END_REF]) because ties during solvers comparison are broken by selecting the solver that in general solves the largest number of instances. Moreover

CPHydra needs to solve a NP-hard problem to decide the schedule of solver to use. Computing the schedule can take, in few cases, more than half an hour for portfolios with more than 8 solvers.

The SBS for the selected benchmark was MinisatID (de Cat et al. 2013) having a PSI of 51.62% and an AST of 950.51 seconds.

Conversely to the other approaches, the AST of CPHydra is not anti-correlated to its PSI.


Marie Fare

Pepita Ould Ahmed

COMPLEMENTARY CURRENCY SYSTEMS QUESTIONING SOCIAL AND ECONOMIC CHANGES

Complementary Currency Systems (CCS) are by no means new to history; since the 1980s they have been attracting more and more attention and growing apace in developed as in developing economies. By Complementary Currency System we understand a unit (or system) of account that is specific (i.e. not general), complementing the official currency, developed at the initiative of a group of agents (private individuals, enterprises, local authorities, NGOs, associations, foundations, private non-profit organisations, etc.) that band together to form a network in a delimited territory, with a view to enabling accounting and the regulation of trade in goods and services.

CCS is a relatively recent theme that, as these new currencies take off, has been attracting increasing attention in research field. A space is being set aside to promote dialogue between researchers working on specific monetary arrangements. In 1997 the International Journal of Community Currency Research Journal (IJCCR) (http://ijccr.net/) was created by Colin Williams, Mark Jackson and Gill Seyfang 1 ; it was to play an important part in spreading knowledge of CCS. Space devoted specifically to this research subject has received further support from the establishment (still in progress) of an international association of researchers working on the subject and the organisation of regular conferences on CCS at the Ecole Normale de Supérieure de Lyon 2 (2011), at the International Institute of Social Studies in the Hague 3 (2013) and at the Federal University of Bahia in Brazil (2015). These events also provide opportunities for meetings between stakeholders (practitioners, local officials and councillors, etc.) in the sector and between operatives and research workers 4 .

The aim of this article is to give an account of the state of the CCS issue, which originated in economic geography and subsequently moved towards institutional economics. After going through the relevant literature and putting it in historical and thematic order, we propose to explain the characteristics, the logic and the impact of these complementary monetary arrangements.

First, we will take a panoramic view of CCS, showing how very diverse they are, both in their nature and their objectives, their concepts, their forms and modes of monetary governance, and the degree of their articulation to political and economic structures.

section 2 analyses the methods used by the literature to evaluate the impact of CCS. The section 3 presents the contributions the challenges they embody, echoing the current context of crisis in the regime of financial globalisation. These new monetary arrangements are part of local economic and socio-economic dynamics, and should be seen as weapons in the struggle against social and monetary exclusion. Lastly, CCS raise important questions on the emergence of a new economic order, based on new standards of production and consumption. They challenge, from a theoretical point of view, the role and place of money in the economy. Section 4 concludes with a return to one of the challenges facing CCSs. It takes us bake to the question of their scale, inquiring into the conditions of possibility and the benefits and potential problems that a change of this sort could entail.

COMPLEMENTARY CURRENCY SYSTEMS: WHAT EXACTLY ARE THEY?

The beginnings of CCS date back to the 19 th and early 20 th century: the monetary experiments (usually described as utopian and /or socialist). Robert Owen (1771Owen ( -1859)), set up the first Labour Exchange in England (1832England ( -1834)), to combat monetary and financial exclusion. In an exchange of fair labour, the products of tradesmen, home-workers and cooperatives were traded, by means of work-tickets, at prices based on the number of hours needed to produce them [START_REF] Dupuis | socialiste utopique[END_REF]. In 1849, Proudhon proposed an alternative project of society based on new monetary and financial principles: universal credit, free of charge, managed by a new banking institution, the "people's bank", with "exchange bills" replacing the official currency 5 . Subsequently, local currencies based on a system of stamped notes (subject to the cost of demurrage, and depreciating with time) were tried out in the 1930s at Wörgl in Austria, and were applied on various terrains, e.g. in the USA in 1933, with Stamp Scrip, under the influence of the economist Irving Fisher; later, in France during the 1950s, a system of local vouchers was developed; very much later, in Argentina, with the currencies used by barter clubs; and, as of the new millennium, in Germany, with regional currencies (such as the Chiemgauer); and last but not least the Stroud pound, launched in the UK in 2009. In the early 1980s, a new wave of CCS emerged with the creation in 1983 of the LETS (Local Exchange Trading System) in Comox Valley on Vancouver Island in Canada, in a context of massive unemployment resulting from the closure of a local industry. This model subsequently spread throughout the world. There had not been a wave of local currencies of this order since the beginnings of industrialisation in the early 19 th century. Over the past 30 years, the gradual diversification of existing models of CCS and their ability to last have raised a number of questions. What do they mean? What impact have they had? The available information on their actual numbers is controversial. It is by no means clear whether the list we have given is exhaustive or not, as some systems have been neither publicised nor studied. According to our sources, some 3,500 to 4,500 systems have so far been recorded in more than 50 countries (Blanc, 2006;[START_REF] Kennedy | Les monnaies régionales. De nouvelles voies vers une prospérité durable[END_REF][START_REF] Seyfang | Growing Green Money? Mapping grassroots currencies for sustainable development[END_REF] 6 . These monetary arrangements are by no means homogeneous. They are highly varied, differing in their political and ideological bases, theoretical reasoning, modes of governance and the material form of their currency. Systems tend to be complex and are more or less closely tied to official monetary systems and to local political and economic institutions. They are also part of contexts that are sometimes markedly "northern" or "southern". Systems that emerge in the South usually come into being during economic crises, and in impoverished social strata. Those that emerge in the North concern strata that can be highly diversified (ranging from people whose position is precarious to the so-called "bohemian bourgeois" urbanites), as are their motivations. Yet, whatever the specific context of their emergence, all these currency systems share the same objectives: support for territorial socio-economic and political dynamics, introduction of new economic practices based on new social and environmental norms, promotion of participatory democracy and of empowerment. When a new currency emerges in a context of fragility or crisis, in some regional or local cases it outlasts the original situation and gains recognition by the relevant political authorities. As of the 1980s, four generations of CCS can be distinguished, according to their monetary organisation and specific links to the socio-economic world and to the local and central public authorities [START_REF] Blanc | Classifying "CCs": Community, complementary and local currencies' types and generations[END_REF][START_REF] Blanc | Les monnaies en tant que dispositifs innovants : une évaluation[END_REF]. These four generations do not necessarily appear in that order, one after another; they are subject to mutation and imbrication; and the emergence of a new CCS does not necessarily put an end to those that already exist.

A first generation of CCS emerges in the form of LETS, as of 1983, and amplifies constantly, from an initial count of about 1412 instances in 2012 [START_REF] Seyfang | Growing Green Money? Mapping grassroots currencies for sustainable development[END_REF]. The literature on the subject is abundant [START_REF] Aldridge | Trading Places: geography and the role of Local Exchange Trading Schemes in local sustainable development[END_REF][START_REF] Boyle | Time Banks. A radical Manifesto for the UK[END_REF][START_REF] Douthwaite | The Ecology of Money[END_REF][START_REF] Lee | Moral money? LETS and the social construction of local economic geographies in Southeast England[END_REF][START_REF] Liesch | Community-based LETS systems in Australia: Localised Barter in a Sophisticated Western Economy[END_REF][START_REF] Nakazato | An Empirical Study of the Social Effects of Community Currencies[END_REF][START_REF] North | Money and Liberation. The Micropolitics of Alternative Currency Movements[END_REF][START_REF] North | Local Money[END_REF][START_REF] Pacione | The other side of the coin: local currency as a response to the globalization of capital[END_REF][START_REF] Seyfang | Examining Local Currency Systems: A Social Audit Approach[END_REF][START_REF] Seyfang | Community currencies: small change for a green economy[END_REF]Williams, 1996a[START_REF] Williams | Local Currencies and Community Development: An Evaluation of Green Dollar Exchanges in New Zealand[END_REF]Williams, , 1996c)). LETS use paper currency or mutual credit. Mutual credit currencies are created in the actual act of trading, by simultaneous crediting and debiting of the parties involved in the deal. These currencies are thus completely different from paper money, which has to be issued prior to the deal in order to enable it. As paper money, we can mention for example the currency used by the Argentine barter clubs that enjoyed unprecedented success and have given rise to a substantial literature (Abramovich and Vazquez, 2007;[START_REF] Goméz | Argentina's Parallel Currency: The Economy of the Poor[END_REF]Hintze, 2003;[START_REF] Ahmed | Les formes du politique dans les « clubs de troc ». Le cas de l'Argentine[END_REF]2010;[START_REF] Plasencia | La oxidación monetaria y la moneda social. Aportes teóricos y análisis de un caso: la moneda social oxidable de Venado Tuerto, provincia de Santa Fe[END_REF]Plasencia and Orzi, 2007;etc.). The arrangements made in this first generation of CCS are characterised by non-convertibility into the official currency, and by their origin: in most cases local associations set them up to respond to demand that was not catered for by the market and the State. Few partnerships were set up with local authorities. Examples of currencies of this generation are the local exchange systems (SEL) in France [START_REF] Laacher | Les SEL. Une utopie anticapitaliste en pratique[END_REF][START_REF] Lenzi | L'enquête nationale sur les systèmes d'échanges locaux (SEL) en 2004[END_REF]Servet, 1999;etc.) and the Community Exchange System (CES) devised in South Africa [START_REF] Coetzee | Global Tools for Local Exchange: Community Currency and Gift Economies[END_REF].

The second generation of CCS can be traced back to the Japanese Fureai Kippu system devised in the 1970s to promote solidarity between population generations. The second generation of CCS came into its own, however, with the North American time-bank and timedollar experiments [START_REF] Cahn | More Throw Away People: The Co-Production Imperative[END_REF], and subsequently with the Italian banche del tempo set up in the later 1990s. It was then that an international dynamic emerged: in 2012 some 1715 instances were recorded [START_REF] Seyfang | Growing Green Money? Mapping grassroots currencies for sustainable development[END_REF]). An abundant literature has been devoted to them [START_REF] Amorevole | La Banca del Tempo. Come organizzare lo scambio di tempo: i valori, i principi, i protagonisti[END_REF][START_REF] Boyle | Time Banks. A radical Manifesto for the UK[END_REF][START_REF] Ozanne | Learning to exchange time: benefits and obstacles to time banking[END_REF]Seyfang, 2003, etc.). The trading was in services, and accounting was based on the time taken to provide them. The resultant currencies were totally non-convertible. Unlike most first-generation experiments, time banks were often closely linked to local authorities or to socio-economic solidarity movements, and promoted social objectives (various forms of local mutual aid) rather than economic ones. This second generation of CCS continued with the Quebec Accorderie model that combined time-trading, microcredit and joint purchasing arrangements, all with outside support, that in Quebec came from a foundation, and in France from local authorities [START_REF] Comeau | Les réseaux d'échange de proximité au Québec. Bilan d'une enquête statistique[END_REF][START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF][START_REF] Lizotte | L'Accorderie and Le Jardin Universel (JEU) in Quebec[END_REF].

A third generation of CCS came into being in 1991 in the USA with the Ithaca Hour [START_REF] Collom | Community Currency in the United States: the social environments in which it emerges and survives[END_REF][START_REF] Douthwaite | The Ecology of Money[END_REF][START_REF] Jacob | Hour Town -Paul Glover and the Genesis and Evolution of Ithaca Hours[END_REF][START_REF] Krohn | An economic analysis of contemporary local currencies in the United States[END_REF]. In 2003 it got a "second wind" in Germany with the Regiogeld experiment (Gelleri, 2009; Kennedy and Lietaer, 2008; Thiel, 2012; Volkmann, 2012 7 and with the emergence of community development banks in Brazil [START_REF] Borges | Banco dos Cocais. Uma experiência inovadora de bancos comunitarios[END_REF][START_REF] Franca Filho | L'enjeu de l'usage des monnaies sociales dans les banques communautaires de développement au Brésil: étude de cas de la Banque Palmas[END_REF][START_REF] Melo | Viva Favela ! Quand les démunis prennent leur destin en main[END_REF][START_REF] Meyer | Les finances solidaires comme biens communs durables: étude de cas de la Banque communautaire de développement Palmas (Brésil)[END_REF][START_REF] Neiva | Banco Palmas: Resultados para o Desenvolvimento Comunitário e a Inclusão Financeira e Bancária[END_REF] (see figure 3). Later on, in the new millennium, it reappeared in the UK with the "Towns in Transition" movement8 at Totnes (2006) and Lewes (2008), then at Stroud and Brixton, in 2009, and at Bristol in 2011[START_REF] Graugaard | A tool for building community resilience? A case study of the Lewes Pound[END_REF][START_REF] Longhurst | The Totnes Pound. in North, P. The Transition Guide to Money[END_REF][START_REF] North | Local Money[END_REF][START_REF] Ryan-Collins | Building local resilience: The emergence of the UK Transition Currencies[END_REF][START_REF] Scott Cato | Stroud Pound: A Local Currency to Map, Measure and Strengthen the Local Economy[END_REF]; in France it appeared at Villeneuve-sur-Lot with the Abeille currency. Approximately 243 CCS of this type were recorded in 2012 [START_REF] Seyfang | Growing Green Money? Mapping grassroots currencies for sustainable development[END_REF], using money in either paper or electronic form (for examples of vouchers, see figure 2). Conversion from the central to the local currency was possible, at fixed rates, but conversion from local to central was either impossible or was subject to penalties. Issues of local currency were covered by equivalent reserves in the national currency. The alternative currencies were designed for ordinary dayto-day consumption, subject to agreements with partners (enterprises or shops). Some currencies also went into partnership with local banks to organise microcredits, or (in the case of the Bristol Pound and the Brixton Pound) with local authorities to settle public services and local rates and taxes.

A fourth generation of CCS came into being after the year 2000, often in the form of smart cards and electronic currency. These CCS were distinguished by the multiple partnerships they set up with local authorities, economic agents and institutions, and national sometimes even European organisations or programmes. Multiple partnerships were set up and specific material forms of money led to technological solutions that sometimes turned out to be expensive. Examples are the NU experiment in Rotterdam in [START_REF] Blanc | Invariants et variantes de la souveraineté monétaire : réflexions sur un cadre conceptuel compréhensif[END_REF]-2003[START_REF] Sambeek | NU-Spaarpas: The sustainable incentive card scheme, Stichting Points[END_REF][START_REF] Seyfang | Community currencies: small change for a green economy[END_REF]), the SOL experiment in France between 2006and 2008[START_REF] Delille | Le projet SOL : pour retrouver le sens des valeurs[END_REF][START_REF] Fare | The SOL: a Complementary Currency for Social Economy and Sustainable Development[END_REF][START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF], and the Eco-pesa that circulated in Kenya in 2010 [START_REF] Ruddick | Eco-Pesa: an evaluation of a complementary currency programme in Kenya's informal settlements[END_REF]. On the whole, these systems were relatively few in number: in the whole world only about ten existed in 2012.

Tables 1 and2 sum up some organisational characteristics of CCS, by generation, and give some quantitative data for some examples as an indication.

MEASURING THEIR IMPACT: A METHODOLOGICAL QUESTION

Because of the very diversity of CCS and the fact that they have emerged only relatively recently, the main studies are empirical and used a pluralism method to analyse the impact of CCS.

Empirical and contextualised studies

Theoretical work on CCS is still a minority concern, however, as Ryan-Collins ( 2011) has pointed out. This can be explained, in our opinion, by a need to distance oneself in time: so many monetary innovations, so different from one another and so complex. A lot of empirical research will be needed before a theory can be formulated convincingly. CCS have not yet been thoroughly studied and there is no database to document their development, characteristics, specific logics and quantitative and qualitative features. Econometric studies not being practicable, it is difficult to account properly for individual behaviour, quantitative aspects and the logics in operation. This is why fieldwork to be undertaken, to obtain data through analyses of impacts.

The majority of researchers working on CCS issues adopt a pluralism method to conduct their field surveys using a number of socio-economic and economic-anthropological methods and approaches such as:

• Action research: the researcher plays a dual role, as research agent and at the same time as socio-economic actor. This involves taking academic knowledge beyond the walls of the institution in which it originated (i.e. education, research) in order to propel social change. This approach is widely used by research institutions in countries such as the UK or Brazil with community development banks. It also consists in making the research process as transparent as possible by doing away with hierarchical barriers between the researcher and the subject being studied, so that research takes on more responsibility and promotes social progress [START_REF] Stringer | Action Research. A Handbook for Practitioners[END_REF].

Research action can also involve making proposals to reduce difficulties faced by the group being studied. • Participatory observation, a method inspired by anthropological practice, which favours direct observation by the researcher of practices, and takes time and place into account in the researchers' observations. • Qualitative field surveys: "spot" studies, discontinuous but repeated, focus on the lifetrajectories of actors (by means of semi-directive surveys and interviews, statistics) inspired by the "life story" method widely used in anthropology and qualitative sociology. This methodological pluralism makes it possible to mobilise methods and tools either proper to the research that is under way, or shared with other disciplines (quantitative and qualitative by means of individual and/or collective interviews and surveys conducted by means of questionnaires). An approach of this sort is helpful to reveal the multidimensional nature, the logics and the impacts of the monetary facts and practices being examined. It mobilises a comprehensive set of tools, starting with observation of monetary practices, and progressively formulating theoretical concepts and elaborating them on the basis of experience. This orients research towards production of highly contextualised primary data generated directly by the actual practice of fieldwork.

A diversity of impact measures criteria

All of these case studies focus on the impact of CCS on economic, social and (in some cases) environmental levels. The indicators of measurement and the criteria adopted are heterogeneous, and there is no grid of evaluation shared by all authors that enables us to compare the various CCS experiments. Some authors have nonetheless attempted to construct a matrix, led by [START_REF] Seyfang | Examining Local Currency Systems: A Social Audit Approach[END_REF]. Her grid of evaluation is based on performance indicators (quantitative and qualitative); she developed it after studying the LETS and Time-bank experiments. More recently, Bindewald and Place ( 2013) have undertaken to develop a standardised matrix to evaluate multi-criteria impacts, based on a list of the factors involved in success and on emblematic cases of CCS. Also worth noting is the Social Trade Organisation9 in Central America (STRO-CA), which has also worked out a multidimensional grid based on the Sustainable Local Economy Framework, and is integrating, as far as possible, specifics of the social and economic environments of projects [START_REF] Brenes | Complementary currencies for sustainable local economies in central america[END_REF]. In the case of the Brazilian community development banks, mapping has been developed on the initiative of the Palmas Institute, which uses it as a tool for implementing and managing currency. Places of production and consumption have been listed with a view to analysing the circulation of money and monetary needs; but the tool has not yet been fully exploited [START_REF] Neiva | Banco Palmas: Resultados para o Desenvolvimento Comunitário e a Inclusão Financeira e Bancária[END_REF]. Criteria adopted to evaluate the impact of CCS are very diverse, as their relevance is tied to forms and objectives that are proper to each system. We will mention here a number of examples.

To take account of the scope of CCS, the size of the relevant monetary community and the volume of its exchanges give an idea of the place occupied by this CCS in monetary, economic, territorial and social space. Looking at CCS from this point of view, once they reach a significant scale, they can have a real impact on the dynamics of local economies [START_REF] Goméz | Governance and sustainability of the Argentine Complementary Currency Systems[END_REF]. When the size of the experiment is too small, on the other hand, its impact remains marginal, as is shown in Aldrige et al. (2003) who deal with LETS in the UK. Similarly [START_REF] Krohn | An economic analysis of contemporary local currencies in the United States[END_REF], in their econometric study of local currencies in the USA, show that in growth of per capita income during the 1990s the local multiplying effect is too feeble to be detected. Krohn and Snyder's results should be relativised, however, as they do not compare the volume of local currency in circulation (and the value added created in CCS) with that of the overall volume of money in circulation.

Forms of governance of CCS (horizontal markets, the hierarchical system, local community groups and association networks) apparently also play a part in the survival and sustainability of the movements. The relevance of this factor varies according to the size of critical mass in CCS. An example: the Argentine barter clubs studied by [START_REF] Goméz | Selective spatial closure and local economic development: what do we learn from the Argentine local currency systems[END_REF].

The impact of CCS on economic dynamics is also influenced by the conditions under which money circulates. [START_REF] Kichiji | A comparison in transaction efficiency between dispersive and concentrated money creation[END_REF] show, using a random networksimulation model that the distribution of money held by agents influences the rate of transactions carried out as a function of the money in stock. Furthermore, [START_REF] Kurita | CC Coupon Circulation and Shopkeepers' Behaviour: A Case Study of the City of Musashino, Tokyo, Japan[END_REF], in a study of coupons in Japan, show that the degree of knowledge of a currency has a forcible impact on its circulation.

The impact of CCS is also measured by their ability to avoid financial exclusion (Williams on LETS in the UK, 1996aUK, , 1996bUK, , 1996c)). Two criteria are usually adopted for this: direct creation of jobs at local level, and the increase in economic, social and human capital held by persons in a situation of exclusion. While some systems, such as Ithaca money in the US [START_REF] Douthwaite | The Ecology of Money[END_REF] are oriented towards the local productive apparatus, and employment, production and local dynamics, others target growth in sustainable consumption, such as the "green points" customer fidelity cards in the NU-Spaarpass in Rotterdam [START_REF] Sambeek | NU-Spaarpas: The sustainable incentive card scheme, Stichting Points[END_REF]. Other examples are given in [START_REF] Lenzi | L'enquête nationale sur les systèmes d'échanges locaux (SEL) en 2004[END_REF] dealing with SEL and in [START_REF] Seyfang | Growing Cohesive Communities One Favour at a Time: Social Exclusion, Active Citizenship and Time Banks[END_REF], on time banks and LETS in the UK. [START_REF] Seyfang | Growing Cohesive Communities One Favour at a Time: Social Exclusion, Active Citizenship and Time Banks[END_REF] has adopted an other criterion for measuring escape from social exclusion: the ability of CCS to enable users to assert their rights as citizens: social rights (integration into networks, bonds of reciprocity), economic rights (having an income; receiving recognition in work; consuming; saving), and political rights (participating in public and associative decision-making). [START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF] has meanwhile kept three multi-dimensional criteria: territorialisation of activities (localisation of exchanges, creation of social links, participation in democratic process); intensification of the dynamics of exchange (development of access to credit, empowerment, struggle against poverty), and transformation of practices, lifestyles and social representations (responsible consumption, ecological citizenship, making organisations responsible, valorising the capacities of each and everyone, and collective empowerment).

In the case of those CCS that have essentially social aims, the main impact criterion adopted is the ability of the systems to create social bonds of mutual aid and solidarity. A special mention should be made here of the CCS in Japan that have objectives that are social (aid for the elderly) or ecological, as the case may be. These systems seek essentially to recreate traditional community bonds -local, and in some cases inter-generational (l'uchi)outside of exploitative production relations [START_REF] Hirota | Les expérimentations de monnaies locales au Japon: les monnaies au service de l'Uchi[END_REF]. [START_REF] Nakazato | An Empirical Study of the Social Effects of Community Currencies[END_REF] examine their ability to create social bonds, using the Granovetter analytical grid that represents bonds as strong or weak.

It is important to stress that unlike the CCS that have economic objectives, those that have social aims do not necessarily seek to expand their scale of application. This is the case in particular with the French SEL [START_REF] Laacher | Les SEL. Une utopie anticapitaliste en pratique[END_REF][START_REF] Lenzi | L'enquête nationale sur les systèmes d'échanges locaux (SEL) en 2004[END_REF] and also with some Japanese local currency systems, the chiiki tsûka [START_REF] Hirota | Les expérimentations de monnaies locales au Japon: les monnaies au service de l'Uchi[END_REF]Kennedy and Liaeter, 2008).

MAIN CONTRIBUTIONS AND QUESTIONS RAISED BY CCS

What we propose here is not an exhaustive synthesis of research on CCS but simply a record (with a historical perspective) of the main contributions and challenges the CCS embody in the current context of financial capitalism in crisis. These new monetary arrangements participate to a local and territorial dynamics. They also raise important questions on the emergence of new economic relationships, based on solidarity and environmental standards of production and consumption. They challenge, from a theoretical point of view, the role and place of money in the economy.

A potential in terms of local dynamics

The first publications on contemporary CCS were made by English economic geographers, and particularly Colin Williams (Williams, 1996a[START_REF] Williams | Local Currencies and Community Development: An Evaluation of Green Dollar Exchanges in New Zealand[END_REF](Williams, , 1996c) ) and his team: Aldridge, Lee, Leyshon, Tooke, Thrift - [START_REF] Leyshon | Alternative economic spaces[END_REF], and the work of Peter [START_REF] North | Money and Liberation. The Micropolitics of Alternative Currency Movements[END_REF]. Their work on the first generation of alternative monetary systems, and in particular on LETS in the UK, included an evaluation of potential in terms of local economic development (jobcreation, self-employment, access to free credit, and so forth) and social well-being (promotion of social bonds, fairness, self-confidence, quality of life, etc.). Surveys were also made of LETS in Australia [START_REF] Liesch | Community-based LETS systems in Australia: Localised Barter in a Sophisticated Western Economy[END_REF] and in New Zealand also of time banks [START_REF] Ozanne | Learning to exchange time: benefits and obstacles to time banking[END_REF], revealing obstacles and levers, both internal and external, to diffusion and extension.

This groundbreaking work was followed by that of other British researchers such as Seyfang and Longhurst (2009), who covered in their surveys, over and above socio-economic effects and local arrangements, the economic impact of CCS, using the concept of sustainable consumption. They studied first LETS [START_REF] Seyfang | Examining Local Currency Systems: A Social Audit Approach[END_REF][START_REF] Seyfang | Community currencies: small change for a green economy[END_REF] and the Totnes currency and/or time banks in the UK (2002,2003,2006), then the local currencies created in "transition towns" as of 2006. These were also studied by other researchers, such as Scott Cato and Suàrez ( 2012), working on the Stroud Pound. Yet other researchers involved themselves directly as actors in setting up the currencies: Ryan Collins (2011) in the Brixton Pound and Mark Burton in the Bristol Pound. Seyfang, Smith and Longhurst see CCS as socio-technical niches, "local grassroots innovations" springing from citizens' initiatives experimenting with alternative lifestyles and sustainable practices that are able to grow and influence society on a broader scale [START_REF] Seyfang | Growing Green Money? Mapping grassroots currencies for sustainable development[END_REF].

Other researchers have studied in a variety of contexts the ability of CCS to promote sustainable local development: in France, [START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF] examines the SOL, and in Quebec the Accorderie; in Kenya, Ruddick studies the Eco-pesa (2011); in Brazil, community development banks have been studied by several researchers [START_REF] Neiva | Banco Palmas: Resultados para o Desenvolvimento Comunitário e a Inclusão Financeira e Bancária[END_REF]; in Argentina, the barter clubs have been analysed as instruments of selective and protective spatial closure [START_REF] Goméz | Selective spatial closure and local economic development: what do we learn from the Argentine local currency systems[END_REF][START_REF] Pacione | The other side of the coin: local currency as a response to the globalization of capital[END_REF]. In the restricted territorial in which they can be used, these currencies can have a beneficial effect on local economies, affecting them in an endogenous manner (consumption inside a local monetary and territorial space; creation of resources and of new outlets and of jobs), promoting a development model based on micro-entrepreneurs and extra-economic values. Use of a local and territorial currency can also strengthen local community links and local identity, as shown by Neiva, Nakagawa, Eskimo, Braz, Silva and Mascarenhas (2013).

Supporting a local strategy of development, some alternative monetary arrangements propose microcredit. Stemming from Brazilian experiments, monetary and financial engineering of this sort is still an exception. The success of this particular arrangement can be seen in the proliferation of community development banks throughout Brazil: today, more than a hundred such systems based on solidarity values are functioning in community selfmanagement mode (França Filho et al., 2012).

The promotion of a new order of values

Whatever their aims -single or multiple: economic, social, environmental, political (empowerment) -CCS arrangements share a common feature: the will to change the prevailing vision of the economic order and to reformulate the rules of the game in order to respect links between human beings (Hart et al., 2010). The flowering of all these CCS is implicitly and in part a critique of today's globalised capitalist economy and of the individualistic market society that it has promoted. CCS arrangements demand, explicitly or by implication, that relations between man and nature and between men themselves be guided by the values of solidarity, reciprocity, proximity and mutual aid. Concrete militant initiatives create alternative exchange communities that resonate with developments in the economic sphere, and in particular with the emergent social and solidarity economy (SSE) and the French Anti-Utilitarian Movement in Social Science (MAUSS in French Mouvement Anti-Utilitariste en Sciences Sociales). The SSE approach is a prolongation of that of Polanyi, based on two normative principles: reciprocity and democratic action [START_REF] Ould Ahmed | The Social and Solidarity Economics: contours and feasibility of a theoretical and political project[END_REF].

The ability of CCS to designate "linking-money" and to promote reciprocal exchange based on solidarity is a theme in most studies (França Filho et al., 2012;[START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF][START_REF] Liesch | Community-based LETS systems in Australia: Localised Barter in a Sophisticated Western Economy[END_REF][START_REF] Neiva | Banco Palmas: Resultados para o Desenvolvimento Comunitário e a Inclusão Financeira e Bancária[END_REF][START_REF] Pacione | The other side of the coin: local currency as a response to the globalization of capital[END_REF]Servet, 1999). [START_REF] Coetzee | Global Tools for Local Exchange: Community Currency and Gift Economies[END_REF], for example, shows that community currencies help a « network society » to emerge: a society in which the principles of reciprocity and the exchange of gifts are embedded in an "economy of relationships". Inspired by the work of Marcel Mauss, [START_REF] Lizotte | L'Accorderie and Le Jardin Universel (JEU) in Quebec[END_REF], basing his argument on instances of SEL in Quebec, shows that the exchange relationships that develop in this context are in fact based on informal mutual aid between individual members, who thereby distinguish gift relationships from the market equivalents.

Brazil has proved a particularly fertile field for solidarity initiatives. Arrais de Paiva and Dos Santos Filho (2011), for example, show that community development banks and solidarity rolling funds financed by the Bank of North-Eastern Brazil have made it possible to constitute in the lower strata of society forms of saving managed by community organisations, and to promote the development of solidarity finance. These arrangements have made it possible to forge reciprocal links locally between individuals, and to create forms of socioeconomic organisation that strengthen job-creation and equality in society. Also in Brazil, [START_REF] Poljokan | Fora do Eixo Card: The Brazilian System for the Solidarity Culture[END_REF] have studied the constitution of a solidarity networks linking 70 cultural cooperatives, the circuito Fora do Eixo, that exchange information and technologies and stimulate the production, circulation and distribution of music, visual arts, literature and drama. These authors deal in particular with the Espaço Cubo cooperative that organises a trade system and has created the Cubo-card, a social currency.

In Argentina, the barter club experiment has raised the possibility of constructing specifically "social" currencies and a whole social solidarity economy (Plasencia and Orzi, 2007). Orzi has been thinking specifically about ways of articulating and developing social currency and solidarity markets. [START_REF] Plasencia | La oxidación monetaria y la moneda social. Aportes teóricos y análisis de un caso: la moneda social oxidable de Venado Tuerto, provincia de Santa Fe[END_REF] thinks about the pertinence of the principle of "rusting" money in promoting a social solidarity economy, basing her thinking on the social currency launched in 1999 at Venado Tuerto in the province of Santa Fe.

The impact of CCS on the struggle against social inequalities, and in particular those that are gender-based, has been measured by the literature. It has emerged that these monetary systems can also be useful to those underprivileged who do not have access to the official currency [START_REF] Stodder | Complementary Credit Networks and Macro-Economic Stability: Switzerland's Wirtschaftsring[END_REF]. This is particularly true of the monetary arrangements of the southern countries that have been developed with these underprivileged groups in view. However, while CCS can help some low-income groups to protect and enhance their styles of life, they are less effective as a general means of reducing poverty [START_REF] Goméz | What was the deal for the participants of the Argentine local currency systems, the Redes de Trueque?[END_REF]. Studies of LETS, in particular, have shown that inequalities of income and gender on formal markets tend simply to be reproduced in alternative systems [START_REF] Bogani | Perspectivas de desarrollo económico y social para las mujeres pobres y empobrecidas en los clubes de trueque. Estudio de caso: 'La Bernalesa[END_REF][START_REF] North | Money and Liberation. The Micropolitics of Alternative Currency Movements[END_REF][START_REF] North | Local Money[END_REF][START_REF] Seyfang | Community currencies: small change for a green economy[END_REF]. Despite over-representation of women among the users of the alternative systems, these systems do no really enable the women to improve their social lot significantly, even though they do improve the women's sociability [START_REF] Comeau | Les réseaux d'échange de proximité au Québec. Bilan d'une enquête statistique[END_REF][START_REF] Lenzi | L'enquête nationale sur les systèmes d'échanges locaux (SEL) en 2004[END_REF][START_REF] Williams | Local Currencies and Community Development: An Evaluation of Green Dollar Exchanges in New Zealand[END_REF].

The CCS question the place and the role of money in economy

In France the Walras Centre (Lyon II University) has been a precursor on CCS themes. Its research programme on SEL (the equivalent of the LETS) was launched during the 1990s. Work was directed by Servet (1999), and subsequently by Blanc (2006). Their approach is socio-economic, close to the institutional current inspired by Polanyi's work and SSE. These authors investigate monetary usages and practices in exchange communities, analysing their functioning, which throws light on monetary concepts. Other French researchers are close to these authors (though some of them come from other horizons), and share their theoretical interrogations.

Servet shows that the SEL throw light on the social foundations of money. In the SEL organisations, money plays its full part in creating links between individuals and between generations. Debt relationships can only be set up between individuals on condition that they trust one another and that they share the same values of solidarity and reciprocity [START_REF] Servet | Le Chicago Plan revisité par les monnaies complémentaires, le microcrédit solidaire et les tontines[END_REF].

Blanc examines the plurality of monetary situations that shows up in the development of CCS [START_REF] Blanc | Les monnaies parallèles. Unité et diversité du fait monétaire[END_REF][START_REF] Blanc | Invariants et variantes de la souveraineté monétaire : réflexions sur un cadre conceptuel compréhensif[END_REF]. He has worked out a substantial categorisation and typology of these parallel currencies (2000,2011) (cf. figure 1). In a transverse interdisciplinary perspective, together with Fare, he justifies the criteria established by their proposed typology of CCS, e.g. the existence and type of social innovation [START_REF] Blanc | Les monnaies en tant que dispositifs innovants : une évaluation[END_REF] and the role of public authorities [START_REF] Blanc | Understanding the role of governments and administrations in the implementation of community and complementary currencies[END_REF]. Options concerning terminology and typology used in the study of these parallel currencies are the subject of an ongoing debate (Blanc, 2006[START_REF] Blanc | Classifying "CCs": Community, complementary and local currencies' types and generations[END_REF][START_REF] Martignoni | A New Approach to a Typology of Complementary Currencies[END_REF].

In the matter of sustainable territorial development, Fare investigates the conditions affecting the establishment and acceptability of CCS and the appropriate scale, suggesting a monetary design based on subsidiarity [START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF][START_REF] Fare | Sustainable territorial development and monetary subsidiarity[END_REF]. In a complementary monetary system, monetary subsidiarity entails the deployment of a specific currency with a unique territorial and socio-economic sphere on each scale of action. This amounts, finally, to pressing the principle of complementarities to its limit, determining for each currency (taking account of the relevant objectives) a single and singular scale for deployment in the framework of rejuvenated territorial governance.

Ould [START_REF] Ahmed | Les formes du politique dans les « clubs de troc ». Le cas de l'Argentine[END_REF][START_REF] Ould Ahmed | Can a community currency be independent to the state money?[END_REF] has questioned monetary plurality, and asked more particularly whether CCS necessarily have to establish some kind of relation (practical, ideological, political, or symbolic) with the official macro-monetary system in order to justify their creation, to be accepted, and to become operational within the community-based spaces of exchange.

Looking a currency in a political-economic perspective, some authors show how the political dimension is revealed in alternative currency movements, their forms and spaces. In various case studies (Argentine barter clubs, SEL in France, LETS in UK, Green Money in Hungary, Green Dollars in New Zealand, etc.), the authors show how the CCS play a part in re-territorialising the political dimension by creating new spaces for protest against and liberation of the monetary order [START_REF] Laacher | Les SEL. Une utopie anticapitaliste en pratique[END_REF][START_REF] North | Money and Liberation. The Micropolitics of Alternative Currency Movements[END_REF][START_REF] Ould Ahmed | Can a community currency be independent to the state money?[END_REF]. Monetary communities can be understood as social movements with political aims, their objective being to construct, by means of collective action, new economic and social bonds that respect new values rather than capitalist norms. In these communities, the bonds formed between participants are not merely social but also politicised, as [START_REF] Laacher | Les SEL. Une utopie anticapitaliste en pratique[END_REF] has rightly pointed out. In most cases they establish these bonds outside conventional political structures, representatives and spaces [START_REF] Ould Ahmed | The Social and Solidarity Economics: contours and feasibility of a theoretical and political project[END_REF]. However, it is above all the leaders and organisers of these CCS who experience the political activism as such; the rank-and-file users' expectations are more practical, materially and symbolically.

In order to strengthen the dynamics of democracy, and some authors suggest that, in coming to decisions on collective options, currency should be viewed as a common, as in the research of Ostrom [START_REF] Meyer | Les finances solidaires comme biens communs durables: étude de cas de la Banque communautaire de développement Palmas (Brésil)[END_REF][START_REF] Servet | Le Chicago Plan revisité par les monnaies complémentaires, le microcrédit solidaire et les tontines[END_REF]. Currency should function as a support of productive practices that respect working conditions and responsible consumption [START_REF] Fare | Les conditions monétaires d'un développement local soutenable: des systèmes d'échange complémentaire aux monnaies subsidiaires[END_REF][START_REF] Seyfang | Community currencies: small change for a green economy[END_REF].

For a theoretical point of view, all these authors share a rejection of an instrumental conception of money that reduces it to a mere tool of market exchanges; they privilege a socio-economic and institutional approach to money, its uses and the practices associated with it [START_REF] Blanc | Les monnaies parallèles. Unité et diversité du fait monétaire[END_REF][START_REF] Ould Ahmed | Monnaie des économistes, argent des anthropologues : à chacun le sien ?[END_REF][START_REF] Zelizer | The Social Meaning of Money: Pin Money, Paychecks, Poor Relief, and Other Currencies[END_REF]. An approach of this sort takes account in particular of the social and political contexts in which an economy operates, and rejects attempts to make the economy a natural, autonomous entity [START_REF] Polanyi | Essais de Karl Polanyi[END_REF]Steiner and Vatin, 2009).

CONCLUSION. THE CURRENT CHALLENGE OF CCS: THE INSTITUTIONALISATION OF CCS AND THE PRESERVATION OF DEMOCRATIC SOVEREIGNTY

An important question raised by CCS -and debated, as yet inconclusively, in the communities concerned -is that of their extension on a larger scale. In this paper we are arguing neither for nor against extension (a political matter to be left to the communities themselves to settle), but seeking to clarify conditions of possibility, potential advantages and possible challenges.

The innovative dimension of CCS is striking. They can be thought of as forms of social innovation [START_REF] Blanc | Les monnaies en tant que dispositifs innovants : une évaluation[END_REF]. Should they be extended? This would involve a shift from experiment to institution. Institutionalisation would entail "an effort to obtain recognition for the social use to which the invention or discovery is put" [START_REF] Fontan | Innovation et changement social[END_REF]. The social utility of CCS would have to be clearly established. This would be a long process, entailing an evaluation of the arrangements and an analysis of their impacts. So far a number of impact studies have been carried out, but most of the CCS have not yet been adequately evaluated. Impact studies are thus a major factor in the development of CCS, which will have to gain greater credibility and legitimacy.

Recognition of the social utility of CCS by public authorities and economic decisionmakers would inevitably confer on them an official and perhaps even legal justification, and increase their potential influence on the entire socio-economic system. Some moral values represented by individuals can have an impact on the emergence of new practices in a local community. Ould Ahmed (2014) points out, however, that there are underlying conditions to this. Some of these are inherent in the social, ideological, and religious predispositions of the agents; others, in the political and economic environment. Beyond this, the local framework has to be predisposed in favour of change: passage to an ampler scale requires a modification of the institutional structures that configure individual interests, determining them to move in such-and-such a direction and to pursue such-and-such an aim. In other words, new values and new economic relationships have not only to be recognised but also adopted by the public authorities and institutions that can enforce change.

CCS could be used to provide support for a strategy of territorial development; their leverage effect increases when they are combined with other mechanisms and instruments used by the authorities and their social and economic partners. At this stage, connecting up the logics and tools that stem from the social and solidarity economy and using them for social and economic development can often provide answers to the questions raised. The tools and resources could be put at the disposal of parties interested in new, different forms of action to improve social and cultural insertion and territorial coherence (e.g. by means of microcredit, tontines, group purchasing, social groceries, cooperatives, funds for solidarity finance and responsible investment cooperative banks, public banks, territorial poles of economic cooperation, etc.), or to launch an ecological transition and increase territorial resilience (e.g. by instituting unconditional incomes, by encouraging eco-responsible behaviour, etc.).

No matter what scale (e.g. local, nation-wide) the users of CCS would like to reach, the role of the public authorities is capital [START_REF] Blanc | Understanding the role of governments and administrations in the implementation of community and complementary currencies[END_REF]. Locally, the authorities can promote the deployment of CCS and help it financially, in accordance with a logic of subsidiarity; they can also play a more active part by accepting the alternative currencies as payment. If nation-wide deployment is envisaged, CCS have to be given a clear-cut legal status so as to move out of the uncertain "grey" zone in law; this would facilitate the intervention of agents in local territories. Thinking of this sort is current in Latin America, and particularly Brazil [START_REF] Vasconcelos Freire | Social economy and Central banks: legal and regulatory issues on social currencies (social money) as a public policy instrument consistent with monetary policy[END_REF]; its aim is an integral monetary organisation based on subsidiarity. Upstream from a major opening-up of this sort, however, all stakeholders would have to be mobilised and come together to form a component of the entire transformative organisation. Together they would have to define and put into effect the new framework of values (e.g. a new model of development) needed to rebuild economic and social relationships. The CCS is a locus in which democratic sovereignty is produced and expressed; civil society is sorely in need of a space of this sort. This particular social demand shows up in the many initiatives we have described; increasingly, the body of society expects to take part much more directly in the decision-making processes of the body politic. One of the challenges implicit in the extension of CCS is that of asserting and preserving democratic sovereignty in socioeconomic spaces. In an overall system that is becoming unsustainable, CCS should constitute and remain a viable and sustainable alternative.

Figure 1 :

 1 Figure 1: simplified chronology of main types of CCS

Figure 2 .Figure 3 .

 23 Figure 2. Examples of vouchers of CCS (illustration by authors)

Table 1 . Main characteristics of currencies cited, by generation

 1

	Generations	CCS		Monetary Forms	Issue	Convertibility
		LETS		Scriptural	Issued in trade	Non-convertible
	G1	SEL		Scriptural	Issued in trade	Non-convertible
		Argentine Trueque	Manual	Prior issue	Non-convertible
	G2	Time banks (UK)		Scriptural	Issued in trade	Non-convertible
		Accorderie		Scriptural	Issued in trade	Non-convertible
		Local complementary currency (France)	Manual	Prior issue	Convertible (on entry but on exit for service providers only)
		Regiogeld (Germany)	Manual and electronic	Prior issue	Convertible (on entry but on exit for service providers only)
	G3	Brazilian community currencies	Manual	Prior issue	Convertible (on entry but on exit for service providers only)
		Currencies of Towns in Transition	Manual and electronic	Prior issue	Convertible (on entry but on exit for service providers only)
	G4	Experimental (France)	SOL	Electronic	Prior (assigned SOL and issue cooperation SOL) or in trade (commitment SOL)	Convertible (cooperation SOL on entry but on exit for service providers only), non convertible (commitment SOL and assigned SOL)
		Nu (Netherlands)		Scriptural	Issue in trade	Convertible (on entry but on exit for service providers only)
	Sources: Adapted from Fare (2011).

Table 2 . Some examples of CCS Generations of CCS Name of currency Zone of activity Date of introduction of the currency Number of providers Number of individual users

 2 The Authors, using documents distributed by associations supporting CCS and interviews carried out ad hoc.

	G3	Palmas	Conjunto	2002	270 (in 2013)	Not recorded
			Palmeira
			(Fortaleza,
			Brazil)
	G3	Chiemgauer	Chiemgau	2003	630 (end 2012)	2573 (end 2012)
			(Germany)
	G3	Brixton pound	Brixton	September 2009	200 (paper	3000 used it at least
			(London, UK)		money) ; 100	once (by 2012)
					(payment by
					SMS) (October.
					2013)
	G3	Bristol pound	Bristol (UK)	September 2012 600 (September	A few thousand,
					2013)	1 200 of whom held
						accounts with the
						Bristol Credit Union

For an exhaustive presentation of the project, see in particular[START_REF] Ferreira | La monnaie « sociale » : l'apport théorique de P.J. Proudhon [1809-1865] et l'expérience du réseau global de troc en Argentine[END_REF].

The website http://www.complementarycurrency.org/ccDatabase/ managed by Stephen DeMeulenaere, founder and coordinator of the Complementary Currency Resource Centre (CCRC), details this diversity.

For a survey of the 73 local-currency projects in the Regiogeld network and their specificities, see in particularThiel (2011).

The "towns in transition" are putting into practice initiatives that are responding to the challenge of climate change and peak oil by improving the resilience of territories. See the site: http//www.transitionnetwork.org/

The Social Trade Organisation (STRO) targets communities that have been paralyzed for years by needless economic depressions; it proposes innovative solutions that use new forms of money and credit to increase purchasing power and make existing purchasing power last longer within given communities or regions.

edited by Gill Seyfang and Noel Longhurst. This conference was organised by the LEFI and Triangle laboratories with support from the Veblen Institute for Economic Reform and the FPH (Charles Léopold Mayer Foundation for the Progress of Man), and the Caisse des Dépôts et Consignations Institute for Research and the Rhône-Alpes Region. 3 V. the site : http://www.iss.nl/research/conferences_and_seminars/previous_iss_conferences_and_seminars/complementary_ currency_systems/ 4 For the 2011 study days see: http://monnaiesendebat.wordpress.org/.