Michel Vasquez

Djamal Audrey Dupont

Djamal Habet

CONSISTENCY CHECKING WITHIN LOCAL SEARCH APPLIED TO THE FREQUENCY ASSIGNMENT WITH POLARIZATION PROBLEM

Keywords: Filtering techniques, consistency checking, Tabu Search

published or not. The documents may come

Consistency checking within local search applied to the frequency assignment with polarization problem

Introduction

The ever-increasing demand for communication, coupled with the limited number available spectra, have made frequency assignment more and more difficult to accomplish effectively. Optimization of this process has therefore become a major issue for network administration and deployment, both civil and military. The Frequency Assignment Problem with Polarization (FAPP) can be formalized as a Max-CSP which is known to be NP-hard.

Because the data problem to be optimized was very large, we decided to adopt a local search method. From among all the existing algorithms, we chose Tabu Search, introduced by Glover in [START_REF] Glover | Tabu Search[END_REF]. The specific structure of the FAPP constraint net-work led us to apply local filtering techniques. Consequently, an arc-consistency procedure, AC, was embedded in the Tabu Search framework to reduce the search space. Hence, the consistency checking concept occurred twice (during the resolution): firstly in the filtering pre-processing, and secondly in the kernel of the neighborhood design.

After presenting the physical and formal definitions of the FAPP problem in Section 2, we describe in Section 3 our general approach to solve it. Finally, a large number of experimental results are discussed and compared in Section 4, in order to highlight the advantages obtained by combining a constraint programming tool with the local search heuristic.

Problem definition

Physical description

The FAPP consists in finding an optimal frequency allocation in hertzian telecommunication networks. The network is composed of a set of sites in which the transmission devices (antennae connected to emitters or receptors) are located. A hertzian connection joins two geographic sites by one or more paths. A path is a uni-directional radio-electric bond, established between antennae at distinct sites, which has a given frequency and polarization.

A frequency resource is therefore a (frequency, polarization) pair in which the components are respectively associated to the carrying frequency of the transmitted signal, and the wave polarization. The polarization is simply either positive or negative. Accordingly, we define the path domain as a set of available resources. This set contains the frequency domain F i , and the polarization information P i , which may include a required polarization.

A frequency allocation consists in assigning a (f i , p i ) pair for each path i which satisfies certain radio-electric compatibility constraints (1, 2, and 3), and minimal distance constraints to avoid interference (4):

1. frequencies equality or not across paths i and j:

f i = f j or f i = f j ; 2. distance between frequencies: |f i -f j | = ε ij or |f i -f j | = ε ij ; 3.

polarization equality or not across paths:

p i = p j or p i = p j ; 4. minimal distance between frequencies: |f i -f j | ≥ γ ij if p i = p j δ ij if p i = p j .
In the constraints (4), the required distance between frequencies depends on their polarizations: the distance is obviously smaller if the polarizations are different

(γ ij ≥ δ ij ).
A feasible solution is an allocation for each path that satisfies the full set of constraints. Unfortunately, most problems do not have any such feasible solution, because the domains are too restrictive or the requirements are too numerous. The operator must therefore search for a "good quality" solution in terms of interference, rather than a feasible one. For this purpose, two constraint classes are introduced:

-CI: strong or imperative constraints (1, 2, and 3 above); -CEM: constraints of type 4 where progressive relaxation is authorized and controlled by 11 relaxation levels. Level 0 corresponds to no relaxation. Increasing from level k to k + 1 involves relaxation of some or all the frequency distances defining each constraint, the maximum level being 10:

|f i -f j | ≥ γ 0 ij ≥ γ 1 ij ≥ ... ≥ γ k ij ≥ ... ≥ γ 10 ij if p i = p j δ 0 ij ≥ δ 1 ij ≥ ... ≥ δ k ij ≥ ... ≥ δ 10 ij if p i = p j .
In this context, a feasible solution at level k is an allocation of each path satisfying all the strong constraints CI and all the CEM constraints at level k, noted CEM k . Such a problem is said to be k-feasible. Assuming that a good quality solution minimizes interference, and that the smaller k is the fewer CEM constraints are relaxed, the hierarchical objective function is dependent on k: first minimizing k, secondly minimizing the number of unsatisfied CEM k-1 constraints, and finally minimizing the number of unsatisfied CEM constraints at the levels below k -1.

Formal definition

From this physical description, modelling the FAPP as a Maximal Constraint Satisfaction Problem (Max-CSP), consists in defining the constraint network X , D, C , and the formal criterion to minimize f : -associating a variable x i to each path: X = {p i , i = 1, ..., n}; -associating to x i a domain D i = F i × P i , where F i is the set of the allowed frequencies for the path x i and P i is one of the following sets {-1}, {1}, or {-1, 1}, D = i=1,...,n D i ; -adding several imperative constraints CI between two paths x i and x j :

f i = f j or f i = f j , |f i -f j | = ε ij or |f i -f j | = ε ij , p i =
p j or p i = p j ; -adding CEM constraints where progressive relaxation is authorized:

|f i -f j | ≥ γ 0 ij ≥ ... ≥ γ k ij if p i = p j δ 0 ij ≥ ... ≥ δ k ij if p i = p j
where the index k, increasing from 0 to 10, indicates the relaxation level of the CEM constraints. C = CI ∪ CEM; -let V (k) be the set of unsatisfied CEM k constraints. The hierarchical objective function to be minimized is:

f = k, V (k-1) , i<k-1 V (i)
where k is such that the problem is k-feasible. The formal criterion f is directly related to the hierarchical optimization problem. We must therefore successively minimize k, V (k-1) then Σ i<k-1 V (i) .

Where necessary, for simplicity, we also define:

-C k = CI ∪ CEM k the whole constraint set at level k; -CI(i, j) ⊂ CI the imperative constraints involving the paths i and j; -CEM k (i, j) ⊂ CEM k the relaxed constraints involving the paths i and j.

3. General approach for solving the FAPP Among all of the dedicated algorithms to solve frequency assignment problems [START_REF] Aardal | Algorithms for Frequency Assignment Problems[END_REF][START_REF] Dorne | Étude des méthodes heuristiques pour la coloration, la T-coloration et l'affectation de fréquences[END_REF][START_REF] Jiang | Méthodes Approchées pour le Problème de Coloriage Généralisé Application au Problème d'Allocation de Fréquences Multiservices dans l'Aviation Civile[END_REF], only heuristic based approaches can produce good quality solutions in reasonable computing time for realistically sized instances. The described algorithm here is also a meta-heuristic one. Although it may seem unworkable to attempt to use a pre-processing filtering operation on an optimisation problem, our Tabu Search procedure is reinforced by a consistency technique that reduces the search space and increases the overall efficiency of the neighborhood exploration. Indeed:

-let n be the path number of a FAPP instance; -let S be the non constrained search space: S includes all the configuration vectors s = ((

f 1 , p 1 ), ..., (f n , p n )) such as f i ∈ F i and p i ∈ P i .
The initial size of S, equal to n 1 |F i | × |P i |, is huge, even for the smallest FAPP instances (200 ≤ n ≤ 3000 and 19 ≤ |F i | ≤ 500). To cope with this difficulty, we restrict the F i domains by a filtering process.

The two expected advantages of such a reduction in domain size are: firstly to decrease the time complexity of the neighborhood evaluation, and secondly to avoid exploring wrong areas in the search space. That is why we hybridize our Tabu Search algorithm with an Arc-Consistent (AC) filtering process.

Another important feature of this approach, with the aim of reducing computing complexity, is that only the first component k of the objective function f is considered within the move heuristic. Consequently, the optimization process is transformed into a sequence of decision problems verifying the existence of a kfeasible configuration, where k decreases from 11 to k * (best k found). The search for a lower value of k is started only if a (k + 1)-feasible configuration has been found. Hence, we solve several CSPs rather than one Max-CSP.

To summarize, if AC is the filtering function of the frequency domains, and Tabu the exploring function of the search space using the meta-heuristic Tabu Search, we have the general pattern described in Algorithm 1.

Algorithm 1. AC-Tabu begin k ← 11 while AC(k) = T rue do if Tabu(k) = T rue then k ← k * -1 end
This is a very straightforward iterative procedure. When either AC(k) or Tabu(k) fails then AC-Tabu returns k * = k + 1 as the best k * -feasible solution found. If AC(k -1) fails and Tabu(k) finds a solution, then k is the optimal value. Indeed, AC provides the Lower Bound of k, and Tabu the Upper one.

On the other hand, if Tabu(k) finds a feasible solution, that solution may be k * -feasible, with k * < k. This means that Tabu can jump more than one k-level.

Filtering with AC

Arc-consistency is a widely studied topic in constraint programming [START_REF] Bessière | Arc-consistency and Arc-consistency again[END_REF][START_REF] Bessière | Refining the Basic Consistency Propagation Algorithm[END_REF][START_REF] Mackworth | Consistency in Networks of Relations[END_REF][START_REF] Mohr | Arc and Path Consistency revisited[END_REF]. AC eliminates variable values with no support, since such values cannot lead to a feasible solution.

As FAPP constraints are binary, it is easy to check for every path i (1 ≤ i ≤ n) and for every value couple (f i , p i ), if for each neighbor j of i, there is a couple (f j , p j ) such that CI(i, j) and CEM k (i, j) are satisfied. This elimination process, eliminate(F i , P i , k), is repeated until there is no change in the domain of any variable: in this case eliminate returns F alse, otherwise it returns T rue. For more details about such algorithms, please refer to [START_REF] Bessière | Arc-consistency and Arc-consistency again[END_REF][START_REF] Bessière | Refining the Basic Consistency Propagation Algorithm[END_REF][START_REF] Mackworth | Consistency in Networks of Relations[END_REF]. The main features of the following AC(k) procedure are:

-managing a list of updated variable domains, in order to check, at the next iteration, only the variables for which their domains have changed; -for each f i and p i values, and for each constraint C(i, j), the eliminate (F i , P i , k) function checks another value in the domain D i as soon as it has found a pair f j ∈ D j and p j ∈ P j satisfying C(i, j). Designing a good Tabu Search requires that its main characteristics should be well defined: the effective search space and therefore the definition of the visited configurations, the neighborhood structure, the move heuristic, and the tabu list management. In our approach, the search space is defined over partial configurations expressed by s = (v 1 , v 2 , ..., v ni ), where v i = (f i , p i ) and n i variables are instantiated (with n i = |s|). To conform with the standard representation by n-ary vectors, we add a new value u (for uninstantiated ) to each domain D i , for indicating that x i is free. Accordingly, the evaluation criterion of a configuration is the number of instantiated variables in s.

This improvement enabled us to work on a consistent neighborhood N (s). At each level k, the visited configurations in N (s) respect the CI and the CEM k constraints. In order to build this original neighborhood, a move(s,s'), replacing the current configuration s by s ∈ N (s), is achieved in two steps: an instantiation of a free variable (i.e. set to u), followed by consistent reparations, which are simply deinstantiations of the conflicting variables with respect to the C k constraints. Consequently, the selected move must improve the configuration (i.e. increase |s|). Hence, the evaluation heuristic of moves from s to s ∈ N(s), is simply ∆(s, s ) = |s | -|s|. Note that the ∆ evaluation is carried out very quickly using efficient incremental techniques, which are now well known [START_REF] Fleurent | Genetic and Hybrid Algorithms for Graph Coloring[END_REF][START_REF] Galinier | Étude des métaheuristiques pour la résolution du problème de satisfaction de contraintes et de coloration de graphes[END_REF][START_REF] Vasquez | Résolution en variables 0-1 de problèmes combinatoires de grande taille par la méthode tabou[END_REF][START_REF] Vasquez | A "Logic-Constrained" Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite[END_REF].

The tabu list is needed to prevent cycling, which notably occurs when we attempt to instantiate the last free variables. To avoid undoing the recent instantiation (x i , v i ), we penalize all the conflicting pairs (x j , v j ) where x j are the neighbors of x i in the constraint network, regarding the CI(i, j) and the CEM k (i, j). In this way, we maintain a table counting the number of times a resource v l is assigned to a path x i (f req [i][l]++). So, the tabu tenure is a dynamic function based on the flip frequencies:

tabu[i][l] = f req[i][l] + iter,
where iter is the current iteration number.

The stop-criterion is either if a solution is found, or if computing time has elapsed.

With the specifications, we thus present the general Tabu algorithm in 3.

Diversification

The aim of the diversification phase is to enable Tabu to escape from attractive zones of the search space. For this purpose, we introduce penalties in the move heuristic. More precisely, each time a configuration s such as ∀s ∈ N (s), |s | ≤ |s| is reached, we add a penalty to all the allocated paths having an unallocated neighbor in the constraint graph. This penalty value is then included in the move heuristic during the diversification phase. Hence, the line [START_REF] Aardal | Algorithms for Frequency Assignment Problems[END_REF] in Algorithm 3 is replaced by the following code, where nogood min is the threshold value, and penalty is the effective penalty value of the move.

if (∆(s, s ) > ∆(s, s max )) ∨ (∆(s, s ) = ∆(s, s max ) ∧ penalty < nogood min ) then s max ← s nogood min ← penalty

Numerical experimentation

The algorithms were coded in C programming language. The running tests were carried out on an NT PC station with a Pentium III 600 MHz cpu. The results are presented in four parts. The first describes the reduction of the search space by the filtering step. The second describes the best qualitative results obtained by the hybrid approach AC-Tabu. The next section then compares the results produced by our Tabu and the hybrid AC-Tabu algorithm. This section ends with a comparison between several methods proposed for the ROADEF-2001 challenge. More information about this competition is available on the web site http://www.prism.uvsq.fr/∼vdc/ROADEF/CHALLENGES/2001/

Cutting frequency domains

This first table shows some characteristics of the fapp instances, their size is given in the second part of their name: up to 3000 variables (paths). These Apart from the fapp16 0260 problem, these benchmarks can be divided into two subsets. The first one (from 01 to 15 ) contains the instances where the domain size is reduced by nearly half. In the second one (from 17 to 30 ), domains are reduced more than 90%.

Hybrid approach results

This part begins with the results obtained by the hybrid approach after 1 computing hour. Only one run (with the 0 random seed) was carried out in this experiment.

For each instance, the Table 2 specifies:

-k, the lowest level where a solution is found. This value is underlined when AC-Tabu proves its optimality; -V k-1 , the number of unsatisfied CEM constraints at level k -1; -V k-2 , the sum of the unsatisfied CEM constraints under the k -1 level; -t 1 , the elapsed time in seconds required to reach the best value of k; -and t 2 , the elapsed time required to obtain the best configuration (considering the three components of the objective function).

Table 2. AC-Tabu results after 1 computing hour. Regarding the feasibility level, most of the k are proved optimal (25 of the 30 instances). Obviously, the instances for which no k * is found are those belonging to the first subset described above. Now, we shall see what happens if we give more cpu time to the hybrid algorithm process. Table 3 shows only the improved solutions reached after 3 computing hours. Unfortunately, no improvement has been obtained for the majority of the instances. Nevertheless, we can see again that it only concerns problems belonging to the first subset of fapp instances. Elsewhere, two new optimal values of k are proved (for the 12 1500 and the 13 2000 problems).

fapp k V k-1 V k-2 t1 t2 fapp k V k-1 V k-2 t1

Tabu versus AC-Tabu

This section compares the behaviors of Tabu alone and the hybrid AC-Tabu algorithm. These algorithms were executed 8 times with seed values varying from 0 to 7, and one hour of computing time.

Table 4 focuses on the k-feasibility level and gives the best (k min ) and the worst (k max ) solutions found by the Tabu and hybrid AC-Tabu processes. The gap between k min and k max is higher for Tabu, than for AC-Tabu, notably on the second subset of the benchmark. In conclusion, the behavior of AC-Tabu is more stable than that of Tabu alone.

Note that the results of fapp12 1500, fapp13 2000 and fapp14 2500 do not contradict those from Table 3: it simply means that AC-Tabu finds a better solution in 3 hours with 0 random seed than in 8 × 1 hour with different random seeds.

Comparison with others methods

We will now present the results obtained during the ROADEF-2001 challenge, which took place in FRANCORO III, in the city of Québec (Canada).

The three compared algorithms (apart from ours) were developed by Caseau (MH+PPC), the Bisaillon team (Tabu), and the Michelon junior team (LNS+PPC).

The (MH+PPC) algorithm combines some constraint propagation with metaheuristics. More precisely, the algorithm increases the level, and at each one it shaves by strong consistency, shuffles by a Large Neighborhood Search (LNS) [START_REF] Shaw | Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[END_REF], which gives a non-feasible solution, and finally tries to obtain a feasible solution by a Limited Discrepancy Search (LDS) [START_REF] Harvey | Limited Discrepancy Search[END_REF], such as a Variable Neighborhood local search (VNS) [START_REF] Hansen | Variable Neighborhood Search[END_REF].

The second approach (Tabu) [START_REF] Galinier | Solving the Frequency Assignment Problem with Polarization by Local Search and Tabu[END_REF] is a local search approach based on Tabu Search that includes some original features, including a specialized neighborhood, heuristics to determine critical variables and values, different diversification techniques, an auto-adaptative mechanism to set the tabu list and finally, a pre-processing operation based on consistency techniques inherited from constraint programming. It is used to treat three different problems:

-Constraint Satisfaction Problem to find a solution at level k; -the problem which satisfies all the constraints at level k + 1, and as much as possible at level k; -problem which satisfies all the constraints at level k + 1, and minimizes the objective function.

The Michelon junior team solves the FAPP by using a meta-heuristic based on a Large Neighborhood Search [START_REF] Shaw | Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[END_REF] and Constraint Propagation. Also, they relax certain constraints to obtain a Maximal Cover Tree. Indeed, their algorithm works in three phases: first it computes a lower bound of k, then it searches for a solution at this level k, and finally it improves this solution with respect to the two last points of the objective function. So as to compare several methods, in terms of quality, we have just given the three values of the objective function: k (underlined when the method proves optimality), the unsatisfied constraint number at level k -1, and the sum of the unsatisfied constraints at the levels below k -1.

The AC-Tabu column gives the results obtained by our method during the challenge. Note that they have been improved since the competition. Indeed, we have polished the code, and experiments are made on different computers. More details about the challenge, benchmarks and all the results can be found on the web site http://www.prism.uvsq.fr/∼vdc/ROADEF/CHALLENGES/2001/ The main test condition is a computing time limited to one hour on a Pentium III, 500 Mhz, 128 Mo.

Regarding only the level k, MH+PPC found the optimal k 26 times, Tabu 27 times, LNS+PPC 27 times, and AC-Tabu 28 times. It seems that there is a problem with the LNS+PPC method, because in 4 instances, it could not find a solution (k = 12) and in several others it found no solution better than 11.

Regarding the two other components of the objective function, Tabu without AC gave the best results 27 times, although it could not prove optimality. In fact, the time spent on the PPC techniques in the other methods, was spent to improve the full objective function.

This method comparison reveals that the most difficult instances of the benchmark were 12 1500, 13 2000 and 14 2500.

To conclude, Table 5 highlights the effectiveness of approximate methods combined with some arc-consistent processes on very large instances.

fapp k V k-1 V k-2 k V k-1 V k-2 k V k-1 V k-2 k V k-1 V k-

Conclusion

In this paper we have presented a hybrid approach to solve the Frequency Assignment Problem with Polarization. AC-Tabu combines some arc-consistent techniques and an original Tabu Search process, with a large neighborhood exploration by means of maintaining consistency. It produces very good results on large-sized FAPP instances.

Tabu alone proves its own worth. Indeed, it provides most of the best results but at the same time, some of the worst ones. There are two main reasons that justify the filtering step: the behavior regularity of the hybrid search algorithm, and the proven optimality of the k-feasibility level, for most of the FAPP instances. Some improvements to this approach are still to be expected. Two perspectives for future work can be identified. Firstly, making AC faster by studying the most recent AC algorithms [START_REF] Bessière | Refining the Basic Consistency Propagation Algorithm[END_REF] and adapting to the FAPP constraint semantic. Secondly, considering the two other objective function components V k-1 and i<k-1 V i in the Tabu procedure.

Algorithm 2 . 3 . 2 .

 232 AC(k) begin change ← T rue while change do change ← F alse for i ∈ [1, n] do if eliminate(Fi, Pi, k) then if Fi = ∅ or Pi = ∅ then return F alse change ← T rue end Exploring with TabuContrary to the random local search, where randomness is extensively used, the meta-heuristic Tabu Search is based on the belief that an intelligent search should include more systematic forms of guidance based on adaptive memory and learning.

Table 1 .

 1 Search Space reduction. Columns k 0 indicate the highest unfeasible level encountered by the AC-Tabu procedure, and columns sec. give the computing time in seconds for the whole iterative filtering process. This table shows that no more than two minutes are required by AC-Tabu to reduce the domains of the largest instances of this benchmark.

	fapp	IDS	F DS	∆%	k0	sec.	fapp	IDS	F DS	∆%	k0 sec.
	01 0200	26 963	12 712 52.85	2	0	16 0260	47 293 46 622	1.42 10	0
	02 0250	36 618	14 759 59.69	1	2	17 0300	64 034	918 98.57	3	0
	03 0300	53 536	28 212 47.30	6	1	18 0350	73 016	1089 98.51	7	0
	04 0300	61 762	21 962 64.44	0	4	19 0350	201 074	3414 98.30	5	6
	05 0350	79 311	54 177 31.69	7	2	20 0420	87 077	1886 97.83	9	0
	06 0500 108 024	53 034 50.91	4	6	21 0500	113 594	7745 93.18	3	1
	07 0600 109 658	69 952 36.21	8	2	22 1750	813 037 10 656 98.69	6	25
	08 0700 134 020	81 933 38.87	4	5	23 1800	455 735	3265 99.28	8	9
	09 0800 121 824	52 948 56.54	2	6	24 2000	567 396	8328 98.53	6	4
	10 0900 197 665 122 050 38.25	5	8	25 2230	610 084 18 867 96.91	2	6
	11 1000 294 634 152 727 48.16	7	15	26 2300	635 123 14 217 97.76	6	4
	12 1500 436 967 164 613 62.33	1	70	27 2550	588188 93 768 84.06	4	8
	13 2000 320 494 144 873 54.80	2	21	28 2800 2 087 947 63 597 96.95	2	66
	14 2500 774 322 320 458 58.61	3	92	29 2900 1 477 634	6435 99.56	5	23
	15 3000 515 606 306 127 40.63	4	24	30 3000 1 942 250 80 703 95.84	6	103
	problems contain up to 2 087 947 total domain values, and up to 67 898 binary
	constraints. Table 1 gives the Initial Domain Size (IDS = (F DS = n 1 |D f i |).	n 1 |D 0 i |) and the Filtered one

Table 3 .

 3 Improved results after 3 hours of computing.

	t2

Table 4 .

 4 Best and worst results for the level of feasibility.

		AC-Tabu	Tabu			AC-Tabu	Tabu
	fapp	kmin kmax kmin kmax	fapp	kmin kmax	kmin kmax
	01 0200	4	4	4	4	16 0260	11	11	11	11
	02 0250	2	2	2	3	17 0300	4	4	4	4
	03 0300	7	7	7	7	18 0350	8	8	8	8
	04 0300	1	1	1	11	19 0350	6	6	6	9
	05 0350	11	11	11	11	20 0420	10	10	10	10
	06 0500	5	5	5	6	21 0500	4	4	4	5
	07 0600	9	10	9	10	22 1750	7	7	7	11
	08 0700	5	6	5	6	23 1800	9	9	9	11
	09 0800	3	4	3	8	24 2000	7	7	7	11
	10 0900	6	7	6	11	25 2230	3	3	10	11
	11 1000	8	9	8	11	26 2300	7	7	7	10
	12 1500	4	7	6	8	27 2550	5	5	11	11
	13 2000	5	6	6	6	28 2800	3	3	9	11
	14 2500	6	6	7	11	29 2900	6	6	8	12
	15 3000	5	6	7	11	30 3000	7	7	11	11

Table 5 .

 5 Comparison with three other methods.

	MH+PPC	Tabu	LNS+PPC	AC-Tabu

Centre LGI2P, École des mines d'Alès, site EERIE, 30035 Nîmes Cedex 1, France; e-mail: vasquez,dupont,habet@site-eerie.ema.fr

Acknowledgement. Special thanks to Van-Dat Cung (PRiSM-UVSQ), Thierry Defaix (CELAR-DGA) and Maurice Diamantini (ENSTA) for allowing us to use their FAPP definition. Thanks also to Gérard Verfaillie for fruitful discussion about some arc-consistent techniques.


Audrey Dupont
email: dupont@site-eerie.ema.fr

Eric Alvernhe
email: alvernhe@site-eerie.ema.fr

Michel Vasquez
email: vasquez@site-eerie.ema.fr

Efficient Filtering and Tabu Search on

Keywords: frequency assignment problem, arc-consistency, path-inverse-consistency, Tabu Search, Consistent Neighbourhood

published or not. The documents may come

Introduction

The Frequency Assignment Problem with Polarisation (FAPP) in Hertzian telecommunication networks consists in assigning frequency resources so as to minimise electromagnetic interference due to the proximity of antennae and interactions within the same Hertzian liaison between emitter and receptor frequencies.

To solve the FAPP, a Tabu Search method working on consistent partial configurations (CN -Tabu) was implemented. The originality of the approach is that it deals with a consistent neighbourhood defined on these particular configurations.

In order to control the global quality of the Hertzian network, in terms of interference, relaxation levels were introduced on some electromagnetic constraints. Taking into account this specificity, we improved our resolution method by an original filtering process, which combined Arc-Consistency (AC) on all the constraints and Path-Inverse-Consistency (PIC) on the relaxable constraint cliques.

The solution search, strongly linked to the relaxation level allows to encapsulate the CN -Tabu following two general approaches: the first one starts from the highest level where maximal relaxation is authorized. The second one begins from the last consistent level calculated by the filtering algorithms. Analysis of these approaches emphasises the stability and speed of the Tabu Search on a Consistent Neighbourhood. This article begins with the modelling of the problem in section 1. Section 2 describes the filtering algorithms, and gives the results obtained. The next part presents the FAPP resolution by detailing the tabu search on a consistent neighbourhood for solving a constraint network, then followed in section 4 by both implementations: Downward and Upward, and a behavioural study by comparison of their results. Finally, section 5 summarises the results obtained by other methods developed to solve the FAPP.

Problem presentation

Physical description

The FAPP concerns a Hertzian telecommunication network made up of transmission equipment (antennae connected to emitters or receptors) located at a set of geographical sites. A Hertzian liaison joins two sites by one or more paths. Hence, a path is a unidirectional radio-electric bond, established between antennae at distinct sites, which has a given frequency and polarisation. A frequency resource for a path is a pair (frequency, polarisation), whose components are respectively associated to the carrying frequency of the transmitted signal and the wave polarisation. In the simplified model, the polarisation is a binary variable (i.e., only vertical or horizontal). For each path x i , a set of available resources {(f i ,p i ), f i ∈ F i and p i ∈ P i }, where F i is the ordered frequency domain representing the authorised wave band, and P i is the polarisation information, which may include a required polarisation.

So, the frequency assignment problem consists in finding, for each path, a frequency resource satisfying the radio-electric compatibility constraints. Moreover, given that many emitters and receptors are located on the same site, other coupling binary constraints linking paths located on the same site, or linking two paths belonging to the same Hertzian liaison must be also verified. Thus, the constraint set is composed by: 1. equality or inequality of frequencies across two paths: f i = f j or f i = f j ; 2. distance between frequencies of two paths:

|f i -f j | = ε ij or |f i -f j | = ε ij ;
3. equality or inequality of polarisation across two paths: p i = p j or p i = p j (not all the paths are linked by this constraint type);

4. minimal distance between frequencies of two paths:

|f i -f j | γ ij if p i = p j , δ ij if p i = p j .
The last constraint type controls the interference phenomenon, which is why the required distance between frequencies depends on their polarisations: it is smaller if the polarisations are different (i.e., δ ij γ ij ).

One feasible solution is thus to assign all the paths that completely satisfy this constraint set. Unfortunately, most problems do not have feasible solutions, because the domains are too restrictive or the requirements too numerous. Consequently, the operator must look for a "good quality" solution. This means that some deterioration is allowed, by permitting some interference. Thus, the intention is now to minimise this interference. With this aim, two constraint classes are introduced:

• IC: strong or Imperative Constraints (type 1-3 above);

• ECC: Electromagnetic Compatibility Constraints (type 4), where a progressive relaxation is authorised and expressed by relaxation levels: level 0 corresponds to no relaxation, and going from level k to level k + 1 involves the relaxation of some or all the frequency gaps, the maximum relaxation level being 10:

|f i -f j | γ 0 ij • • • γ k ij • • • γ 10 ij if p i = p j , δ 0 ij • • • δ k ij • • • δ 10 ij if p i = p j ,
since in the 11th level, γ 11 ij = δ 11 ij = 0, so there is no ECC. So, we note ECC k the set of ECC constraints at level k; this means that each constraint belonging to ECC k is affected to its γ k ij and δ k ij gaps. Accordingly, a feasible solution at level k is an assignment of all the paths satisfying all the strong constraints IC and all the ECC k constraints. If such a solution exists, the problem is said to be k-feasible. Consequently, the objective function of the problem becomes, in order of priority:

1. search the lowest relaxation level k for which a k-feasible solution exists; 2. then, minimise V (k-1) : the number of constraints of ECC (k-1) unsatisfied at level k -1;

3. finally, minimise 0 i<k-1 V (i) : the sum of the constraints of ECC i unsatisfied at all levels i less than k -1.

Considering the first objective of the evaluation function, the optimal solution s * will be necessarily at the lowest k-feasible level (k * ).

Modelling as a constraint network

Setting the paths as variables, frequencies and polarisations as their domain values, and IC and ECC as the constraint set, the FAPP can be formalised as a Maximal Constraint Satisfaction Problem (Max-CSP), on the following constraint network:

• let X = {x 1 , . . . , x n } be the set of the n paths;

• let F i be the frequency domain of x i , and P i the polarisation domain, where P i ∈ {{-1}, {1}, {-1, 1}}, each resource to be affected to each variable x i is a pair (f i , p i ) where f i ∈ F i and p i ∈ P i ; • let IC be the set of the imperative constraints:

IC = {p i = p j , p i = p j , |f i -f j | = ε ij , |f i -f j | = ε ij }, ε ij
can be null; in this way, all the frequency constraints are merged in two constraint types: Equality of the Distance between two Frequencies (EDF) (f i = f j and |f if j | = ε ij ) and Difference of the Distance between two Frequencies (DDF) (f i = f j and |f i -

f j | = ε ij ).
• let ECC k for 0 k 10 be the set of the relaxed constraints:

|f i -f j | |p i + p j | 2 γ (k) ij + |p i -p j | 2 δ (k) ij ;
Every problem is 11-feasible.

The strategy adopted for the resolution consists in transforming the Max-CSP (an optimisation problem) into 11 CSP (decision problems) according to the relaxation level on the electromagnetic compatibility constraints: each CSP(k) contains both the IC and the ECC k constraints.

This enables us to introduce some filtering treatments on each CSP(k), in order to obtain the k consistent level closest to level k * . The second advantage of this filtering process is to reduce the domain size, by deleting the inconsistent values.

Filtering algorithms for the FAPP

Basic definitions

After recalling some concepts of consistency, we briefly present two filtering algorithms: Arc-Consistency (AC) then Path-Inverse-Consistency (PIC).

Let CN = X , D, C be a binary constraint network, and

C(ij ) a constraint in C linking x i and x j . A value f i ∈ D i is consistent with C(ij ) if and only if ∃f j ∈ D j such that (f i , f j ) ∈ C(ij ), f j is then called a support for (x i , f i ) on C(ij ). A value f i is called viable if it has at least one support on each C(ij ).
A domain D i is called consistent domain, if all of its values have at least one support on each constraint.

Introduced by [START_REF] Waltz | Understanding Line Drawing of Scenes with Shadows[END_REF], Arc-Consistent filtering (AC) on a constraint network is achieved by removing all non-viable values. Some variant AC algorithms have been elaborated, for example AC3 [START_REF] Mackworth | Consistency in Networks of Relations[END_REF] and AC-inference [START_REF] Bessière | Using Inference to Reduce Arc Consistency Computation[END_REF].

To refine the filtering operation, Freuder proposes in [START_REF] Freuder | Neighborhood Inverse Consistency Preprocessing[END_REF] the k-inverse consistency, in which each variable value that cannot be extended to a consistent instantiation including k -1 additional variables is removed. We shall use the Path Inverse Consistency (PIC), which is the 3-inverse consistency. More formally, a constraint network is PIC-consistent, if and only if ∀x i , x j , x k ∈ X such that

x j = x i = x k = x j , ∀v i ∈ D i : ∃v j ∈ D j and v k ∈ D k such that {(x i , v i ), (x j , v j ), (x k , v k )} is locally consistent.
For more details concerning filtering algorithms, the interested reader can refer to [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF].

General methodology

It may seem unworkable to attempt to use a pre-processing filtering on an optimisation problem. However, as stated in section 1.2, the resolution strategy adopted for the FAPP transforms the initial optimisation problem into 11 decision problems. Hence, each CSP resolution is preceded by a filtering process.

Starting from level 11 down to the consistent level, the filtering algorithm finds, for each domain value, the minimal level at which the value has, at least one support on each constraint. So, it stops when it empties one variable domain, and returns the level above, which is the last consistent level where a solution can possibly be found. This algorithm is directly inspired by the AC3 and PIC algorithms.

The next three sections present this filtering process. To be precise, for each constraint type C(ij ), they detail the computing of the consistent domain of a variable x i involved in this constraint type, then the propagation mechanisms (i.e., how to maintain the consistency of the domain D j linked by C(ij ) to D i where a value was deleted by an other constraint).

Arc-consistency on binary constraints

Arc-consistency is carried out on each constraint type. So, we begin with the equality and difference constraints of distance between two frequencies, which are easy to process, then continue with the specific processing of the electromagnetic compatibility constraint type.

Distance constraints: equality and difference

The equality of the distance between frequencies. EDF are expressed by |f if j | = ε ij , where ε ij ∈ N can be null (i.e., f i = f j ). For checking the D i consistency, it is enough to check for each f i ∈ D i if f iε ij or f i + ε ij are in D j . For all the equality constraints between x i and a neighbouring variable x j with a gap ε ij , the deletion of f i from D i is propagated on D j by deleting

f i + ε ij (respectively f i -ε ij ) if f i + 2 × ε ij (respectively f i -2 × ε ij ) is not in D i .
Difference of the distance between frequencies. DDF are expressed by |f if j | = ε ij , where ε ij ∈ N can be null (i.e., f i = f j ). Checking the consistency on a difference constraint is easier. Indeed, for each f i ∈ D i , all the D j values different from f i -ε ij and from f i + ε ij are supports for f i on C(ij ). Hence, if the domains D j contains more than two values, then it is sure of finding a f i support. If D j has only one value f 1 , we delete the two values

f i = f 1 -ε ij and f i = f 1 + ε ij if they belong to D i . If D j has two values (f 1 and f 2 ), we propagate on D i if and only if ∃f i ∈ D i such as f i = f 1 + ε ij = f 2 -ε ij .
Consistency domain of D j is compute in the same way. Concerning the propagation on this constraint type C(ij ), considering that a value f i was deleted from D i by a C(ik) constraint, any propagation is needed on D j if and only if the filtered D i has more than two values. Otherwise, we use the same consistency check as to compute the consistent domains.

The electromagnetic compatibility constraints (ECC)

The mathematical formula of this constraint type is |f if j | ε ij , where ε ij = γ ij if polarisations p i and p j are equal, and δ ij otherwise.

In the following section, a different reasoning method is adopted to compute the domain consistency. Rather than searching for a support f j on C(ij ) for each domain value f i , we search the value set supported by D j . Indeed, instantiating x i and x j consists in respecting one of the two inequalities, f i < f j or f i f j . In the first inequality, assigning max(D j ) to x j leads to the potential consistent domain for

x i , [-∞, max(D j ) -ε ij ].
In the second one, assigning min(D j ) leads to the second potential consistent domain, [min(D j ) + ε ij , +∞]. Considering the two inequalities, the full potential consistent domain becomes

Cons(i) = [-∞, max(D j ) -ε i,j ]∪[min(D j ) + ε i,j , +∞].
However, this interval union is not necessarily a subset of D i , so the consistent domain is effectively D i ∩ Cons(i). Since the domains are ordered, this algorithm has the same complexity as a two set intersection computation, so it is linear. Concerning the propagation mechanism, no updating is needed even if a value is deleted from the domain D i while min(D i ) and max(D i ) have not changed.

Path inverse consistency on 3-cliques with 3 ECCs

Path inverse consistency is implemented for the electromagnetic compatibility constraint cliques. As an AC refinement, PIC increases the deleted value number, by working simultaneously on three constraints. This idea was inspired by [START_REF] Hertz | A Tabu Search for the Frequency Assignment Problem with Polarization[END_REF], but is implemented using our method of consistency computing and propagation on the ECCs.

In fact, stating that arc-consistency is 2-inverse-consistency allows the reasoning to be extended to ECC cliques. At this stage, arc-consistency is carried out on three variables (x 1 , x 2 and x 3 ) linked by three ECCs. So, there are 6 possible inequalities (f 1 < f 2 < f 3 , f 1 < f 3 < f 2 , . . . ). Considering any one of them, all the constraints lose their absolute term. In order to compute the arc consistent domain of one variable, we determine the potential consistent interval for each inequality. Let l (where l ∈ [1, 3]) be the variable position in the current order, its potential consistent domain is computed as follows:

• each of the l -1 first variables is assigned to the minimal consistent value according to the constraints linking it to the previous variables in the order; • each of the 3l last variables is assigned to the maximal consistent value according to the constraints linking it to the next variables in the inverse order; • now, we define [a, b] as the potential consistent domain for the lth variable on the current order; a (respectively b) is the minimal (respectively maximal) consistent value for all the constraints linking the (l -1)th first (respectively (3l)th last) variables; a or b could be -∞, or +∞, or not defined, or any other value (not necessarily in the domain of the lth variable domain); • if l = 2, we check the crossing constraint (linking the first and the third variables) before computing a and b.

If one of these points is not defined, the potential consistent interval in the considered order is empty. The consistent variable domain is therefore the intersection between its domain and the union of the six intervals obtained by the different orders. As the domains are sorted, local consistency checking is linear.

Path-inverse-consistency on 3-cliques with 2 ECCs and one EDF

A 3-inverse-consistency on two ECCs and one EDF is implemented if the distance value of the equality constraint ε 13 is smaller than the two ECCs values sum: ε 13 < ε 12 + ε 23 , where C( 13) is the EDF, C( 12) and C( 23) are the ECCs. Under this condition, the orders

f 1 < f 2 < f 3 and f 3 < f 2 < f 1 entail the violation of at least one constraint.
Hence, finding the consistent domain of x 2 consists in looking for all f 2 the pairs (f 1 , f 3 ), where f 1 ∈ D 1 and f 3 ∈ D 3 must be simultaneously higher, or simultaneously lower than f 2 . If they exist, four value pairs (f 1 , f 3 ) are well designed to be supports:

(f 1 , f 3 = f 1 -ε 13 ) and (f 1 , f 3 = f 1 + ε 13 ), set in the left of the domains, then (f 1 = f 3 -ε 13 , f 3 ) and (f 1 = f 3 -ε 13 , f 3 ) set in the right. A value f 2 is consistent if it is
supported by one of these pairs. So, calculating the x 2 consistent domain is linear.

Computing a x 1 consistent domain consists in checking for each value f 1 whether f 1 + ε 13 or f 1ε 13 belongs to D 3 . Therefore, we deduce the f 1 3-inverse-consistency by verifying if one of these pairs can be extended with one of the x 2 consistent values. Finally, calculating the x 3 consistent domain is similar to x 1 .

Filtering results

Experiments were carried out on the FAPP benchmark proposed for the ROADEF'01 challenge. This consists of 40 instances, having 200 to 3000 variables, 163 to 15664 imperative constraints and 945 to 30625 electromagnetic compatibility constraints. The cardinality of the whole domain size is 2 million. Tests were performed on a 1.9 GHz Pentium IV processor.

After giving the instance characteristics: instance name which includes the variable number in column 1, the imperative constraint number (column 2), the ECC number (column 3) and the total size of all the domains (column 4), table 1 shows a comparison between a generic AC3 algorithm (column 5) and our specific AC3 (column 6). Generic AC3 checks all the value pairs, while specific AC3 is adapted to constraint characteristics. Because these two algorithms implement the same filtering, this two versions obviously give the same consistent level k const in column 7, and the same percentage of filtered values according to the initial domain size in the ratio column. So, we compare their computation time in seconds in columns 5 and 6.

The AC3 time analysis shows that the specific version is much faster than the generic one, up to 100 times faster in some instances, for example, 12-1500, 14-2500 and 39-2750.

The last part of table 1, presents the results obtained by our PIC only on the particular 3-cliques, as mentioned in sections 2.4 and 2.5, which is why we refer to PIC -in the results table. The k consistent level is given in column 9, then the ratio of filtered values at this level according to the initial domain size is presented in column 10 and finally the computing time in the last column, expressed in seconds. Hence, we can compare PIC - with the specific AC3 in terms of filtering quality by first regarding the consistent level then the filtered domain size.

The qualitative improvement made by adding PIC -to the specific AC3 consists, firstly, in a refinement of the consistent level for two instances: 01-0200 (from 3 to 4) and 31-0400 (from 3 to 5). In the latter instance, this avoids the resolution method having to search CSP(3) and CSP(4). Secondly, it deletes more values for other instances in a time that remains reasonable, below 31 seconds.

Resolution with CN -Tabu

CN -Tabu (for Tabu Search on a Consistent N eighbourhood) is an interesting hybrid method which includes some of the arc-consistent mechanisms in its Tabu Search (as defined in [START_REF] Glover | Tabu Search[END_REF]). This method has been applied to some industrial problems adjacent to the FAPP [START_REF] Vasquez | Arc-Consistency and Tabu Search for the Frequency Assignment Problem with Polarization[END_REF]: the Daily Photographs Satellite Problem (DPSP) (Vasquez and Hao, 2001b) and the Antenna Positioning Problem (APP) (Vasquez and Hao, 2001a), which is the upstream problem of the FAPP. For better understanding, we will first present the general methodology of a Tabu Search, then the principle of our hybrid method. The last part explains how our Tabu Search is used through the levels corresponding to each CSP, in both directions, downward and upward.

Tabu search methodology

A Tabu Search, TS, is a meta-heuristic designed for tackling hard combinatorial optimisation problems. By contrast with random approaches, TS is based on the belief that an intelligent search should include more systematic forms of guidance based on adaptive memory and learning. TS can be described as a form of a neighbourhood search with a set of critical and complementary components.

For a given optimisation instance (S, f ) characterised by a search space S and an objective function f , a neighbourhood N is introduced. It associates for each s in S, a non-empty subset N (s) of S. A typical TS algorithm begins with an initial configuration s in S, then repeatedly visits a series of the best local configurations following the neighbourhood function. At each iteration, one of the best neighbours s ∈ S is selected to become the current configuration, even if s does not improve the current one in terms of cost function. To avoid the problem of cycles occurring and allow the search to go beyond local optima, tabu list is introduced. This adds a short time memory component to the method. A tabu list maintains a selective history H (short time memory), composed of previously encountered configurations or, more generally, pertinent attributes of such configurations. A simple TS strategy consists in preventing configurations of H from being considered on the k next iterations, called the tabu tenure. A tabu tenure can vary for different attributes, and is generally problem dependent. At each iteration, TS looks for the best neighbour from this dynamically modified neighbourhood N (H, s), instead of N (s) itself. Such a strategy prevents the search from being trapped in short term cycling and makes the search more rigorous. When attributes of configurations, instead of configurations themselves, are recorded in a tabu list, some unvisited, yet interesting configurations may be prevented from being considered. Aspiration criteria may be used to overcome this problem. A widely used aspiration criterion consists in removing a tabu status from a move when it leads to a configuration better than the best one obtained so far. Since TS uses an aggressive search strategy to exploit its neighbourhood, it is crucial to have special data structures and techniques which allow rapid updating of move evaluations, and reduce the effort of finding best moves. A Tabu Search can therefore be described by specifying its main elements: the configuration representation, the cost function to evaluate the configurations, the neighbourhood function, the tabu list and its tabu tenure, and finally the aspiration criterion.

The CN -Tabu method

For better understanding of the method description, we must differentiate between two uses of the term neighbouring. The first one concerns the neighbouring variables in the constraint network, which are the variables linked by a constraint to the given variable; whereas a neighbouring configuration in an approximate method is used to denote a new configuration obtained from the current one by a move which changes one or more variable affectations. Now, we will see the specificities of our Tabu Search. The first and most important point to emphasize is that CN -Tabu works on consistent partial configurations, rather than on inconsistent complete configurations, like all the other local search methods. Hence, the cost function used is merely the affected variable number in the configuration: one configuration is better than another if it has more instantiated variables.

In order to visit the combinatorial space search, CN -Tabu jumps from a configuration to a neighbouring one by making moves. A move consists in affecting a not yet instantiated variable, then repairing the possible conflicting affectations. More precisely, each move is made in two steps: first, we assign a pair (f i , p i ) to the chosen candidate path x i , then we propagate this affectation to its neighbours x j in the constraint network and, if necessary, we de-instantiate the conflicting neighbouring values, using local considerations respecting IC(ij ) ∪ ECC k (ij ). This can be done efficiently using the incremental computing principle as in [START_REF] Fleurent | Genetic and Hybrid Algorithms for Graph Coloring[END_REF], on specific data structures, allowing variable domains to be dynamically reduced. More precisely, after each move, we update the domains of x j , neighbours of the variable x i which has already been instantiated, by considering their inconsistency degrees regarding the current partial configuration. Hence, this mechanism can be viewed as a dynamic filtering operation. As the complexity of the updating step is directly linked to the graph constraint degree, the mechanism seems to be appropriately sized only for weak arity networks. Moreover, a tabu list is needed to prevent cycling, which notably occurs when we attempt to instantiate the last uninstantiated variables in the current partial configuration. Indeed, all the domain values (f j , p j ) likely to de-instantiate the variable x i affected by the move are classified tabu during some iterations: the tabu tenure is proportional to the number of times this resource has been affected. However, the aspiration criterion enables selection of a tabu neighbour if and only if it improves the cost function, i.e., it has more affected variables than the current one. Finally, the last two important elements in a Tabu Search are the intensification and the diversification phases. Given that our study focuses on minimising the relaxation level, we need to solve the different CSP(k) as quickly as possible. The intensification phase is therefore not needed. The diversification phase makes it possible to escape from attractive zones of the search space. For this purpose, we introduce penalties during the search phase. More precisely, each time a partial configuration s cannot be extended (i.e., the configuration s has more instantiated variables than all its neighbours), we add a penalty to all pairs (x i , (f i , p i )) of the affected variables which have an unassigned neighbour in the constraint network. These assigned variables belong to a nogood, emphasized by adding penalties. This penalty value is then included in the move heuristic during the diversification phase. Indeed, the diversification phase is a tabu search in which candidate selection depends on the "nogood" values.

Downward and upward methods

The presented filtering algorithm provides the last consistent level. However, this level may be lower than the feasible one, i.e., the minimal level from which a solution exists. If they are the same (i.e., the search method found a solution at the last consistent level returned by the filtering), we are sure that this level is the optimal one, considering the first point of the objective function (i.e., minimize the feasible level).

This allows to envisage two ways to tackle the FAPP: the first one starts from the maximal level, then decreases the level when it has found a solution. The second one, in opposite, starts from the last consistent level, and try to find a solution. If not, it increases the level since it found a feasible level.

In the next, we will present the two approaches, downward and upward, by using the CN -Tabu algorithm to solve each CSP(k), before giving some comparison results.

Downward approach

Downward is the most intuitive approach, knowing that a local search can say if it has found a solution but never say if no solution exists. Starting from level k = 11 where any ECCs was considered, by a consistent partial configuration provided by a Greedy search, downward attempts to decrease the feasible level to the consistent one. So, the main loop alternates search and diversification phases, in order to solve each CSP(k) until the last consistent level and decreases k if a solution is found.

Algorithm 1 describes the downward method, where S is the search space, and f the objective function. For more clarity, we detail the notations and functions involved:

• s * represents the optimal configuration; • s -represents the partial configuration from level k -1, obtained from the solution at level k by de-instantiating the conflicting variables; • n is the total number of variables;

• k is the relaxation level, where the algorithm solves the CSP(k);

• get-filtering-domains(k): computes, for each variable domain, the consistent values at level k. Indeed, the domains are thus dynamic; • change-parameters(): updates the execution parameters of CN -Tabu (seed, maximal iteration number, etc.); • stop-criterion: means that a solution is found at the consistent level (k-const), or once the authorised time has elapsed.

Upward approach

By contrast with downward, upward starts from the consistent level and climbs through the levels. It attempts to solve the different CSP(k) between the consistent and the feasible levels. More precisely, while no solution is found at the current level, k is increased and the new CSP(k) resolution starts from the best partial configuration produced by the previous step. Once a solution is reached, the feasible level becomes k. The aim is thus to reduce the feasible level to the consistent one. Algorithm 2 describes the upward method as an "intelligent" algorithm, which reuses information and configurations from the previous resolution. However, this approach is more risked. Indeed, downward approach guarantees to go down from a level only if a solution was found at the current level, whereas it may be possible that upward searches at several levels without never finding a solution. Algorithm 2 describes upward method. The notations are the same as downward algorithm, on which we add:

• k-const: the relaxation level returned by the filtering process, it means that no solution can be found at (k-const -1) level, at less one variable domain has been empty by constraint propagations. • k-real: the level at which CN -Tabu has found a solution. So, the aim is to reduce the k-real level to the k-const one.

Result comparisons

Tables 2 present the results obtained by 100 runs of one hour on each instance, with the initial seed varying from 0 to 99. They compare the downward (columns 3 to 4) and upward (columns 5 and 6) approaches. Column 1 is the instance name and column 2 the obtained level, it is underlined if it is the optimal level. For each method (downward, and upward), we give the success rate in the T % column, as well as the average time in seconds required to reach the optimal level, in the time column. By comparing the number of times each method found the optimal level, we see that upward was 100% reliable on 27 instances, whereas downward only worked on 20 instances. Even if we consider that a method can be said to be reliable if it has a ratio 75%, downward is reliable on 31 instances, as compared with 35 for upward. These results show that the upward approach is more stable than the downward one (i.e., it is less dependent on the tuning parameters, especially the random seed).

Furthermore, the upward approach consumes less time than downward. Indeed, upward is faster than downward on 29 instances, whereas downward is faster on only 4 instances. For most of the benchmark instances, the times are approximately comparable. However, some need to be focused, notably instance 22-1750, where upward is a hundred times faster than downward, or instance 32-0550, where upward is more than 500 times faster. Hence, much more time is required in order to improve the other two components of the objective function (i.e., minimise the violated constraint number at level k -1, and the sum at level less than k -1).

The risks taken by upward in its resolution, changing the relaxation level without having necessarily found a solution on the current level, allows this method to produce better results, in terms of quality (or stability) as well as in execution speed, than the downward one.

Another aspect to point out concerns the hard instances 12-1500, 13-2000 and 14-2500. The upward approach found the optimal level 36 times for 12-1500, and 3 times for 13-2000 as compared with 0 times by the downward method. For instance 14-2500, upward found the optimal level twice, as opposed to once by the downward approach. These instances are said to be hard because they have many variables, many constraints, and the filtering ratio is less than 66%. However, there are two things wrong, concerning the instances:

• 31-0400: the downward approach obtains better results than the upward approach.

This instance has only 400 variables and all (except 6 for upward) the founded solutions are at the level 5 or at level the 11. • 39-2750: no method found a level better than 11, whereas the known optimum is 3; except for two occasions where upward found solutions at level 8.

Table 3 details the results obtained on the hard instances, in order to better understand the real difficulties met by a local search on these instances. The first two columns give the instance name and the name of the resolution approach, the next ten show the relaxation level. The optimal k is underlined if it has been found, otherwise an * is inserted.

Once again, we note the effectiveness of the upward approach, notably on instance 14-2500, where the k found is mainly between 5 and 6, while it can reach 11 by downward.

Related work

The Frequency Assignment Problem Framework has been widely studied, notably in the context of the European Project EUCLID CALMA (Combinatorial Algorithms for Military Applications). In 1995, the CELAR (Centre d'ELectronique de l'ARmement, France) proposed a set of benchmarks for the frequency affectation problem called the RLFAP (Radio Link Frequency Assignment Problem) coming from real networks with simplified data. From the wide range of literature in the field [START_REF] Koster | Frequency Assignment -Models and Algorithms[END_REF][START_REF] Aardal | Algorithms for Radio Link Frequency Assignment: The CALMA Project[END_REF][START_REF] Hao | Tabu Search for Frequency Assignment in Mobile Radio Networks[END_REF][START_REF] Castellino | A Tabu Search Algorithm for Frequency Assignment[END_REF][START_REF] Voudouris | Solving the Radio Link Frequency Assignment Problem Using Guided Local Search[END_REF], we would like to cite [START_REF] Aardal | Models and Solution Techniques for the Frequency Assignment Problem[END_REF], which provides a very clear survey of the different frequency assignment problems and their resolution methods.

The model studied in this paper can be viewed as a follow-up to that of the CALMA project. Indeed, the problem is extended to take into consideration the polarisation and the relaxation level on the electromagnetic compatibility constraints. It was the subject of the ROADEF'01 challenge, which took place at FRANCORO III, in the city of Québec (Canada) in May 2001. It has opposed six finalist methods. We present in table 4 the results they obtained. During the competition, only one run was allowed and the computing time was limited to one hour on a Pentium III, 500 MHz, 128 MB. Table 4 details the hierarchical objective function, by giving first the relaxation level k, then the sum of all the unsatisfied ECC k-1 , and finally the sum of all the unsatisfied ECC i , where i varies from 0 to k -2.

The first approach, developed by Bisaillon's team [START_REF] Galinier | Solving the Frequency Assignment Problem with Polarization by Local Search and Tabu[END_REF] and referred to as TS-VN, is a local search based on Tabu Search on a variable neighbourhood. This method successively treats three different problems:

• finding a solution at the level k (k-feasible);

• finding a k+1-feasible solution which as far as possible satisfies constraints at level k;

• finding a k + 1-feasible solution and minimising the objective function.

The algorithm MH + CP, developed by Caseau, combines constraint propagation with meta-heuristics, increasing the level. More precisely, at each level, it "shaves" with strong consistency. If the constraint network is consistent, a Large Neighbourhood Search [START_REF] Shaw | Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[END_REF]) returns a configuration. If it is a nonfeasible solution, then a Limited Discrepancy Search [START_REF] Harvey | Limited Discrepancy Search[END_REF] tries to obtain a feasible one. If not, it increases the level. The third method, LS-CC, developed by Gavranovic is a typical Local Search guided by the constraint cost. At each level, it builds frequency trees, ignoring the polarisation constraints. Then it tries to optimise the polarisation allocation.

In a similar way, the classical Tabu Search (referred to as Tabu in table 4), implemented by Schindl's team decreases the level, and at each level optimises a frequency allocation without any polarisation, then assigns polarisation values.

Michelon junior team solves the FAPP by using a meta-heuristic based on a Large Neighbourhood Search and on constraint propagation (LNS + CP). They relax some constraints to obtain a maximal cover tree. Indeed, their algorithm works in three phases: first it computes a lower bound of k, then it searches for a k-feasible solution, and finally it improves this solution with respect to the last two points of the objective function.

Finally, the last column gives the results obtained by the CN -Tabu developed for the challenge. It follows the downward approach, using a standard AC procedure.

Briefly to analyse table 4, we only focus on the optimal level k * . The first method (TS-VN) reaches this level in 32 instances, the second (MH + CP) in 35 instances, and the third (LS-CC) in 28 instances. Both LNS + CP and Tabu reach k * only in 19 instances. By achieving optimality 36 times, CN -Tabu obtains the best results in the competition. Moreover, the improvements presented in this paper are significant. Indeed, downward finds k * for 37 instances and upward fails only in one instance (see table 2). However, great care is needed, because the running conditions are not the same: although the resolution time was fixed to one hour, CPU speeds are different, and we consider the best results out of 100 runs.

More details on this challenge, the benchmarks, and all the results can be found on the web site: http://www.prism.uvsq.fr/~vdc/ROADEF/CHALLENGES/ 2001/challenge2001_en.html

Conclusion and perspectives

In this paper, we have presented an original approach to the resolution of the FAPP. It combines a specific filtering algorithm with the hybrid CN -Tabu search.

The filtering algorithm, based on the FAPP constraint specificities and improved by considering the path inverse consistency on 3-cliques, refines the consistent level search. From a theoretical point of view, the PIC algorithm for the 3-cliques on ECCs, could be generalised to the k-inverse consistency. The k-inverse consistent domain of D i becomes the intersection between D i and the k! intervals defined by the k! orders. The complexity remains linear within the domain size.

CN -Tabu hybridises a Tabu Search with arc-consistent mechanisms, by considering the consistent neighbourhood. Efficient at solving CSPs, it is the kernel of the two hierarchical resolution strategies downward and upward. Emphasised by the experimental results, the speed and stability of upward confirm the effectiveness of working on partial but consistent configurations. Moreover, they enable the other two components of the objective function to be tackled. To achieve this, we envisage to define equality constraints of distances between frequencies as meta-variables because of their hardness. One last point that should be highlighted concerns instance 39-2750, for which a more precise analysis is needed to understand its constraint network particularity, in order to improve the CN -Tabu.

Table 2

 2 Upward versus downward.

	Instance k	Downward		Upward	Instance k	Downward	Upward
			T %	time	T %	time		T %	time	T %	time
	01-0200	4 100	0.75	100	0.44	21-0500 4 100	0.01	100	<0.001
	02-0250	2 100	3.55	100	4.12	22-1750 7 100	92.03	100	0.92
	03-0300	7 100	13.68	100	16.05	23-1800 9	77	7.87	100	1.75
	04-0300	1	98	25.48	100	10.49	24-2000 7 100	6.52	100	0.05
	05-0350 11 100	<0.001 100	0.88	25-2230 3 100	6.77	100	0.39
	06-0500	5	97	204.44	99	35.05	26-2300 7 100	8.56	100	1.01
	07-0600	9	83	3.91	100	3.21	27-2550 5 100	23.92	100	2.55
	08-0700	5	98	39.33	99	7.1	28-2800 3 100	33.64	100	1.2
	09-0800	3 100	14.78	100	7.48	29-2900 6 100	17.31	100	2.03
	10-0900	6 100	869.42	98	7.64	30-3000 7 100	319.55	100	5.99
	11-1000	8	95	441.31	98	22.66	31-0400 5	65	791.86	18	809.33
	12-1500	2	0	-	36 1371.53	32-0550 6	99	68.86	100	0.13
	13-2000	3	0	-	3 2242	33-0650 5	79	112.47	100	<0.001
	14-2500	4	1 3366	2 2542	34-0750 4	94	10.04	99	5.53
	15-3000	5	77 2332.87	83 1748.52	35-1500 6	48	108.02	100	2.24
	16-0260 11 100	<0.001 100	<0.001 36-2000 7	87	167.95	97	10.39
	17-0300	4 100	<0.001 100	<0.001 37-2250 5	14	834.5	100	1.66
	18-0350	8 100	<0.001 100	<0.001 38-2500 3	42 1168.67	100	4.96
	19-0350	6 100	2	100	<0.001 39-2750 3	0	-	0	-
	20-0420 10 100	<0.001 100	<0.001 40-3000 4	64	722.81	98	15.8

Table 3

 3 More details on hard instances.

	Instance	Method	2	3	4	5	6	7	8	9	10	11
	12-1500	downward	*	2	16	15	34	33
		upward	36	9	4 5	6	1	3
	13-2000	downward		*	11	47	40	2
		upward		3	57	27	13
	14-2500	downward			1	33	49	4		1	9	3
		upward			2	46	51		1
	31-0400	downward				65						35
		upward				18	6					7 6
	39-2750	downward		*								100
		upward		*					2			98

Acknowledgments

Special thanks to Van-Dat Cung (PRiSM-UVSQ), Thierry Defaix (CELAR-DGA) and Maurice Diamantini (ENSTA) for allowing us to use their FAPP definition. Thanks also to Eric Nabor from THALES-COMMUNICATIONS for helpful discussions.


Michel Vasquez
email: vasquez@site-eerie.ema.fr

New Results on the Queens n 2 Graph Coloring Problem

Keywords: queens graphs, graph coloring, independent sets, cliques based filtering

For the Queens n 2 graph coloring problems no chromatic numbers are available for n > 9except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14.

Introduction

Given a n × n chess board, a queen graph is a graph with n 2 vertices, each of them corresponding to a square of the board. Two vertices are connected by an edge if the corresponding squares are in the same row, column, or diagonals (both ascending and descending diagonals), this corresponds to the rules for moving the queen in a chess game.

The coloring problem for this graph consists in finding the minimum number of colors necessary for placing n 2 queens on the board so that two queens of the same color cannot attack each other. Finding this number (the chromatic number χ)is an optimization problem. We may also consider the following decision problem: given a n 2 chess board, is it possible to place n sets (each of them corresponding to a given color)of n queens on the board so that there is no clash between two queens in the same set? [START_REF] Gardner | Further Mathematical Diversions: The Paradox of the Unexpected Hanging and Others[END_REF] states without proof that this is the case if and only if n is not divisible by 2 or 3. If so, n = χ(Queens n 2 )notedχ n -since the maximum clique number is n (the rows, the columns and the 2 main diagonals constitute the 2n + 2 maximum cliques of this graph).

Although the graph coloring problem has been the subject of intense research, applications to the Queens n 2 problem are much scarcer: [START_REF] Mehrotra | A Column Generation Approach for Graph Coloring[END_REF] use a column generation approach to the independent set formulation of the graph coloring problem, devising an efficient algorithm tosolve the maximum weighted independent set problem arising in the column generation process, and are able to solve problems up to n = 9. [START_REF] Caramia | Iterative Coloring Extension of a Maximum Clique[END_REF] suggest a sophisticated algorithm based on the iterative coloring extension of a maximum clique; extensive computational results are given, Queens n 2 problems are solved up to n = 9. Heuristic methods canalso be used: Kochenberger et al. (to appear) transform general binary integer problems into unconstrained quadratic binary problems, and solve these problems using the tabu search method. Queens n 2 problems up to n = 10 are tackled, but non-exact methods (see [START_REF] Chiarandini | An Application of Iterated Local Searchto Graph Coloring Problem[END_REF][START_REF] Hamiez | Coloration de Graphes et Planification de Rencontressportives: Heuristiques, Algorithmes et Analyses[END_REF] for other recent works) fail to prove that χ n = n and only give an upper bound for the chromatic number.

Our approach

Due to the above observation concerning maximum cliques, the chromatic number of the Queens n 2 is greater than or equal to n. We consider the question: "Are n colors enough to color the Queens n 2 ?". Considering this decision problem, and taking into account the specific characteristics of the Queens n 2 graphs, we shall design a straightforward algorithm.

This algorithm is mainly based on the notion of an independent set (IS). An IS is a subset of vertices not linked by an edge of the graph: the vertices of an IS can all have the same color.

If n colors are enough to color the Queens n 2 graph, then each coloring with n colors defines n independent sets (one for each color). Since no IS can contain more than n vertices while n 2 vertices have to be colored, the answer to the above question is positive if and only if there are n disjoint independent sets I 1 . . . I n with exactly n vertices each.

Independent sets

Hence, the frst step for solving Queens n 2 consists in enumerating all IS with n vertices (in other words in computing the set IS n of candidate independent sets: the global set of IS). This step is completed by a standard depth-first search that uses the forward checking technique effciently to reduce the search space. Starting from each square of the first row on the chess board, this algorithm erases the column and diagonals under the current row before trying to find a free (unerased) square in the next row. A new IS is added to IS n if there is a square remaining in the last row of the chess board.

We thus replace the vertex ← {colors} assigning problem by the IS n ← {0, 1} assigning problem: the value is 1 if the corresponding IS is selected, 0 otherwise. That leads us from a n n×n search space size to one of size 2 |ISn| . For instance, this preprocessing step applied to Queens 5 2 decreases the number of combinations from 298023223876953000 to 1024 since |IS 5 | = 10.

Actually, trying to solve the problem by selecting such IS avoids manyincorrect color assignments during the coloring process.

Branching and backtracking rules

The choice of these n IS, among the |IS n | candidates, is submitted to the non overlapping constraint: ∀i = j, I i ∩I j = ∅ (only one queen by square). This assignment task is achieved by a branch and bound procedure. Note that assigning one IS corresponds to coloring n vertices (or squares): the depth of the search tree is less than n.

Every time an IS I i is selected, propagation on the constraint above is carried out: all I j such that I i ∩ I j = ∅ are removed from the global set of IS: IS n .

At every stage in the search we can identify the subsets IS i j of IS that cover each free square (i, j) of the chess board. The non colored square which can be covered by the smallest number of remaining IS corresponds to the branching node. More precisely, the next branching node is made up of the minimal subset IS min = argmin{|IS i j |, (i, j) non colored square}. Exploring this node consists in sequentially selecting each IS of IS min . The search tree is not a binary one but a variable breadth one depending on |IS min |.

Eventually, the process backtracks as soon as IS min = ∅ occurs.

Dynamic filtering based on cliques

It is not a new idea to reduce the search space while exploring it (see, for instance, the study of [START_REF] Sabin | Contradicting Conventional Wisdom in Con-Straint Satisfaction[END_REF] for general CSP framework and [START_REF] Caramia | Constraint Propagation in Graph Coloring[END_REF] for a graph coloring application of constraint propagation). The key point of such a technique is to find a condition that eliminates numerous values while needing little computing time to be evaluated. The principle of our filtering procedure is as follows. After the ith IS assignment ni other IS have to be chosen to constitute a solution. If, at this stage of the search, there exists, in the subgraph of non colored squares, a clique of size ni, C n-i , then all the remaining IS to be chosen must cover one vertex in this clique. This means that if the condition I j ∩ C n-i = ∅ holds for an I ∈ IS n , then we can remove this I j from the search space under the current node of the tree search. By construction, the I j can not produce such a condition with squares belonging to the same row or column (there are no more than n rows and n columns in the chess board, and each I j counts n vertices). This is not the case for the diagonals. For example, at the root of the search tree, we can delete the IS which do not cover one square of each of the 2 main diagonals. At the next node we can consider these 2 main diagonals plus the 4 with n -1 squares, and so on. We only need to update one counter and implement one test for each diagonal to check this condition.

To summarize, this filtering procedure is based on cliques corresponding to the diagonals of the chess board.

Experimentation

In this section we briefly give some details of the largest structures used to implement the algorithm before showing the main results it has produced.

Implementation

The algorithm is written in the C programming language.

Independent sets are stored in a global two dimensional array Big IS Array that contains |IS n | × n entries to memorize the n column numbers that define each IS in IS n .

Two other tables of size proportional to |IS n | are used to keep track of the non overlapping constraint on the remaining IS. This constraint is propagated effciently by means of an n × n array of pointers to tables which contain the addresses in Big IS Array of the IS covering the square in row i and column j. The numbers |IS i, j | of these IS are stored in a n × n array of integers (see figure 1 for an example). Considering Queens 15 2 problem which has 1484400 IS, the structure Big IS Array uses 85 MB of memory, then, for each node of the search tree,we need one array for the pointers to the IS, this gives a total amount of 85 × (1 + 15) = 1360 MB RAM.

Results

Computation was carried out on a PENTIUM 4 1.7 GHz CPU with 512 MB RAM.

Up to Queens 11 2 the answer is instantaneous. There is no solution for Queens 10 2 . Thus X 10 ≥ 11. Since X 11 = 11 we deduce that X 10 = 11 (the first 10 rows and the first 10 columns of the Queens 11 2 solution constitute a 11 colors correct assignment for the 10 × 10 chess board). Exploring the search tree for Queens 12 2 requires less than 2 hours CPU. The enumeration finds 454 solutions proving that X 12 = 12. The algorithm hence achieved complete-ness for Queens 10 2 and Queens 12 2 .

Unfortunately, instances become quickly intractable when n increases (we limited the CPU time to one week). Finding a solution for Queens 14 2 required some parallelization. The 9990 IS of the first IS min set (which corresponds to the first node of the search tree), are distributed on several CPU. The process starting with the 9987th IS provided a solution after 472692 seconds of computing time. This result is weaker than completeness but it is enough to prove that X 14 = 14.

The figure 3 gives certificates for both the Queens 12 2 and Queens 14 2 coloring numbers. Each letter represents a color. We can note symmetries on the two above solutions. The IS always appear in pairs and are symmetric (horizontally for n = 12 and vertically for n = 14). It is also the case for the 454 other solutions of Queens 12 2 . Exploiting this remark would divide the tree depth by two. However, even if we could generalize this result, it would not allow us to cope with the Queens 16 2 problem since it counts 4543410 pairs of IS: that For n = 4 and n = 6 no branch and bound is needed because there are not enough IS to cover the chess board.

This table answers the question: is X n = n ? for values of n up to 14.

Conclusion

We have proposed an exact algorithm for solving the Queens n 2 coloring problems. This algorithm makes major use of a particular characteristic of these graphs: only independent sets with n vertices are useful to answer the question: "is Queens n 2 chromatic number equal to n ?". This leads us to a straightforward enumeration approach intended to select n independent sets rather than assign colors to n 2 vertices. The branch and bound procedure is reinforced by an efficient filtering technique based on the cliques belonging to the vertices of the graph which are not colored yet. Thus, at each node of the tree, many independent sets are removed, drastically decreasing the size of the remaining search space.

Experimentation provided 3 new results: X (Queens 10 2 ) = 11 , X (Queens 12 2 ) = 12 and X (Queens 14 2 ) = 14. That is the qualitative contribution of this work.

Moreover the results for n = 12 and n = 14 are the same for Queens m × n problems (m × n chess boards for which m ≤ n) since the maximum clique number is still equal to n when m < n.

Perspectives

Firstly, the investigation of symmetries noted in Section 3.2 should enable to obtain results for larger instances than Queens 14 2 . For this purpose, we suggest to modify significantly the data structures used by our first algorithm. More precisely, the concept aims at changing the balance between speed and memory consumption. We strongly believe that this is a promising way to improve our algorithm.

Secondly, the results obtained on Queens 12 2 and Queens 14 2 constitute an example of some instances that are not too large and have never been solved by any heuristic approach (see for instance [START_REF] Chiarandini | An Application of Iterated Local Searchto Graph Coloring Problem[END_REF][START_REF] Hamiez | Coloration de Graphes et Planification de Rencontressportives: Heuristiques, Algorithmes et Analyses[END_REF]Kochenberger et al., to appear). Here we have an implement of critical analysis and maybe even a perfecting implement for these inexact resolution methods of dificult problems, that we are going to investigate in a near future.

Figure 1 .

 1 Figure 1. Distribution of the IS at the root of the search tree for Queens 10 2 .

Figure 2 .

 2 Figure 2. |IS i, j | after the first assignment of the search process for Queens 10 2 .

Figure 3 .

 3 Figure 3. Certificates for X 12 = 12 and X 14 = 14.

Table 1 .

 1 Filtering efficiency and other global indications. Big IS Array and 8 × 277 MB for the 8 arrays of pointers to IS needed by the search tree.Finally, the Table1summarizes the computational results obtained for instances up to n = 15. For each Queens n 2 instance, we show the number of vertices (|V |), the number of edges (|E|), the preprocessing-for IS n -CPU time in seconds ( pp.t.), the number of IS before filtering on n cliques: (|IS n |) and after: (|IS f n |), the number of solutions found (|sol.|), the search completeness state (cmpl.) and the total CPU time (t.t.).

	n	|V |	|E|	pp.t.	|IS n |	| IS	f n |	| sol.|	cmpl.	t.t.
	4	1 6	7 6	0	2		0	0	yes	0 sec.
	5	2 5	160	0	10		10	2	yes	0 sec.
	6	3 6	290	0	4		0	0	yes	0 sec.
	7	4 9	476	0	40		32	4	yes	0 sec.
	8	6 4	728	0	92		48	0	yes	0 sec.
	9	8 1	1056	0	352		232	0	yes	0 sec.
	10	100	1470	0	724		544	0	yes	0 sec.
	11	121	1980	0	2680	1744	8	yes	1 sec.
	12	144	2596	0	14200	9440	454	yes	6963 sec.
	13	169	3328	2	73712	52008	295	no	168 hours
	14	196	4186	15	365596	238088	1	no	168 hours
	15	225	5180	73	2279184	1484400	?	no	168 hours
	means 277 MB RAM for the

* Joint "Ecole des Mines d'Alès, Commissariat à l'Energie Atomique" Research Team.

Acknowledgments

We would like to thank the anonymous referees for the valuable and detailed comments which helped to improve the presentation of this paper.


Cédric Fandio

Nathan Vezinaud

Geneviève Zembri-Mary

Hanane Krim

Genevieve Zambri-Mary

Integrating Urban Planning and Rail Transport for High-Quality Urban Development in sparsely populated areas: Case Studies of Bearn (France) and Canton of Jura (Switzerland)

Keywords: Béarn, Bonfol, Porrentruy, Sparsely populated area, Rail transport, Urban planning

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Integrating Urban Planning and Rail Transport for High-Quality Urban Development in sparsely populated areas: Case Studies of Béarn (France) and Canton of Jura (Switzerland)

Axis contracts are a kind of urban planning-transport coordination tool that has been used for planning and policy coordination as well as for studing densification around the railway (Gallez et al. in [START_REF] Gallez | Myth and practices of urban planning-transport coordination[END_REF]; Maulat in [START_REF] Maulat | The role of territorial planning in the coordination of town planning and regional rail transport policies at the metropolitan scale: The Toulouse example[END_REF] and in [START_REF] Maulat | Contracting to coordinate urban planning and transport? Crossreferences on four railway axis contract experiences[END_REF]; Bentayou et al. in [START_REF] Bentayou | Contrat d'axe et Transit-Oriented Development: quel renouvellement de l'action publique en matière de mobilité et d'aménagement (Stakeholder perspective)[END_REF]; Meunier-Chabert in [START_REF] Meunier-Chabert | Axis contracts in France: where are we?[END_REF]). However, some authors have partially addressed di culties, such as those related to the low level of involvement for specific community categories like Maulat et al. in [START_REF] Maulat | Contracting to coordinate urban planning and transport? Crossreferences on four railway axis contract experiences[END_REF] and [START_REF] Maulat | The role of territorial planning in the coordination of town planning and regional rail transport policies at the metropolitan scale: The Toulouse example[END_REF]. In order to address this issue, we focue in this work on the public action strategies and governance instruments used in two railway axes contracts; the Béarn axis contract in the Nouvelle-Aquitaine region (France), which focuses specifically on the Puyoo -Pau -Montaut-Bétharram and Pau -Oloron -Bedous railway lines (Aquitaine Region, 2015), and the Canton of Jura agreement relating to railway line 238 that connects city of Porrentruy to the commune of Bonfol (Suitzerland) (contrat d'axe Canton du Jura, 2017 in [START_REF] Of | Avenir de la ligne 238 Porrentruy-Bonfol: contrat d'axe[END_REF]). The research problem and our study hypothesis are discussed in depth in the first section, which is then followed by a description of the qualitative research technique we used, which included documentary analysis and semi-structured interviews. The territorial analysis grid, a crucial analytical tool created to analyze government options, is then introduced. The parts that follow give a detailed account of our findings, highlighting the impact institutional systems have on governance, before going over our theoretical framework and closing with implications and future ideas. In essence, this article explores the complicated environment of rail axes governance to clarify its various aspects and impacts.

Methodologiy

Problem statement and reserch hypothesis

Governance can be described as a way that di↵erent players, social groups, and institutions interact and coordinate, not necessarily all belonging to the government, to achieve common objectives defined collectively. This process involves using tools called "public action instruments," which are essentially devices that help manage how government authorities and their intended recipients interact, influenced by the meanings and representations they convey (Lascoumes, Le Galès 2005, p. 13). Given this perspective, let's explore how the governance of the two studied rail corridor contracts is organized. How do the institutional frameworks in these areas influence the use of these tools? To address these questions, we propose the hypothesis that the approach to contracts in Pays du Béarn is potentially less inclusive and participative compared to that in the Canton of Jura. This di↵erence is attributed to the distinct institutional frameworks in these two regions.

Qualitative approach using documentary analysis and semi-structured interviews based on an interview guide

First, the planning documents for the two study regions highlight concerns about methods for densification near the railway. Aquitaine Region (2015) and Canton du Jura (2017) allow us to identify and list the actions planned or programmed, the goals of which are to organize coordination between the various players involved in the process in order to promote monitoring. In this case, the railway axis contracts of the Pays du Béarn and the Canton du Jura.

Then, the local players in the study's study areas, with whom we are conducting semi-structured interviews, are likewise faced with this issue. Between May 2023 and June 2023, these interviews with local stakeholders of varying status were conducted in the two designated areas. They were conducted utilizing an interview framework that addressed governance-related topics. The discourse of the players interviewed was then analyzed using a geographical analysis grid created for this purpose in order to pinpoint the governing processes driving the implementation of the route contracts.

Territorial analysis grid

The governance of the rail axes contracts under investigation is one of the public action levers available to local parties to implement a policy of densification around the railway. In order to make sure that these activities are being monitored, it isused to organize the parties involved. This tool is one of several that make up a territorial analysis grid (as presented in Figure 1) that is used to decipher the tools and techniques applied in the axis contracts as well as the perspectives of the participants. Based on research on the issues with coordinating urban planning and rail transportation (Gallez et al. in [START_REF] Gallez | Myth and practices of urban planning-transport coordination[END_REF]; Bentayou et al.in [START_REF] Bentayou | Contrat d'axe et Transit-Oriented Development: quel renouvellement de l'action publique en matière de mobilité et d'aménagement (Stakeholder perspective)[END_REF]; Maulat [START_REF] Maulat | Contracting to coordinate urban planning and transport? Crossreferences on four railway axis contract experiences[END_REF][START_REF] Maulat | Contracting to coordinate urban planning and transport? Crossreferences on four railway axis contract experiences[END_REF]; Meunier-Chabert in [START_REF] Meunier-Chabert | Axis contracts in France: where are we?[END_REF]), four territorial analysis indicators were created. Figure 1 displayed as a table, provid a structured view of the rail axes contracts' key elements. In this table, the top row outlines the primary goals and objectives specified in the contract's o cial documents.

The subsequent three rows delve deeper into these objectives, elaborating on the specific public actions designed to attain them. This detailed breakdown helps to understand the steps and strategies involved in achieving the outlined goals. In the last row of the table, you'll find a listing of governance tools that have been implemented within the rail contracts to facilitate the realization of these objectives. These tools serve as mechanisms for coordination and management. Finally, the table's last column introduces the theoretical framework of "multi-level governance." This framework is crucial for interpreting the perspectives and discussions of the stakeholders interviewed in the context of the rail axes contracts.

Results

Institutional systems shape how governance works, influencing public actions at both national and local levels. They provide insights into what can be achieved and how it's done. For instance, France is a decentralized unitary state with a strong central government, which can sometimes exclude certain groups like private developers, NGOs, and foundations, leading to challenges.

On the other hand, Switzerland, as a Confederation known for shared management and participatory democracy, has a di↵erent governance model. These distinct institutional dynamics in France and Switzerland impact how public policies, including rail contracts, are designed and carried out.

In the case of rail corridor contracts in Béarn and the Canton of Jura, they rely on partnerships involving various stakeholders pursuing common goals. Notably, these partnerships tend to be more inclusive in Switzerland than in France due to their di↵ering institutional frameworks (Palier et al in [START_REF] Palier | The "Three Is" and the analysis of the State in action[END_REF]; Poupeau in [START_REF] Poupeau | Analyze multi-level governance[END_REF]).

Discussion

In this paper, we examine the strategies and methods applied in the Béarn and Canton de Jura rail corridor contracts. We employ a theoretical framework called neo-institutionalism, which allows us to comprehend that contemporary decisions are often influenced not solely by e ciency but also by established norms and practices. It's important to note that while we primarily utilize neoinstitutionalism, other approaches, such as inter-organizational analysis, can also provide valuable insights into the motivations and interests guiding public actions (Poupeau in [START_REF] Poupeau | Analyze multi-level governance[END_REF]; Palier et al. in [START_REF] Palier | The "Three Is" and the analysis of the State in action[END_REF]). likely to encourage urban densification around these di↵erent rail routes? If so, which do you think are the most relevant? If not, why not? What do you recommend achieving this? What are the main obstacles that need to be overcome to achieve the desired objective? -5-Do you have anything to add to conclude our interview? Would you be willing to take part in a focus group we could organize on this topic with other local players in the coming weeks?

Fig. 1 :

 1 Fig. 1: Regional analysis grid for rail transport policies (Source: author based on Rapport Jacques Chauvineau (2001), Region Aquitaine (2015), Canton du Jura (2017))

-

  EJ2: Head of the Transport Mobility Section -EJ3: Former project manager, drafters of the axis contract -EJ4: Mayor of Bonfol -EJ5: Developer participating in the Route Committee -EJ6: Current municipal planner B APPENDIX 2: INTERVIEW GUIDE -1-What is your name, position and reporting structure? -2-Who are the main players involved in drawing up and implementing the Bearn axis contract, and what are their responsibilities? -3-What tools or resources do local authorities have at their disposal to encourage a policy of densification around the railway? How can the Route Contract help? -4-Generally speaking, are the measures set out in the Bearn axis contract