Omar Abdelkafi
email: omar.abdelkafi@univ-lille.fr

Bilel Derbel
email: bilel.derbel@univ-lille.fr

Arnaud Liefooghe
email: arnaud.liefooghe@univ-lille.fr

A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem

Keywords: Big Optimization, Iterative tabu search, Quadratic assignment problem

Parallelization is an important paradigm for solving massive optimization problems. Understanding how to fully benefit form the aggregated computing power and what makes a parallel strategy successful is a difficult issue. In this study, we propose a simple parallel iterative tabu search (PITS) and study its effectiveness with respect to different experimental settings. Using the quadratic assignment problem (QAP) as a case study, we first consider different small-and medium-size instances from the literature and then tackle a large-size instance that was rarely considered due the its inherent solving difficulty. In particular, we show that a balance between the number of function evaluations each parallel process is allowed to perform before resuming the search is a critical issue to obtain an improved quality.

I. INTRODUCTION

Optimization problems underlying different application domains are becoming more and more difficult to solve, with the size of the underlying data increasing continuously. In this context, there is evidence that the optimization community is more and more considering the solving of large-scale optimization problems [START_REF] Mahdavi | Metaheuristics in large-scale global continuous optimization: A survey[END_REF], [START_REF] Li | Nature-inspired algorithms for large scale global optimization[END_REF]. Despite their high efficiency, state-of-art evolutionary algorithms and metaheuristics [START_REF] Blum | Metaheuristics in combinatorial optimization : Overview and conceptual comparison[END_REF] are still facing a number of challenges to find a good solution in a reasonable amount of time.

One of the natural way to tackle large-scale problem instances is to benefit from parallel computing facilities and to explore strategies to set up parallel solving procedures [START_REF] Abdelkafi | A survey on the metaheuristics applied to QAP for the graphics processing units[END_REF]. However, understanding how to fully take advantage form the aggregated computing power and what makes a parallel strategy successful is a difficult issue, in particular when tackling large-size problem instances.

In this paper, we consider the Quadratic Assignment Problem (QAP) as a case study for setting and analyzing parallel solving techniques. The QAP was first introduced by Koopmans and Beckmann [START_REF] Koopmans | Assignment problems and the location of economic activities[END_REF] to model a facility location problem. It can be described as the problem of assigning a set of facilities to a set of locations with given distance and flow between locations and facilities, respectively. The objective is to assign the facilities to locations in such a way that the sum of the products between flows and distances is minimized. More formally, the problem can be stated as follows:

min p∈P z(p) = n i=1 n j=1 f ij d p(i)p(j) (1)
where f and d are the flow and distance matrices respectively, p ∈ P represents a solution where p i is the location assigned to facility i and P is the set of all n vector permutations.

The objective is to minimize z(p), which is the total cost assignment for the permutation p.

It is well-known that the size of the considered QAP instances significantly increases the difficulty of the solving procedure, even when considering heuristic and stochastic search procedures such as metaheuristics and evolutionary algorithms. Therefore, the QAP is a good candidate for studying the effectiveness of using a parallel search approach. In this work, we investigate the parallelization of an efficient sequential metaheuristic to solve QAP, called Ro-Ts [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF]. Our primary goal is to study the behavior of this metaheuristic in a parallel context as a first step toward the setting of highly effective algorithms for solving large-scale instances.

In general, we are tempted to say that increasing the number of processes, keeping the same number of evaluations for each process, is enough to improve the performance of an algorithm. This is not always obvious and it depends on the structure of the instances as well as the behavior of the algorithm that can change in the parallel context. For the case of large-scale instances, we wish to study in particular the impact of two parameters. The first parameter is the number of processes run in parallel, and the second one is the sequential load to be performed by each process.

The rest of the paper is organized as follows. In Section II, we review some of the best-known parallel and sequential approaches to solve the QAP. In Section III, we describe the design of a parallel metaheuristics based on a master-worker architecture. In Section IV, we conduct an experimental analysis using small and medium instances, as well as one large problem instance from the literature. Finally, in section V, we conclude the paper and we propose some perspectives.

II. BACKGROUND

The QAP can be considered as one of the hardest combinatorial problems in theory and practice.

This problem was introduced in [START_REF] Koopmans | Assignment problems and the location of economic activities[END_REF] and later studied in an extensive manner. In particular, different tabu search approaches were proposed, e.g., [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF]- [START_REF] Benlic | Breakout local search for the quadratic assignement problem[END_REF].

One of the first efficient approach to solve the QAP is the robust tabu search (Ro-Ts) proposed by Taillard [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF], where it is shown how to reduce the complexity of computing a fitness value of neighboring solutions using an incremental evaluation procedure. Many other works are based on Ro-Ts to solve the QAP, e.g., [START_REF] James | Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem[END_REF]- [START_REF] James | A cooperative parallel tabu search algorithm for the quadratic assignment problem[END_REF]. James et al. [START_REF] James | Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem[END_REF] proposed two categories of Tabu Search (TS) extending Ro-Ts. The first one is a continuous diversification process coupling a perturbation mechanism with TS. The second one is a discontinuous diversification TS process where a new starting solution is used to replace the current working solution in TS trajectory. In [START_REF] James | A cooperative parallel tabu search algorithm for the quadratic assignment problem[END_REF], a cooperative parallel tabu search algorithm for the QAP is introduced which is based on exchanging information throughout the execution of the algorithm. Later, Benlic et al. [START_REF] Benlic | Breakout local search for the quadratic assignement problem[END_REF] proposed an Iterated Local Search (ILS) with a breakout strategy based on the history of the search. According to the evolution of the search, the ILS selects a perturbation degree, among a range of available ones, in order to better escape local optima.

One of the most important parallel work on QAP was proposed in [START_REF] Czapinski | An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem on CUDA platform[END_REF]. In fact, a Parallel Multi-start Tabu Search is proposed with respect to the CUDA platform. Good quality solutions are obtained, however only the instances of Skorin-Kapov [START_REF] Kapov | Tabu search applied to the quadratic assignment problem[END_REF] are considered, and the biggest instance size tackled there-in is n = 100, which is still a medium scale. In [START_REF] Tosun | On the performance of parallel hybrid algorithms for the solution of the quadratic assignment problem[END_REF], a parallel hybrid algorithm is composed of three steps. The first step is the generation. It consists in using a parallel Genetic Algorithm (GA) based on the island model. Each process represents an island and all the nodes execute a GA in parallel. The second step is a diversification. This diversification method is applied to all solutions. Finally, the global best solution obtained with the first two steps is used as a starting solution for the Ro-Ts. In [START_REF] Abdelkafi | Comparison of two diversification methods to solve the quadratic assignment problem[END_REF], a cooperative variant of Iterative Tabu Search (ITS) is proposed. Each process performs an ITS in which a Ro-Ts is executed at each generation. After each iteration, each process sends its current solution, obtained by the Ro-Ts, to a neighboring process. Then, a distance is computed between the current solution and the solution received from the neighbor process. This distance is based on the similarity between the two solutions (the same facilities assigned to the same locations). According to this distance, the algorithm takes the decision to apply a known diversification strategy, to perturb randomly the solution or to generate a new random solution.

III. PARALLEL ITERATIVE TABU SEARCH

For this work, we propose a simple Parallel Iterative Tabu Search (PITS) based on the state-of-the-art sequential Ro-Ts [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF]. A defined number of processes (NbrPro) is launched. Each process executes an ITS. This number is important because it fixes the parallel deployment of the algorithm. This number can not be increased infinitely since it depends closely on the physical limit of the architecture on which it is executed. For this reason, it is important to effectively exploit the potential of each process.

Each ITS is a succession of Ro-Ts. The number of Ro-Ts calls represents the global iterations (Giterations). One of our motivations for using this algorithm is its efficiency on the QAP. Moreover, like all TS, the Ro-Ts is able to escape from local optima. For a good management of the parallelization, we want to control the sequential load to be executed by each process. For this reason, having a parameter such as the number of iterations performed by the Ro-Ts (TSiterations) is essential. We also would like to vary this parameter in order to find the right balance between the processes.

At each global iteration, a Ro-Ts is performed from different starting solutions. It is done for all the processes. A cooperation mechanism to exchange information between the different processes is used. The objective is to find a good starting solution to improve the global solution. In this approach, after each Ro-Ts, the current process sends the best solution to the master process. The master process select the global best solution. It sends the global best solution to all the processes. Each process receives the information and executes a random perturbation on the received global best solution. Only a part of the solution is changed. This allows the algorithm to keep a good structure for the next Ro-Ts. Many works from the literature, such as [START_REF] James | Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem[END_REF], [START_REF] James | A cooperative parallel tabu search algorithm for the quadratic assignment problem[END_REF], show that using the structure of the best solution found by the search can lead to a promising region of the search space. The random perturbation is considered as a diversification after each Ro-Ts to escape from stagnation and to explore new regions of the search space.

As you can note, in our algorithm design, two parameters are important. The first one is, how many processes the algorithm is going to use. It can be handled through NbrPro. The second one is how long time the execution will take for each process. It can be handled through the TSiterations parameter. In this work, we have based our experiment on these two parameters to see the effect of the parallel design setting.

The choice to have multiple parallel ITS is motivated by many distributed architectures using parallel CPU (Central Processing Unit) that we can have in several computing grids. CPUs are powerful for doing sequential calculations. This is well adapted to the multiple iterations that are executed by the ITS. Obviously, if our intention was to use another architectures such as the Graphic Processing Unit (GPU), we would have made a different choice like parallelizing the evaluations in order to take advantage of the GPUs power in the calculation.

Algorithm 1 is the pseudo-code of the PITS. Figure 1 illustrates the general flow of the algorithm. More information about the Ro-Ts can be found in [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF]. if P is the master process then Select the GBsolution between all the LBsolution processes;

IV. EXPERIMENTAL ANALYSIS

A. Experimental setup

In our experimentation, the algorithm is written in C/C++. It is compiled on Grid'5000 [START_REF]Grid'5000: A large scale and highly reconfigurable experimental grid testbed[END_REF] with a parallel Intel Xeon E5-2630 v4, 10 cores/CPU, 256GB RAM, 2x279GB HDD, 10Gbps ethernet.

The proposed algorithm is experimented on benchmark instances from the QAPLIB (http://www.seas.upenn.edu/qaplib/ inst.html) [START_REF] Burkard | QAPLIB -A quadratic assignment problem library[END_REF] and instances from (http://mistic.heig-vd.ch/ taillard/problemes.dir/qap.dir/qap.html) [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF]. The size of the considered instances ranges between 40 and 343. All the results are expressed as a percentage deviation from the Best Known Solution (BKS).

deviation = (solution -BKS) × 100 BKS (2)
The QAPLIB archive contains 136 instances that can be classified into four types:

• Real life instances (Type 1); • Unstructured randomly generated instances based on a uniform distribution (Type 2); • Randomly generated instances similar to real life instances (Type 3); • Instances in which distances are based on the Manhattan distance on a grid (Type 4); For each instance, 20 independent executions are performed and the average performance is considered. We shall focus on the percentage deviation in our comparison, although the execution time is also provided for completeness.

B. Results on small-and medium-size instances

The aim of this experiment is to confirm the efficiency of PITS algorithm against works from the literature. We start with a comparison on well-known small-and medium-size QAP instances. Two competitive algorithms from the literature have been chosen for this comparison. CPTS is a parallel algorithm using the number of calls to the objective function as a stopping criteria. This number is fixed to 10000 × n × n calls. For PILS, which is a sequential algorithm, the stopping criteria is fixed by the execution time (1 200 seconds for instance size less or equal to 100). Both proposals stop the algorithm as soon as the BKS is reached. The focus of this comparison is solution quality. We use only 5 well-known benchmark instances from the QAPLIB (Type 2), which are the most difficult to solve. The other instances form the QAPLIB are easy to solve for our algorithm and the algorithms from the literature. The instance size ranges between 40 and 100.

This experiments use the parameters reported in Table I. Let us remind that NbrPro is the number of processes, TSiterations is the number of iterations executed by each Ro-Ts, Giterations is the number of Ro-Ts calls and the percentage of perturbation is the percentage of the solution that changes randomly with respect to the global best solution. For example, for an instance of size 100, 20 assignments of the global best solution will be modified randomly.

For this first experiments, we did our best to be as fair as possible when comparing PITS with the CPTS algorithm. The number of objective function calls is set to 200 000 × n (20 processes × 100 Giterations × (100 × n) T Siterations). For CPTS, it is fixed to 10000 × n × n, which is always more than the number of calls that we use for our algorithm. Indeed, for n = 20, we use the same number of calls as CPTS. It means that from a size of 20, our algorithm uses less budget. Indeed, the smallest instance size considered in this paper is 40.

Table II reports the obtained results from all algorithms. The CPU time (CPUt) is computed in minutes. It represents the average CPU time from 20 independent runs. The number in brackets with the deviation is the number of runs where the algorithm reached the BKS.

For the experiments of Table II, the best global average is obtained by the CPTS [START_REF] James | A cooperative parallel tabu search algorithm for the quadratic assignment problem[END_REF] algorithm with 0.469%. It is followed by PITS with a very close average results of 0.499%.

Notice that the proposed PITS obtains better results than the PILS algorithm [START_REF] Stützle | Iterated local search for the quadratic assignment problem[END_REF]. Of course, the execution time depends on the architecture used, but it is important to note that our algorithm has a time average of 3.28 minutes, against 79.24 minutes for CPTS.

These preliminary experiments show that our proposed PITS algorithm is able to obtain almost the same global performances (CPTS outperforms PITS with only 0.03% for the average of the 5 instances) in less budget in terms of CPU time and number of objective function calls.

The experimental results show the efficiency of our algorithm. Indeed, PITS obtains a good performance (less than 0.5% deviation from the BKS) for this reference benchmark.

C. Case study: large-size instance tai343e01

In the rest of the paper, we analyze our proposal using one large instance called tai343e01, from (http://mistic.heig-vd. ch/taillardproblemes.dir/qap.dir/qap.html). In order to give an idea about its complexity, let us mention that the number of constraints for this instance is 61 202. To our knowledge, only [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF] and [START_REF] Hussin | Hierarchical Iterated Local Search for the Quadratic Assignment Problem[END_REF] attempted to solve this instance in the past. In these two works, few results about tai343e01 are actually reported. It is considered as very hard to solve, even for metaheuristics.

The first result is reported in [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF], where the deviation from the BKS is 18%. In [START_REF] Hussin | Hierarchical Iterated Local Search for the Quadratic Assignment Problem[END_REF], several algorithms are compared and the best result from 20 independents trials is given. The algorithms used in the comparison are: Ro-Ts [START_REF] Taillard | Robust taboo search for the quadratic assignment problem[END_REF], ILS-ES [START_REF] Stützle | Iterated local search for the quadratic assignment problem[END_REF], as well as two variants of the Hierarchical Iterated Local Search (HILS(2) and HILS(3)). The best results are obtained by HILS(3) with 0% deviation from the BKS (for the best trial between the 20 independents run). The second variant HILS(2) show a deviation of 59%, the ILS-ES 4% and the Ro-Ts 34%.

The parameters from Table III are used in the following experiment. The major contribution of our work is the setting of the algorithm in a parallel context. As already explained in section III, we focus our analysis on two parameters. The variation of the processes number (NbrPro) and the variation of the iteration number executed by Ro-Ts (TSiterations). To better compare our results, we consider the work from [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF] where the sequential budget (in terms of number of function evaluations) used for the Ro-Ts is 1 619 120. We use a parallel design to get competitive results while remaining close from the budget used in the literature. We decided to choose our settings so that we could have a budget close to the literature as well as larger and smaller budgets, in order to analyze the impact.

Figure 2 shows the average deviation of form 20 independent runs using 20 parallel processes. At each global iteration, the deviation of the best global solution is reported. A number of 100 Ro-Ts are iterated with 1 500 iterations for each one of them.

Our algorithm gets an average deviation of 14.21% from the BKS solution (as shown in Figure 2) and a best trial of 11.61% (best solution between 20 independents executions). The average execution time for the 20 runs is 24.17 minutes in this case. The curve also shows the ability of the algorithm to converge towards better solutions without notable stagnation. The total budget used in this experimentation is 3 000 000 evaluations (1 500 TSiterations × 100 Ro-Ts × 20 processes).

It is important to notice that we have experimented the same algorithm with the same parameters but without the cooperation between the processes through the exchange of the best global solution. The results obtained are much lower than the results obtained by the version that uses the exchange. Indeed, without the exchange we manage to obtain an average deviation of 22.73% from the BKS. It gets a deviation of 21.28% for the best trial. It confirms that the cooperation with the best global solution has a positive effect on the behavior of our algorithm.

For the work of [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF], using 1 619 120 sequential evaluations, a deviation of 18% for the best trial is reported. For our algorithm, we have a sequential budget of 150 000 evaluations (1 500 TSiterations × 100 Ro-Ts). We can observe that with a very little sequential budget (less than 10% of what it is used in the literature) but with a multistart iterative Ro-Ts and an effective exchange of the best solution, we get a better results than the 18% found in [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF]. This suggest that the strength of a tabu search approach for this instance lies in the perturbation step rather than in the iterative search. This also suggests that for this large instance, we need much less iterations in each TS in order to get good performance, which is an ideal framework for parallelization. In order to validate this hypothesis, two scenarios are considered, the first one is the reduction of the number of TSiterations from 1 500 to 750 and 350 iterations while keeping the same number of processes (lower budget). The number of processes can be 10 or 20 or 40 in our case. The second experiment is to keep the same budget, but with a different distribution (variation of the number of processes). For example, the budget of 1 500 000 can be distributed with (1 500 TSiterations × 100 Ro-Ts × 10 processes) or (750 TSiterations × 100 Ro-Ts × 20 processes).

Table IV shows the average deviation of our experiments for the 20 independent runs. The CPU time (CPUt) is computed in minutes. It represents the average time for the 20 independent runs. Naturally, the execution time increases with the increase of the number of iterations, because the sequential part is more important. For example, for 20 processes and 750 TSitrations, the average time is 12.52 minutes. This average increases to 24.17 minutes when we increase the number of TSiterations to 1 500. On the other hand, if we keep the same number of TSiteration and we increase the number of parallel processes, the average time remains constant. For example, for a TSiteration of 350, using 10 processes or 20 processes gives the same average time of 6 minutes. We can observe that this does not remain true when we use 40 processes. This is simply due to a physical limitation of the architecture, because we actually only have 20 completely parallel CPUs at our disposal for the experiments. In this case, the last 20 processes are forced to wait for the first 20 processus, which has the effect of doubling the execution time. If we had 40 CPUs completely parallel we could have obtained exactly the same results in twice less time. If we take into account only the quality of the solutions, two main informations can be extracted from this table.

1) Impact of the number of iterations: Firstly, when fixing the same number of processes and varying the number of iterations, we do not observe any significant change in performance, even with a much larger budget. Indeed, whether it is for 10, 20 or 40 processes, we almost have the same deviation even with a twice same budget.

From Figure 3, we can observe the evolution of the average deviation (for 20 independents runs) through the algorithm Fig. 3. Impact of increasing the number of iterations progress. For 10 and 40 processes, increasing the number of TSiterations from 350 to 1 500 does not improve quality. The only change that can be noted (but which remains very small and cannot be distinguished on the figure) is when using 20 processes. In this case, doubling the budget from 1 500 000 to 3 000 000 evaluations brings an improvement of 0.8% in the average deviation.

Our conclusion is confirmed in Figure 4, showing the best solution obtained by each algorithm setting after 10, 20, 50 and 100 global iterations (Giterations). We want to see if, at any moment of the execution, one of the configuration takes the advantage. All we can say is that for all the reported results, none of the configurations take the advantage, considering the same number of processes.

These results suggest that increasing the number of iterations in the TS does not help the search process while increasing the overall number of evaluations. Moreover, for an equivalent budget, the experiments show that it is more beneficial to set a smaller number of iterations. For example, for a budget of 1 500 000 evaluations, it is more beneficial to have 20 processes with 750 iterations each (which gives an average deviation of 15.01%) than 10 processes with 1500 iterations each (which gives an average deviation of 17.96%)

2) Impact of the number of processes: The second main finding from Table IV is the behavior of the algorithm when using the same number of iterations and varying the number of processes. Increasing the number of processes has obviously the effect of increasing the overall budget. Nevertheless, unlike the first case, this increase leads to a clear improvement of performance. Indeed, if we consider a setting with 750 TSiterations, doubling the budget from 1 500 000 (20 processes and 750 TSiterations) to 3 000 000 (40 processes and 750 TSiterations) allows us to improve the average deviation by 2.69% (from 15.01% to 12.32%).

Figure 5 clearly shows that scaling the number of processes has then a positive impact on the results. The use of 40 parallel processes, with the same budget for each process, improves significantly the average deviation. This is confirmed in Figure 6 showing the obtained deviation at different steps of the search process (i.e., using different termination criteria). Through this figure, we can observe the best solution obtained by each algorithm setting after 10, 20, 50 and 100 global iterations (Giterations). If we consider the case of the 350 iterations (left column), the use of 40 processes outperforms the use of 20 and 10 processes for all the iterations level (10, 20, 50 and 100) that can be seen in Figure 6. This results means that the increase of the budget with the increase of the number of processes is beneficial.

D. Discussion

In this work, we propose a very simple parallel model to solve QAP, with a particular focus on the tai343e01 instance. The landscape of this instance seems to need a very small number of iterations (few intensification search). Indeed, increasing the budget has no impact, unless we increase the number of processes. Through this point, we try to show that, in the parallelization, it is essential to find the good distribution, so that the search process becomes more efficient.

Generally speaking, in the literature, the use of parallelization is focused on maximizing the budget without worrying about the landscape and how to distribute this budget.

A good instance for parallelization is an instance that can be solved efficiently when we maximize the number of processes 1500 and minimize the execution time on each process. This is the case of instances that need many search from multiple starting solutions such as the instance tai343e01.

The best results we could get are with 350 iterations × 100 Ro-Ts × 40 processes (a total budget of 1 400 000). The average deviation from the BKS on 20 independent executions is 12.19% and we obtain a deviation of 8.78% for the best attempt in only 13 minutes. These results outperform the deviation obtained in the literature with the Ro-Ts algorithm [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF] using a smallest budget (1 400 000 evaluations against 1 619 120 for [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF]).

Table V shows the average deviation as well as the calculated time in minutes for the 20 independent executions of our best configuration (350 iterations × 100 Ro-Ts × 40 processes).

The results obtained in this paper are easily exploitable and interesting on hybrid genetic algorithms. Indeed, each process can represent an individual of the population. The random perturbation can be replaced by a crossover between the best solution found in the population and the best local solution of each process. The hybridization of the algorithm can be done thanks to the tabu search proposed in this work. Moreover, the analysis shows that in the case of the instance studied in this article, it is beneficial to increase the number of processes that can execute a small number of iterations. This configuration can be very effective in the context of a hybrid genetic algorithm.

Another obvious use of this paper results, is the improvement of the existing evolutionary algorithm. For example, in the case of [START_REF] Tosun | On the performance of parallel hybrid algorithms for the solution of the quadratic assignment problem[END_REF], it is possible to improve the last part of their algorithm with the parallelization of the tabu search applied to the best individual obtained by their genetic algorithm.

V. CONCLUSIONS AND PERSPECTIVES

In this work, we have presented and experimented a parallel approach for QAP. This approach demonstrates efficient results on the set of benchmark instances experimented. We evaluated our approach on 5 benchmark instances from the QAPLIB, and we showed that the algorithm was able to obtain competitive results compared against several variants from the literature. We also analyzed the tai343e01 instance from [START_REF] Drezner | Recent Advances for the Quadratic Assignment Problem With Special Emphasis on Instances that are Difficult for Meta-Heuristic Methods[END_REF]. This analysis represents the main motivation for this work.

In summary, two main contributions are proposed in this work. The first one is to propose a parallel variant of the Ro-Ts, able of performing well on small-to medium-size instances as well as on large-size instances, simply by changing a few set of parameters. The second, and most important contribution, is a deeper analysis of a large-size instance for the well known QAP, in order to find the right distribution of the budget in the parallel context.

In future works, there are several possible ways to extend this work. One possibility is to experiment the impact of other potential solution exchange strategies through the creation of a set of local optima produced by the parallel processes, and by choosing one of them following a particular strategy. Another possibility is to study the landscape of the other large-size instances in order to propose a good tuning to solve these instances and to see if they share a similar landscape topology.

Algorithm 1

 1 The general PITS algorithm 1: Input: perturb: % perturbation; cost: cost of the current solution; Fcost: best cost found; solution: current solution; LBsolution: local best solution found; GBsolution: Global best solution found between all the processes; Nbr-Pro: Number of parallel processes executed; TSiterations: Number of the Ro-Ts iterations; Giterations: Number of global PITS iterations. 2: for all P in NbrPro do

16 :

 16 Receives all the LBsolution from the other processes 17:

  the GBsolution from the master process 23: Random Perturbation of GBsolution; 24: Update a new solution to start a new global iteration; 25: end for 26: end for Algorithm 2 One TSiteration of the Ro-Ts

Fig. 1 .

 1 Fig. 1. PITS algorithm

Fig. 2 .

 2 Fig. 2. Average deviation of 20 trials (20 processes and 1500 TSiterations)

Fig. 4 .

 4 Fig. 4. Impact of increasing the number of iteration -details.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Impact of the variation in the number of processes.

  : if movement is tabu but meets all aspiration criteria or is not tabu and is a new Tcost then

	3:	Store the best permutation indexes that meet all condi-
		tions;
	4: end if
	5: Update tabu list;
	6: Update solution;

1: Input: cost: cost of the current solution; solution: current solution; Fsolution: best solution found; Tcost: best cost found inside the TS; Tsolution: best solution found inside the TS; 27: if the cost is better than the Tcost then 8: Update the Tsolution with solution; 9: end if 10: Update the delta matrix of the move costs;

TABLE I PARAMETERS

 I

			OF THE FIRST EXPERIMENTS
		Parameter		Value
		NbrPro		20
		TSiterations		100 × n
		Giterations		100
		percentage of perturbation	20%
			TABLE II
			RESULTS
	Instances BKS	PITS deviation CPUt(min) deviation CPUt(min) deviation CPUt(min) CPTS PILS
	tai40a 3139370 0.216(0)	0.53	0.148(1)	3.5	0.280(0)	12.0
	tai50a 4938796 0.486(0)	1.04	0.440(0)	10.3	0.663(0)	11.2
	tai60a 7205962 0.532(0)	1.81	0.476(0)	26.4	0.820(0)	7.4
	tai80a 13515450 0.662(0)	4.36	0.691(0)	94.8	0.927(0)	12.7
	tai100a 21052466 0.597(0)	8.67	0.589(0)	261.2	1.027(0)	9.8
	Average	0.499(0)	3.28	0.469(1)	79.24	0.743(0)	10.62

TABLE III PARAMETERS

 III OF THE LARGE SCALE EXPERIMENTS

		Parameter		Value
		NbrPro		{10, 20, 40}
		TSterations		{350, 750, 1500}
		Giterations		100
		percentage of perturbation	20%
	Best deviation	20
		1	10	100
			Global iterations

TABLE IV RESULTS

 IV SHOWING THE VARIATION OF ITERATIONS OR PROCESSES

	NbrPro/TSiterations	Budget	Deviation	CPUt(min)
	10/350	350 000	17.22%	6.28
	10/750	750 000	17.59%	12.48
	10/1500	1 500 000	17.96%	24.11
	20/350	700 000	15.11%	6.47
	20/750	1 500 000	15.01%	12.52
	20/1500	3 000 000	14.21%	24.17
	40/350	1 400 000	12.19%	13.01
	40/750	3 000 000	12.32%	25.89
	40/1500	6 000 000	13.06%	49.69

• Cooperative parallel tabu search (CPTS)[START_REF] James | A cooperative parallel tabu search algorithm for the quadratic assignment problem[END_REF]; • Population-based iterated local search (PILS)[START_REF] Stützle | Iterated local search for the quadratic assignment problem[END_REF].

ACKNOWLEDGEMENT

Experiments presented in this paper were carried out using the Grid'5000 testbed (http://www.grid5000.fr). Therefore, we would like to thank the Grid'5000 team. Grid'5000 is supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations.


Irene Castañeda
email: irene.castaneda@u-psud.fr

C Bellard

I Jari

B Pisanu

J.-L Chapuis

E Bonnaud

Trophic patterns and home-range size of two generalist urban carnivores: a review

Keywords: diet, home range, red fox, domestic cat, anthropogenic habitats, trophic pattern, urban carnivores, predation

Foxes and cats are the most abundant medium-sized urban carnivores. To date, however, there has been a lack of effort to synthesize data on the spatial and trophic resources used by these two carnivores, despite the importance of this information for assessing their similarity and roles in urban food webs. In this paper, we first synthesize all available information on the trophic patterns and home-range size of these two predators based on a total of 91 studies. Second, we conduct statistical analyses to test the influence of environmental and biological variables such as regional differences, habitat characteristics, age, and sexual status on their home-range size and diet patterns within urban habitats, and then evaluate the methods used to investigate these components. Our findings highlight the lack of studies that simultaneously monitor the diet and home-range size of both predators within urban habitats. To the best of our knowledge, this is the first study to compare fox and cat home-range size and diet. Foxes exhibited larger ranges than cats, while intact cats showed larger home ranges than desexed cats. Diet diversity obtained for both predators confirmed their trophic plasticity within urban habitats. Both predators consumed fewer mammals and invertebrates in highly disturbed habitats compared to medium ones. We also found that the procedure of data acquisition significantly influenced fox and cat home-range sizes. In terms of diet, the type of recovered samples had a significant effect on the diet composition of both predators. To improve our understanding of the relative impact of these two urban carnivores on urban wildlife, we recommend simultaneously studying both species in future studies. Moreover, methodological standards for both diet and home-range size studies are needed to allow comparisons.

Introduction

Among medium-sized (<5 kg) carnivore species, red foxes (Vulpes vulpes) and domestic cats (Felis silvestris catus) (hereafter foxes and cats, respectively) are the most abundant species associated with human settlements [START_REF] Flockhart | Predicting free-roaming cat population densities in urban areas[END_REF][START_REF] Lombardi | Coyote, fox, and bobcat response to anthropogenic and natural landscape features in a small urban area[END_REF]. Foxes are one of the most widespread carnivores; while they originated from the Middle East [START_REF] Statham | Range-wide multilocus phylogeography of the red fox reveals ancient continental divergence, minimal genomic exchange and distinct demographic histories[END_REF], today they are present in all continents with the exception of Antarctica. Specifically, British foxes derived from Central European populations [START_REF] Edwards | Temporal genetic variation of the red fox, Vulpes vulpes, across Western Europe and the British Isles[END_REF], North American foxes differ from their European counterparts [START_REF] Sacks | A restricted hybrid zone between native and introduced red fox (Vulpes vulpes) populations suggests reproductive barriers and competitive exclusion[END_REF][START_REF] Leite | Differentiation of North African foxes and population genetic dynamics in the desert-insights into the evolutionary history of two sister taxa, Vulpes rueppellii and Vulpes vulpes[END_REF], while Australian foxes were introduced by humans from Europe [START_REF] Macdonald | Red fox Vulpes vulpes Linnaeus, 1758 (Least concern, 2004)[END_REF]. Cats were probably domesticated in the early Neolithic period (i.e. 9000 years ago; [START_REF] Driscoll | The Near Eastern origin of cat domestication[END_REF], becoming ubiquitous residents of human settlements. The habitat use [START_REF] Gehring | Body size, niche breadth, and ecologically scaled responses to habitat fragmentation: mammalian predators in an agricultural landscape[END_REF][START_REF] Saito | Trait-dependent changes in assemblages of mid-sized and large mammals along an Asian urban gradient[END_REF] and foraging behavior [START_REF] Mirmovitch | Spatial organisation of urban feral cats (Felis catus) in Jerusalem[END_REF][START_REF] Contesse | The diet of urban foxes (Vulpes vulpes) and the availability of anthropogenic food in the city of Zurich Switzerland[END_REF] of these two species allow them to establish urban populations [START_REF] Bateman | Big city life: carnivores in urban environments[END_REF], as they make use of a wide range of wild and anthropogenic resources through fragmented urban landscapes [START_REF] Meckstroth | Diets of introduced predators using stable isotopes and stomach contents[END_REF][START_REF] Krauze-Gryz | Annual variation in prey composition of domestic cats in rural and urban environment[END_REF].

In human-altered habitats, home-range sizes have been studied for over 50 years for foxes [START_REF] Storm | Movements and activities of foxes as determined by radio-tracking[END_REF] and over 30 years for cats [START_REF] Panaman | Behaviour and ecology of freeranging female farm cats (Felis catus L.)[END_REF]. The home-range size of urban foxes [START_REF] Gloor | The rise of urban foxes (Vulpes vulpes) in Switzerland and ecological and parasitological aspects of a fox population in the recently colonised city of Z€ urich[END_REF][START_REF] Gosselink | Temporal habitat partitioning and spatial use of coyotes and red foxes in East-Central Illinois[END_REF] is usually greater than that of cats [START_REF] Mirmovitch | Spatial organisation of urban feral cats (Felis catus) in Jerusalem[END_REF][START_REF] Barratt | Home range size, habitat utilisation and movement patterns of suburban and farm cats Felis catus[END_REF][START_REF] Schmidt | Survival, fecundity, and movements of free-roaming cats[END_REF]. Adult foxes use larger areas than juveniles do [START_REF] Rosatte | The ecology of red foxes, Vulpes vulpes, in metropolitan Toronto, Ontario -disease management implications[END_REF], while the opposite has been recorded for urban cats [START_REF] Morgan | Urban cat (Felis catus) movement and predation activity associated with a wetland reserve in New Zealand[END_REF]. Males display larger home-ranges than females for both foxes [START_REF] White | Spatio-temporal patterns of home range use by foxes (Vulpes vulpes) in urban environments[END_REF] and cats [START_REF] Liberg | Density, spatial organisation and reproductive tactics in the domestic cat and other felids[END_REF]. Although the sexual status of cats may heavily influence home-range size within urban areas [START_REF] Baker | Domestic cat (Felis catus) and domestic dog (Canis familiaris). In Urban carnivores: ecology, conflict and conservation[END_REF], previous findings did not show any difference between intact and desexed individuals [START_REF] Guttilla | Effects of sterilization on movements of feral cats at a wildlandurban interface Effects of sterilization on movements of feral cats at a wildlandurban interface[END_REF][START_REF] Hall | Factors determining the home ranges of pet cats: A meta-analysis[END_REF]. However, current home-range sizes are inferred using a wide range of calculation methods, making it difficult to disentangle the role of habitats and species specificities to explain variations [START_REF] Laver | A critical review of home range studies[END_REF].

The diet of generalist predators such as foxes and cats depends on prey abundance that may vary temporally and spatially [START_REF] Paltridge | The diets of cats, foxes and dingoes in relation to prey availability in the Tanami Desert, Northern Territory[END_REF][START_REF] Krauze-Gryz | Annual variation in prey composition of domestic cats in rural and urban environment[END_REF]. Birds and small rodents are usually found in fox and cat diets within urban and suburban habitats [START_REF] Meckstroth | Diets of introduced predators using stable isotopes and stomach contents[END_REF][START_REF] Krauze-Gryz | Annual variation in prey composition of domestic cats in rural and urban environment[END_REF]. The diet of urban or suburban foxes and cats is also characterized by the use of anthropogenic refuse as a food resource [START_REF] Mirmovitch | Spatial organisation of urban feral cats (Felis catus) in Jerusalem[END_REF][START_REF] Contesse | The diet of urban foxes (Vulpes vulpes) and the availability of anthropogenic food in the city of Zurich Switzerland[END_REF]. However, diet analyses may be affected by the method used to infer prey composition and abundance (e.g. carried home vs. eaten in situ; [START_REF] Krauze-Gryz | Annual variation in prey composition of domestic cats in rural and urban environment[END_REF].

Comparisons between fox and cat home-range size or diet are needed in order to determine the similarities and differences regarding these two key ecological features. This knowledge would help us to understand and quantify the impact of these predators, which could exert synergic predation on the same prey populations. Simultaneous monitoring of fox and cat home-range size or diet has been conducted in wild habitats, showing high similarities between the two species [START_REF] Catling | Similarities and contrasts in the diets of foxes, Vulpes vulpes, and Cats, Felis catus, relative to fluctuating prey populations and drought[END_REF][START_REF] Molsher | The ecology of feral cats, Felis catus, in open forest in New South Wales: interactions with food resources and foxes[END_REF][START_REF] Risbey | The impact of cats and foxes on the small vertebrate fauna of Heirisson Prong, Western Australia. I. Exploring potential impact using diet analysis[END_REF][START_REF] Krauze-Gryz | The good, the bad, and the ugly: space use and intraguild interactions among three opportunistic predators-cat (Felis catus), dog (Canis lupus familiaris), and red fox (Vulpes vulpes)-under human pressure[END_REF]. Recently, it was demonstrated that in such habitats (foreshores of Lake Burrendong), fox removal results in a decrease in cat home-range size and an increase in cat consumption of invertebrates and carrion [START_REF] Molsher | Mesopredator management: effects of red fox control on the abundance, diet and use of space by feral cats[END_REF]. Within human-altered habitats, the abundance and impact of these predators can strongly vary, meaning that ecological information is required to improve management and/or control measures.

In this paper, we conducted an extensive literature review to compare fox and cat home-range size and diet patterns in urban and suburban habitats. Our aims were first to summarize available knowledge on these two key ecological components for both species, which are currently understudied in comparative studies despite their similar role as predators in urban ecosystems, and examine the possible competition between the two species. Based on current knowledge, we expected that foxes and cats would exhibit similar home-range size and diets, with species-specific biological features and habitat properties influencing home-range size. Second, we aimed to test how the distinct methodologies used to analyze diet or space use would consistently alter the biological inferences in comparative studies. Finally, we aimed to discriminate the environmental variables (i.e. level of disturbance) that could explain differences in home-range size and diet for both predators.

Materials and methods

Sample selection criteria

First, we conducted a complete literature review using the online bibliographic database ISI Web of Knowledge to search for studies monitoring foxes and cats in urban and suburban habitats (Fig. 1). Specifically, we used the following keywords for foxes ('Vulpes vulpes' OR 'fox'), cats ('Felis silvestris catus' OR 'Felis catus' OR 'cat'), and urban and suburban habitats ('urban' OR 'suburban' OR 'exurban' OR 'city' OR 'metropolitan' OR 'municipal' OR 'non-rural' OR 'peri-urban'). The keywords were combined as follows: one predator species AND one urban synonym. We then refined results by selecting the following categories from the Web of Science: zoology, ecology, biodiversity and conservation, multidisciplinary sciences, biology, evolutionary biology and development biology. We also explored references in the literature of the selected papers. We automatically screened the abstract and title of each relevant publication using R programming language (version 1.1.423) with functions from the 'tm' package. First, we removed punctuation, whitespaces, and link words to analyze the words within the titles and abstracts. Second, we used the 'grepl' function to search the words related to diet and home-range size (i.e. 'diet', 'intake', 'nutrition', 'food', 'menu', 'aliment', and 'comestible' for diet, and 'spatial use', 'home range', 'movement pattern', 'territory' and 'utilization distribution' for home range size). Finally, publications containing these words were screened manually. We retained studies that: (1) focused on foxes and/or cats; (2) were conducted in urban or suburban areas; and (3) described homerange size and/or (4) quantified diet. This resulted in a total of 91 studies. For each study, we reported the region (Africa, Asia, Europe, North America, or Oceania), location of the study site, home-range size, as well as diet information.

Home-range size

Home-range size can be calculated using different methods that are listed in Table 1. Each method can be assessed using a predetermined percentage of independent fixes. For each study, we recorded the number of independent fixes used to calculate home-range size, the temporal interval of these fixes, and the data acquisition procedure (i.e. triangulation or automatic localization). We also reported the weight of the collars used and the animals studied. The age (juvenile or adult), sex and sexual status (intact or desexed) were taken into account as biological characteristics of the studied individuals.

Diet patterns

Diet in the selected studies was based on the analysis of scats, stomachs and prey items brought to the owner's home. For each study, we recorded the sample types, sample sizes and number of prey categories. We considered eight main prey categories: mammal, bird, reptile, amphibian, invertebrate, fish, fruit and anthropogenic refuse. Then, we calculated the percentage of relative frequency of occurrence (% RFO) as the number of occurrences of each prey category multiplied by 100 and divided by the total number of occurrences of all prey categories in all samples. We also determined diet diversity using Levin's standardized index (B A ) [START_REF] Krebs | Chapter 14: Niche measures and niche preferences[END_REF] with the following formula:

where n is the number of prey categories and P is the proportion of records for each prey category (i). The standardized form of the formula is thus: where B is Levin's index of niche breadth and B max is the total number of prey categories. B A ranges from 0 to 1. For a complete generalist individual B A = 1, while the value decreases with greater specialization.

Additional variables

Although the selected studies were conducted in urban and suburban areas, in order to quantify the degree of anthropogenic habitat pressure, we used the Anthropogenic Biomes of the World spatial layer, Version 2: 1900-2000 [START_REF] Ellis | Anthropogenic transformation of the biomes, 1700 to 2000[END_REF]. This database represents a global spatial dataset of the anthropogenic transformation of the biosphere through direct human interaction with ecosystems for the period 1900-2000, including agriculture and urbanization. Anthropogenic transformation within each biome is estimated using population density, agricultural intensity (cropland and pastureland) and urbanization. The biomes are divided into 19 subclasses and grouped in six main classes: dense settlements (urban and other dense settlements), villages (dense agricultural settlements), croplands (land used mainly for annual crops), rangelands (land used mainly for livestock grazing and pasture), semi-natural lands (inhabited land with minor use for permanent agriculture and settlements) and wild lands (land without human populations or substantial land use). We excluded the classes of semi-natural and wild lands, because this study focuses on urban and suburban habitats. We then reclassified the four remaining classes into two categories given the low number of studies found in each category: high anthropogenic pressure (HAP) (dense settlements and villages) and medium anthropogenic pressure (MAP) (croplands and rangelands). The degree of anthropogenic pressure was determined using a buffer (based on mean home range in each study) around the central point of the study location. We plotted the localizations in R Studio (R Core Team, 2016) using raster [START_REF] Hijmans | raster: geographic data analysis and modeling[END_REF], sp [START_REF] Hijmans | Package 'sp[END_REF], rgdal (Bivand et al., 2018a), and rgeos [START_REF] Bivand | rgeos: Interface to Geometry Engine -Open Source[END_REF] packages.

Statistical analysis

For each dataset (53, 33 and 20 studies for the global, fox, and cat home-range size models, respectively), we first calculated variance inflation factors to detect collinearity. A cut-off value of 3 can be used to remove collinear variables [START_REF] Zuur | Mixed effects models and extensions in ecology with R[END_REF]). Home range estimates as the dependent variable were log-transformed prior to analyses to ensure normality and homogeneous variances. Because observations were not independent (i.e. multiple observations within the same study), we used linear mixed models to fit the statistical models. First, we constructed a full model with all likely influencing variables (calculation method, procedure of data acquisition, region, habitat and predator species) for the home-range size (Table S1). We included study.ID and animal.ID (individuals or group of individuals within studies) as random factors in order to take into account variations between and within studies. Then, we selected by a stepwise backward elimination procedure of the least significant terms (P > .05) to determine the best adequate minimal model (i.e. the best-performing model had the best trade-off between goodness of fit and model simplicity). We analyzed two full additional models, one for each predator species (Table S1). In these models, in addition to study.ID and animal.ID, we included the calculation method as the random factor because of its significant influence on homerange size estimations.

Diet data was described using the diet diversity index and % RFO of prey categories. As not all eight prey categories were reported in the studies, only the prey categories with at least 10 observations > 0% RFO were used to fit the models. Diet diversity was sine-transformed before analysis, and the % RFO of the main reported prey categories (mammals, birds and invertebrates) were square-root transformed before analysis to ensure normality and homogeneous variance. Because observations were not independent (i.e. multiple observations within the same study), we also used linear mixed models with the study.ID as random variables to analyze diet diversity and variation in the % RFO (Table S1). The Kenward-Rogers method was used to generate the approximate denominator degrees of freedom. Post-hoc multiple comparisons of means were conducted using the Bonferroni test. All analyses were performed in R studio. We used the lmer functions from the 'lme4' package [START_REF] Bates | The lme4 package[END_REF], the step function from the 'lmerTest' package [START_REF] Kuznetsova | lmerTest: tests in linear mixed effects models[END_REF], corvif from the 'lsmeans' package [START_REF] Lenth | Least-squares means: the R Package lsmeans[END_REF], and glht from the 'multcomp' package [START_REF] Hothorn | The multcomp package[END_REF](Hothorn et al., , 2010)).

Results

We obtained a total of 91 studies dating from 1934 to 2016, of which 43 studies exclusively reported home range (28 for foxes and 15 for cats), 10 studies involved both home-range size and diet (five for foxes and five for cats) and 38 studies addressed diet (15 for foxes, 22 for cats and 1 for both foxes and cats) (Table S2 for home range and S3 for diet studies). Overall, 62 studies were carried out in MAP habitats, while 28 studies were conducted in HAP habitats. Regarding regions, 38 studies were carried out in Europe, 30 in North America, 15 in Oceania, six in Asia, and only one in Africa. By consequence, studies from Asia and Africa were not included in the statistical models.

Home-range size

The best models to predict home-range size of red foxes and cats within urban habitats are shown in Table S1 in Supporting Information. A synthesis of the analyzed studies on homerange size is available in Table S2 in Supporting Information.

A positive trend was observed in publication output on home-range size for different home-range calculation methods used (Figure S1a). However, publishing rate was relatively low, when compared with the general publishing rate within the Web of Science (Figures S1b andS2).

Among the 53 home-range size studies analyzed, homerange sizes were generally monitored for both males and females in 45 of the analyzed studies (85%), with the number of studied individuals ranging from one (4%) (i.e. [START_REF] Macdonald | Social factors affecting reproduction amongst Red Foxes, Vulpes vulpes. In The red fox[END_REF] to 55 [START_REF] Haspel | Home range of freeranging cats (Felis catus) in Brooklyn, New York[END_REF]. Thirty-eight studies (72%) only monitored adult home-range size. Thirty-three studies (64%) reported the number of independent fixes, ranging from 20 [START_REF] Hough | The ranging behavior of a maturing female red fox, Vulpes vulpes[END_REF] to 24 202 [START_REF] Woollard | A behavioural comparison of dispersing and non-dispersing foxes (Vulpes vulpes) and an evaluation of some dispersal hypotheses[END_REF]. The most frequent method for data acquisition was triangulation (85%), followed by automatic localization (13%). The majority of studies (76%) used only a single method to calculate home-range size, while 23% used at least two methods. Only a single study [START_REF] Gehrt | Population ecology of free-roaming cats and interference competition by coyotes in urban parks[END_REF] calculated home-range size using three different methods (MCP, fixed kernel, and local convex hull). The two most frequently used calculation methods were MCP 100% and kernel density estimation 95%. MAP habitats were more represented in the dataset (68%) compared to HAP habitats (32%). Most home-range studies were conducted in Europe (40%), followed by North America (32%), Oceania (19%), Asia (8%) and Africa (2%).

Within predator species, foxes exhibited significantly larger home ranges than cats (118.00 AE 30.81 ha and 77.40 AE 27.27 ha, respectively) (Table 2, Fig. 2b).

With respect to the factors that might separately be able to influence the home-range size of each species, fox home-range size was significantly affected by the life stage of individuals (F 1,2 = 6.84, P = .0096). Juvenile foxes exhibited significantly smaller home-range sizes compared to adults (102.46 AE 32.06 ha and 176.88 AE 38.94 ha, respectively) (Table 2; Fig. 2c). Cat home-range size was affected by the sexual status of the individual (F 1,2 = 24.56, P = 2.015e-06), with larger values observed for intact cats compared to desexed cats (77.64 AE 30.45 ha and 2.33 AE 1.29 ha, respectively) (Table 2; Fig. 2d).

Home-range size of both predators was significantly affected by the calculation methods (F 5,6 = 47.67, P < 2.2e-16), procedure of data acquisition (F 1,2 = 9.38, P = .0033), and predator species (F 1,2 = 17.04, P = .0003). Although calculation method is one of the significant factors influencing home-range size, this is only due to the different percentage of fixes among the methods; by contrast, the home-range sizes obtained using the same percentage of fixes (e.g. Fixed Kernel 95% vs. MCP 95%) were not significantly different (Table 2). Data acquisition using triangulation produced significantly larger home ranges than the automatic localization of individuals (107.50 AE 24.86 ha and 57.42 AE 28.79 ha, respectively) (Table 2; Fig. 2a).

Diet patterns

The best models to predict diet patterns of red foxes and cats within urban habitats are shown in Table S1 in Supporting Information. A synthesis of the analyzed studies on diet is available in Table S3 Supporting Information. As with studies on home-range size, there was a weak positive trend in publication output on fox and cat diet for different diet samples used (Figure S1b), but the publishing rate was considerably lower than the general growth rate of scientific publication (Figure S2).

Among the 48 diet studies analyzed, 20 analyzed fox diet (42%), 27 cat diet (56%) and one both predator diets [START_REF] Meckstroth | Diets of introduced predators using stable isotopes and stomach contents[END_REF]. The most frequently reported type of diet samples for cats were items brought to the owners' house (42%), whereas scats were the most frequent sample type for foxes (44%). Sample sizes ranged from 25 [START_REF] Cavallini | Ranging behavior of the red fox (Vulpes vulpes) in rural Southern Japan[END_REF] to 14 370 [START_REF] Woods | Predation of wildlife by domestic cats Felis catus in Great Britain[END_REF]. The number of prey categories ranged from one to seven, with a mean of four categories per study. MAP habitats (77%) were more frequent than HAP habitats (27%) among diet studies, which were mostly conducted in Europe (44%), followed by North America (31%), Oceania (17%) and Asia (8%). No diet studies were carried out in Africa.

We calculated diet diversity based on the % RFO of prey categories contained in diet studies, showing that foxes had a similar diet diversity (0.44 AE 0.05) to cats (0.39 AE 0.03). The principal prey category in fox and cat diet studies were mammals (48 and 71%, respectively). The secondary prey category in fox studies was anthropogenic refuse (19%) and in cat studies was invertebrates (4%) and anthropogenic refuse (4%) as well. Mean diet diversity was slightly higher in HAP habitats (0.49 AE 0.06) than MAP habitats (0.38 AE 0.03). Across regions, diet diversity was slightly higher in Asia (0.47 AE 0.16) compared to the other regions (Europe: 0.44 AE 0.05; N. America: 0.39 AE 0.04, and Oceania: 0.37 AE 0.04). Nevertheless, diet diversity was not significantly influenced by region, degree of anthropogenic habitat pressure, type of samples, or predator species (Table 3).

The % RFO of invertebrates was significantly affected only by the % RFO of the two other main prey categories of mammals (F 1,1 = 48.35, P = 1.35e-09) and birds (F 1,1 = 14.19, P = .0003), as well as the type of habitat (F 1,2 = 4.31, P = .0419). When the % RFO of birds and mammals increased, the % RFO of invertebrates decreased (Fig. 3a,b, respectively). Diet comprised a lower % RFO of invertebrates in HAP compared to MAP habitats (Fig. 3c). The % RFO of mammals was also significantly affected by the type of habitat (F 1,2 = 9.26, P = .0032). We found that both predators fed significantly less on mammals in HAP compared to MAP habitats (Table 3; Fig. 3d). The % RFO of birds was significantly affected by the type of samples (F 2,3 = 29.39, P = 2.316e-10) and predator species (F 1,2 = 10.22, P = .0024). The % RFO of birds was significantly lower in scats and stomachs than prey items. Moreover, foxes consumed significantly more birds than cats did (Table 3; Fig. 3d).

Discussion Home-range size

To our knowledge, this is the first study to compare fox and cat home-range size within urban and suburban habitats based on the published literature. We found that foxes exhibit larger home ranges than cats in human-altered habitats (118.00 AE 30.81 ha and 77.40 AE 27.27 ha,respectively). This result suggests that the degree of these predators' relation with humans likely explains their home-range size. Because foxes are wild carnivores, they must find their own food resources and shelter sites, while cats rely on humans to obtain these resources [START_REF] Moodie | The potential for biological control of feral cats in Australia[END_REF]. In wild land habitats, such as open forests in New South Wales, [START_REF] Molsher | The ecology of feral cats, Felis catus, in open forest in New South Wales: interactions with food resources and foxes[END_REF] found fox and cat home-range sizes to be similar, thus supporting our hypothesis that the respective wild and domestic character of foxes and cats may explain the larger home ranges of foxes in the selected studies. Compared with other urban carnivores, the home-range sizes found for foxes and cats in this study are smaller than those of jackals in farmlands near the town of Dinsho in southern Ethiopia [START_REF] Admasu | Spatial ecology of the white-tailed mongoose in farmland in the Ethiopian Highlands[END_REF], similar to those of urban dingoes in peri-urban areas of Queensland [START_REF] Allen | Dingoes at the doorstep: preliminary data on the ecology of dingoes in urban areas[END_REF] probably due to the smaller body size of jackals compared to dingoesand larger than those of freeroaming domesticated male dogs in the city of Puerto Natales (Chile) [START_REF] Perez | Movement and home range of home range of owned free-roaming male dogs in Puerto Natales. Chile[END_REF] probably due to the dogs' high site fidelity to their owner's home as described by the authors.

The lack of significant influence of environmental variables (habitat and region) on fox and cat home-range size suggests that the predators' spatial behavior is similar at these scales. Our findings showed that juvenile foxes were characterized by smaller home ranges than adults (102.46 AE 32.06 ha and 176.88 AE 38.94 ha, respectively), which is consistent with previous studies conducted in similar habitats (i.e. [START_REF] Frafjord | Winter range of a red fox (Vulpes vulpes) group in a northern birch forest[END_REF][START_REF] Rosatte | The ecology of red foxes, Vulpes vulpes, in metropolitan Toronto, Ontario -disease management implications[END_REF] and with juvenile philopatry [START_REF] Baker | Potential fitness benefits of group living in the red fox, Vulpes vulpes[END_REF][START_REF] Robertson | Ranging behaviour of juvenile red foxes and its implications for management[END_REF].

Regarding cats, only sexual status affected their home-range size. Specifically, intact cats displayed larger home ranges than their desexed counterparts (77.64 AE 30.45 ha and 2.33 AE 1.29 ha, respectively), which might indicate the behavioral effects of sterilization. This result contrasts with the available data for feral cats [START_REF] Guttilla | Effects of sterilization on movements of feral cats at a wildlandurban interface Effects of sterilization on movements of feral cats at a wildlandurban interface[END_REF] as well as pet and farm cats [START_REF] Hall | Factors determining the home ranges of pet cats: A meta-analysis[END_REF] in which desexing did not reduce home-range size. Thus, while cat sterilization may reduce home-range size, its impact could be more concentrated (not lower). Future studies should delimit the extent of these biological features on cat home-range size in order to better understand the spatial ecology of cats. Our results showed that the home-range size of both predators obtained using the same percentage of fixes did not differ, thus supporting the reliability of assessed home-range sizes as determined with different calculation methods but the same percentage of fixes. Home-range sizes estimated with triangulation were 50% larger than those estimated with automatic localizations, which led to overestimating the activity areas of monitored individuals and consequently the spatial delimitation of their different activities (i.e. reproduction, rest, feeding). This difference in home-range size obtained using the triangulation or automatic localization of individuals may be due to the lower accuracy of the former method [START_REF] Springer | Some sources of bias and sampling error in radio triangulation[END_REF][START_REF] White | Effects of biotelemetry triangulation error on detecting habitat selection[END_REF]. Although the greater use of triangulation (80%) is probably due to the low costs of the equipment, we recommend using more accurate procedures such as the automatic localization of individuals, which, despite being more expensive, are much less time-consuming and currently better adapted to respond accurately to the spatial ecological questions.

Diet patterns

Our results show that fox and cat diet diversity was similar. To the best of our knowledge, this is the first study in which fox and cat diet diversity and composition have been compared within urban and suburban habitats. The lack of significance between fox and cat diet diversity contrasts with the results of [START_REF] Molsher | The ecology of feral cats, Felis catus, in open forest in New South Wales: interactions with food resources and foxes[END_REF] and [START_REF] Risbey | The impact of cats and foxes on the small vertebrate fauna of Heirisson Prong, Western Australia. I. Exploring potential impact using diet analysis[END_REF] who respectively found fox diet diversity to be significantly higher and lower than cat diet diversity. Mammals were the principal prey category in the reviewed fox and cat diet studies, while anthropogenic refuse (for foxes) and both anthropogenic refuse and invertebrates (for cats) were the secondary prey categories. Mammals were also the principal prey category in the studies conducted by [START_REF] Meckstroth | Diets of introduced predators using stable isotopes and stomach contents[END_REF] and [START_REF] Krauze-Gryz | Annual variation in prey composition of domestic cats in rural and urban environment[END_REF] in human-altered habitats. In addition, the use of anthropogenic refuse by the urban populations of foxes and cats has been highlighted by other authors (i.e. [START_REF] Mirmovitch | Spatial organisation of urban feral cats (Felis catus) in Jerusalem[END_REF][START_REF] Contesse | The diet of urban foxes (Vulpes vulpes) and the availability of anthropogenic food in the city of Zurich Switzerland[END_REF] in urbanized areas.

Compared with other urban carnivores, mammals were also the principal prey category of coyotes in the Denver urban area [START_REF] Poessel | Coyote (Canis latrans) diet in an urban environment: variation relative to pet conflicts, housing density, and season[END_REF], golden jackals in Serbia ( Cirovi c et al., 2014) and dingoes in peri-urban habitats of Queensland [START_REF] Allen | Diet of dingoes and other wild dogs in peri-urban areas of northeastern Australia[END_REF].

We showed that the consumption of the main reported prey categories (mammals, birds, and invertebrates) varied depending on the different factors considered: prey category, predator species, habitat, and type of recovered samples. There was a significant negative relationship between the consumption of invertebrates and vertebrates by both predators. This negative relation might be due to the nutrient composition of each prey category and/or the metabolism of the predators. For instance, the metabolic energy provided to free-ranging cats from invertebrate prey items is higher than those provided by birds or mammals [START_REF] Plantinga | Estimation of the dietary nutrient profile of free-roaming feral cats: possible implications for nutrition of domestic cats[END_REF]. We also found that both invertebrates and mammals were consumed at a lower rate in highly disturbed habitats. This result may reflect the influence of two non-exclusive effects: the high availability of anthropogenic food refuse, synanthropic birds and mammals, and ornamental fruits in more urbanized habitats [START_REF] Mckinney | Effects of urbanization on species richness: a review of plants and animals[END_REF] and/or the negative effect of urbanization on prey invertebrate and mammal populations, which are more abundant in highly disturbed habitats [START_REF] Gentili | Decreased small mammals species diversity and increased population abundance along a gradient of agricultural intensification[END_REF].

Even so, among the vertebrates consumed by foxes, birds represent a higher % RFO compared to those consumed by cats. This consumption preference of foxes highlights the need to specifically study the trophic behavior of generalist carnivore species, as it may have a contrasting impact in urban trophic webs. However, this result should be considered with caution, as the % RFO of birds highly depends on the type of sample recovered.

Foxes and cats may directly impact the abundance of urban prey (through predation) or indirectly by consuming anthropogenic food refuse (interference). This top-down effect of predators on prey species abundance has been described by [START_REF] Fischer | Urbanization and the predation paradox: the role of trophic dynamics in structuring vertebrate communities[END_REF] but it is rarely studied (cf. this review) in urban and suburban habitats, where two types of food resources may be found: natural and commensal. Thus, these two predators can have contrasting effects, as they can (i) negatively impact depleted populations of natural prey and/or (ii) control through predation the spatial and/or temporal boosting abundance of commensal prey.

Future directions

In a context of global change, widespread and potentially overabundant predators such as foxes and cats need further attention, as changes in their population dynamics may significantly disrupt ecosystem structure, function, and services.

We identified intra-and interspecific differences in the home-range sizes and diets of foxes and cats. The highly flexible spatial and trophic behaviors of foxes and cats demonstrated in this review will influence predator impacts on prey population dynamics, that will deserve further investigations and considerations to optimize management strategies in these human-altered habitats.

Although foxes and cats are two common predators, the future increase in urbanized areas will not have the same effect on these predator populations. While fox populations will lose their natural habitats, this species is able to efficiently use urban habitats to maintain or even increase their populations. It is also likely that the number of cats will continue to increase within urban areas, while the number of prey killed by cats will probably be higher than at present (i.e. [START_REF] Loss | Population impacts of freeranging domestic cats on mainland vertebrates[END_REF][START_REF] Woinarski | How many birds are killed by cats in Australia?[END_REF]. Thus, management policies based on their ecological features such as home-range size and diet patterns should be applied. We thus strongly advocate for more studies to investigate the home-range size and diet of these two generalist species in urban and suburban habitats following our recommendations regarding the design of such monitoring. Indeed, we detected a significant effect of methodology when investigating home-range size and diet of both predators. We also clearly detected the effects of biological and local environmental variables (degree of anthropogenic habitat pressure). Therefore, and not surprisingly, our findings suggest that future studies dealing with home ranges should be conducted with as many individuals as possible, a more even distribution of sexes, different age classes (i.e. juveniles and adults), and different sexual statuses (intact and desexed) when applicable.

Regarding diet studies, the types of samples recovered may influence the evaluation of diet composition, since they contain different proportions and types of prey. As highlighted in MAP habitats, cat diets are commonly studied through the analysis of scats and stomachs [START_REF] Pearre | Trends in the prey size-based trophic niches of feral and house cats Felis catus L[END_REF]Turner & Bateson, 2000), whereas in HAP habitats, prey items brought to the owner's house are more commonly assessed [START_REF] Kays | Ecological impact of inside/ outside house cats around a suburban nature preserve[END_REF][START_REF] Baker | Impact of predation by domestic cats Felis catus in an urban area[END_REF][START_REF] Flux | Seventeen years of predation by one suburban cat in New Zealand[END_REF]. We thus recommend encouraging cat owners to recover cat scats to allow for study comparisons. We also suggest indicating major taxonomic prey categories (mammalian, avian, etc.) as well as more precisely identifying the lower taxonomic categories (up to the level of species, when possible). Moreover, the % RFO is often an insufficient descriptor of predator diet [START_REF] Medina | Food habits of feral cats (Felis silvestris catus L.) in insular semiarid environments (Fuerteventura, Canary Islands)[END_REF]. Other suitable descriptors such as the minimum number of prey items contained in scats and ingested biomass are required to calculate different trophic indexes that will help to decipher predator diet, the consequences for prey populations, and predator-prey interactions more generally. Finally, we recommend simultaneously monitoring prey densities or using prey density data to provide more complete data on predation pressure and impact on prey populations.

Figure 1

 1 Figure 1 PRISMA diagram flow. * and synonyms.

Figure 2

 2 Figure 2 Estimated home-range size (ha) (log-transformed; means AE SE based on: (a) procedure of data acquisition, (b) predator species, (c) fox home-range size based on individual age, and (d) cat home-range size based on sexual status. Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05

Figure 3

 3 Figure 3 Predators' diet composition: (a) percentage of relative frequency of occurrence (% RFO) of invertebrate versus % RFO bird; (b) % RFO of invertebrate versus % RFO mammal; (c) % RFO invertebrate by habitat; MAP = medium anthropogenic pressure and HAP = high anthropogenic pressure; (d) % RFO mammal by habitat; (e) % RFO bird by predator species and sample types. Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 [Colour figure can be viewed at zslpublications.onlinelibrary.wiley.com].

Table 1

 1 Description of the variables used in statistical data analysis

		i
		RFO prey
	Diet diversity	(BA)
	Cat home-range	size (ha)
	Fox home-range	size (ha)
	Global home-range	size (ha)	U
		Levels	Fixed Kernel (95%) (FK 95%)	Kernel Density (50%) (KDE 50%)	Kernel Density (90%) (KDE 90%)
		Factor	Calculation	methods
		Group of variables	Methodological variables

U Kernel Density (95%) (KDE 95%) U Minimum Convex Polygon (100%) (MCP 100%) U Minimum Convex Polygon (75%) (MCP 75%)

Table 2

 2 Mixed linear model with log home-range size (ha) of both predator species (global model), red foxes (fox model), and domestic cats (cat model) as dependent variables, and the method of calculation, procedure of data acquisition, predator species, age and sexual status as explanatory variables. Monitored animal groups (nested within studies) and study ID were used as random variables, and in the fox and cat models, calculation methods were also used as random variables. Test statistics are given for the final model achieved by a stepwise backward elimination procedure of the least significant terms from a global model based on the predicted relationship and likely interactions. Only levels of explanatory variables with at least 10 observations were included in models to avoid powerless analysis

		Global model		Fox model			Cat model
		B	CI	P	B	CI	P	B	CI	P
	Fixed parts
	(Intercept) KDE 50% KDE 90% KDE 95% MCP 100% MCP 75% MCP 95% Triangulation	0.04 À0.73 À0.31 À0.09 0.16 À0.85 À0.30 0.81	À0.51 to 0.59 À1.00 to À0.46 À0.55 to À0.08 À0.36 to 0.18 À0.04 to 0.36 À1.14 to À0.57 À0.51 to À0.09 0.29 to 1.33	0.881 <0.001 0.010 0.503 0.110 <0.001 0.006 0.003	1.72	1.38 to 2.07	<0.001	À0.02	À0.050 to 0.46	0.938
	Fox	1.01	0.53 to 1.49	<0.001
	Juvenile Intact				À0.19	À0.32 to À0.05	0.010	0.74	0.45 to 1.04	<0.001
	Random parts
	r 2		0.080			0.067			0.094
	s 00, Animal.ID:Study.ID		0.192			0.059			0.304
	s 00, Study.ID		0.535			0.248			0.289
	s 00, method					0.058			0.166
	N Animal.ID:Study.ID		405			183			166
	N Study.ID		41			19			18
	N method					4			5
	ICC Animal.ID:Study.ID		0.238			0.136			0.356
	ICC Study.ID		0.662			0.575			0.339
	ICC method					0.135			0.195
	Observations		678			247			359
	R 2 /Ω 0 2		0.969/0.968			0.902/0.894			0.933/0.931
	Levels of explanatory variables -Method of calculation: Fixed Kernel 95% (FK 95%), Kernel Density 50% (KDE 50%), Kernel Density 90% (KDE

90%), Kernel Density 95% (KDE 95%), Minimum Convex Polygon 100% (MCP 100%), Minimum Convex Polygon 95% (MCP 95%), and Minimum Convex Polygon 75% (MCP 75%). Procedure of data acquisition: automatic localization and triangulation. Predator species: cat and fox. Age: adults and juveniles. Sexual status: intact and desexed. Bold values indicate significant results.

Table 3

 3 Mixed liner model with the sine-transformed B A (diet diversity), square root of % RFO of mammals, birds, and invertebrate as dependent variables, and habitat, predator species, type of samples, and % RFO of invertebrates, mammals, and birds as explanatory variables. Study ID was used as a random variable. Test statistics are given for the final model achieved by a stepwise backward elimination procedure of the least significant terms from a global model based on the predicted relationship and likely interactions. Only levels of explanatory variables with at least 10 observations were included in models to avoid powerless analysis

	RFO bird RFO invertebrate	P B CI P B CI P		<0.001 29.28 22.89 to 35.66 <0.001 5.84 4.84 to 6.84 <0.001	<0.001	0.003 À0.90 À1.74 to À0.05 <0.042 À20.36 À26.28 to À14.43 <0.001 À20.77 À26.83 to À14.71 <0.001 À0.08 À0.17 to 0.01 0.104 À0.05 À0.06 to À0.04 <0.001 9.59 3.71 to 15.46 0.002	À0.05 À0.07 to À0.02 <0.001		44 44	0.497 0.569	89 89	= medium anthropogenic pressure. Type of samples: scats, stomachs, and prey items. Predator
	BA model RFO mammal	B CI P B CI	Fixed parts	(Intercept) 0.40 0.35 to 0.45 <0.001 7.88 7.31 to 8.45	RFO invertebrate À0.08 À0.10 to À0.05 HAP À1.32 À2.17 to À0.47 Scats	Stomachs	RFO mammal	Fox	RFO bird	Random parts	N Study.ID 44 44	ICC Study.ID 0.505 0.713	Observations 89 89	Levels of explanatory variables -Habitat: HAP = high anthropogenic pressure and MAP	species: cat and fox. Bold values indicate significant results.

Acknowledgments

We acknowledge Ecology Population and Community group members for their pertinent comments at the beginning of the study. We are grateful to the editor and two anonymous reviewers who helped to improve our paper. We also thank B. Castagneyrol for helping with the statistical analyses. We are grateful to D. Zarzoso-Lacoste for the useful discussions. This work was supported by a Region Ile-de-France Ph.D. scholarship for IC.

Supporting Information

Additional supporting information may be found online in the Supporting Information section at the end of the article: Table S1. Best models to predict home-range size and diet patterns of red foxes and cats within urban habitats Table S2. Synthesis of analyzed home-range studies with details on publication (first author and year of publication), environmental features (habitat (HAP = high anthropogenic pressure; MAP = medium anthropogenic pressure) and region), predator species and methodologies (mean number of independent fixes, interval of fixes, home-range calculation, collecting data (triangulation/automatic location), collar and animal weight, number, age (A = adult; J = juvenile; A&J = Adult & Juvenile), sex (Male = male; F = Female; M&F = male and female) and sexual status (I = Intact; D = Desexed; I&D = Intact and Desexed) of studied individuals) Table S3. Synthesis of analyzed diet studies with details on publication (first author and year of publication), environmental features (habitat (HAP = high anthropogenic pressure; MAP = medium anthropogenic pressure) and region), predator species, sample types (stomachs, scats or prey items), sample size, number of prey categories, percentage of relative frequency of occurrence for nine main prey categories (mammal, bird, reptile, amphibian, invertebrate, fish, fruit, anthropogenic, unidentified)