Andréa Cynthia Santos
email: andrea@isima.fr

Solving large p-median problems using a Lagrangean heuristic

Keywords: Lagrangean heuristics, primal-dual heuristics, p-median problem. Résumé Heuristiques lagrangiennes, heuristiques primal-dual, problème des p-médianes

The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean relaxation. Variable fixing tests are used to reduce the size of the problems and a local search procedure is also applied. Variable fixing strategies eliminate 90% of arcs on average. Computational results are reported for large graph instances with about 4000 nodes and 14 millions arcs.

Introduction

Let G = (V, A) be a directed graph with a set V of vertices and a set A of arcs. Let c ij ∈ , ∀(i, j) ∈ A, be the cost of assigning a demand j ∈ V to a median i ∈ V (medians are also referred to facilities or locations in the literature). Given a positive integer 0 < p ≤ |V |, the p-median problem consists in selecting p medians in V such that the total cost of assigning each demand to the closest median is minimized. This problem belongs to the set of NP-hard problems on general graphs G for an arbitrary p [START_REF] Garey | Computers and intractability: A guide to the theory of NP-Completeness[END_REF].

The interest of solving p-median problems appears as it is the core of many location problems and because of its large number of applications. For example, several location applications are found in [START_REF] Tansel | Location on networks: a survey part i: the p-center and p-median problems[END_REF] and cluster analysis are shown in [START_REF] Hansen | Cluster analysis and mathematical programming[END_REF][START_REF] Rao | Cluster analysis and mathematical programming[END_REF]. The amount of work dedicated to this problem has significantly increased in the last decade [START_REF] Reese | Solutions methods for the p-median problem: an annotated bibliography[END_REF], and there is a clear improvement in the state of the art for the problem. Advanced heuristics such as Lagrangean heuristics [START_REF] Senne | Lagrangean/surrogate heuristics for p-medians problems[END_REF] and metaheuristics [START_REF] Resende | A hybrid heuristic for the pmedian problem[END_REF], and sophisticated exact algorithms such as the branch-and-price-and-cut [START_REF] Avella | Computational study of largescale p-median problems[END_REF], and the semi-lagrangean relaxation [START_REF] Beltran | Solving the p-median problem with a semi-lagrangean relaxation[END_REF] have been proposed. Improvements on the polyhedral characteristics for the p-median have been done, for example in [START_REF] De Farias | A family of facets for the uncapacited p median polytope[END_REF]. Moreover, efficient variable fixing strategies for a problem close to the p-median are presented in [START_REF] Briant | The optimal diversity management problem[END_REF]. For further investigation, readers are referred to the following surveys: work [START_REF] Reese | Solutions methods for the p-median problem: an annotated bibliography[END_REF] provides insightful information for more than 200 articles on the classic version of the p-median problem. An overview on heuristics and metaheuristics approaches can be found in [START_REF] Captivo | The p -median problem: A survey of metaheuristic approaches[END_REF][START_REF] Hansen | Complement to a comparative analysis of heuristics for the p-median problem[END_REF]. For the state of the art and theoretical analysis see, for example, [START_REF] Tansel | Location on networks: a survey part i: the p-center and p-median problems[END_REF][START_REF] Tansel | Location on networks: a survey part ii: exploiting tree network structure[END_REF].

In this work, a new Lagrangean heuristic is proposed on a classic Lagrangean relaxation, as presented in [START_REF] Narula | An algorithm for the p-median problem[END_REF]. The typical heuristic for that Lagrangean relaxation does not perform well as mentioned in [START_REF] Briant | The optimal diversity management problem[END_REF] and it uses a single criterion to choose the medians. The heuristic proposed in this work uses two criteria to select the medians. The second criterion uses an information from the dual solution to build a primal solution. Some efficient reduction tests are applied and the proposed heuristic is coupled with a local search. The subgradient method of [START_REF] Held | The travelling-salesman problem and minimum spanning trees[END_REF] is used to compute Lagrangean multipliers. The algorithm is tested on the OR-library [START_REF] Beasley | OR-Library: Distributing test problems by electronic mail[END_REF] and on the TSP-Library [START_REF] Reinelt | TSPLIB -A traveling salesman problem library[END_REF] instances. Results show that the Lagrangean heuristic suggested here outperforms results obtained using a classic Lagrangean heuristic. The variable fixing tests eliminate 90% of arcs on average. After reductions, it only remains a core that contains the hardness of each instances. Instances for which optimality was not proved, duality gaps are lower than 2%. Some remaining gaps are closed by using the branch-and-cut tree of a commercial solver.

This paper is organized as follows: a mathematical formulation is presented in Section 2. A Lagrangean relaxation based on the referred formulation is described in Section 3. In Section 4, the Lagrangean heuristic is described in detail. Section 5 is dedicated to the reduction tests. Computational results are reported in Section 6 and some concluding remarks are given in Section 7.

Problem formulation

Binary variables x ii are associated with every node i ∈ V to identify if node i is chosen as a median. Variables x ij are associated with every arc (i, j) ∈ A to state whether node j is connected to the median i or not. Then, the p-median problem can be formulated as follows:

min (i,j)∈A c ij x ij st. (1)
i:(i,j)∈A

x ij + x jj = 1 ∀j ∈ V (2)
i∈V

x ii = p (3)
x ij ≤ x ii ∀(i, j) ∈ A (4)
x ii ∈ {0, 1} ∀i ∈ V (5)

x ij ≥ 0 ∀(i, j) ∈ A (6)
The objective function (1) minimizes the total cost of assigning each node j to a median i. Equations (2) state that either a node j is connected to one median or j is a median. Constraint (3) ensures that p nodes are chosen as median. Inequalities (4) state that a node j can be connected to a node i only if i is a median. Variables x are defined in Constraints ( 5) and [START_REF] Belloni | A lagrangian heuristic for the linear ordering problem[END_REF].

A feasible solution S for the p-median problem can be represented as a set of p clusters: a cluster q i is a set of nodes with one median i (x ii = 1) and with nodes {j 1 , j 2 , ..., j l } (l ≤ |V | -p) connected to i by an arc, that is (x ij = 1). Thus, a solution S = {q 1 , q 2 , ..., q p }, with no arcs between the clusters. Figure 1

Lagrangean relaxation

Different Lagrangean relaxations based on the formulation ( 1)-( 6) can be found in the literature: [START_REF] Narula | An algorithm for the p-median problem[END_REF], [START_REF] Christophides | A tree search algorithm for the pmedian problem[END_REF], [START_REF] Hanjoul | A comparasion of two dual-based procedures for solving the p-median problem[END_REF], and [START_REF] Mirchandani | Multidimensional extensions and a nested dual approach for the m-median problem[END_REF]. In this work, the Lagrangean relaxation proposed by [START_REF] Narula | An algorithm for the p-median problem[END_REF] is used since it produces very good lower bounds. Lagrange multipliers λ j ∈ are associated to the Constraints [START_REF] Avella | Computational study of largescale p-median problems[END_REF], which are dualized. The corresponding Lagrangean dual problem is as follows:

L 1 (λ) = min i∈V j∈V (c ij -λ j ) • x ij + j∈V λ j st. (7)
Constraints ( 3) - [START_REF] Belloni | A lagrangian heuristic for the linear ordering problem[END_REF].

Let d ij = c ij -λ j be the Lagrangean costs. For each node i ∈ V , its associated auxiliary cost is defined as f i = d ii + j∈V \{i} min{0, d ij }. Thus, L 1 (λ) can be reformulated as:

L 1 (λ) = min i∈V f i x ii + j∈V λ j st. (8)
i∈V

x ii = p (9)
x ii ∈ {0, 1} ∀i ∈ V (10)
The Lagrangean subproblem ( 8)-( 10) corresponds to a simple enumeration of the p facilities with the smallest costs f i . This Lagrangean relaxation has the integrality property. Thus, the best lower bound attained using this Lagrangean relaxation is equal to the lower bound of the linear relaxation for the problem (1)- [START_REF] Belloni | A lagrangian heuristic for the linear ordering problem[END_REF]. The subgradient method of [START_REF] Held | The travelling-salesman problem and minimum spanning trees[END_REF] is used to compute Lagrangean multipliers λ j . At each subgradient iteration k, multipliers λ k j are calculated as well as the auxiliary costs f k i . Then, since the p-median is a minimization problem, medians with the smallest auxiliary cost are selected for the dual solution. Moreover, each node j not chosen as median is connected to the median i (x ij = 1), whenever d k ij < 0 and x ii = 1. Arcs included in the solution have an associated negative Lagrangean cost. They have contributed in the computation of the auxiliary costs f k i , ∀i ∈ V , at iteration k.

Lagrangean heuristics

Lagrangean heuristics have been successfully applied to a large number of problems in the literature, see for example [START_REF] Andrade | Using lagragian dual information to generate degree constrained spanning trees[END_REF][START_REF] Belloni | A lagrangian heuristic for the linear ordering problem[END_REF]. In particular, for the p-median problem and its variants, Lagrangean heuristics are presented in [START_REF] Beasley | Lagrangean heuristics for location problems[END_REF][START_REF] Senne | Lagrangean/surrogate heuristics for p-medians problems[END_REF]. A basic characteristic of these strategies is the use of dual Lagrangean information to produce primal solutions.

Let us assume that, at each subgradient iteration k, the vector f k contains the auxiliary costs f i in increasing order :

f k = [f k 1 ≤ f k 2 ≤ ... ≤ f k p ≤ f k p+1 ≤ ... ≤ f k |V | ].
The p first nodes are the set of medians for the dual problem. Let UB k and LB k be respectively the current values of the upper and of the lower bounds, at iteration k. Moreover, UB * and LB * are respectively the best values of the upper and of the lower bounds found so far.

The classic primal heuristic for relaxation ( 8)- [START_REF] Christophides | A tree search algorithm for the pmedian problem[END_REF], denoted here of Classic Lagrangean heuristic (Classic LH), consists in generating a primal solution at each subgradient iteration k as follows: the p nodes with the smallest associated auxiliary costs in the vector f k are taken as medians. The remaining |V | -p nodes are connected to the closest median. This is a straightforward way to generate primal solutions based on Lagrangean relaxation (8)- [START_REF] Christophides | A tree search algorithm for the pmedian problem[END_REF]. The Classic LH worst case complexity is O(p • |V |). Unfortunately, results are not very good. This fact has motivated the investigation of better ways to improve primal solutions using dual information.

In the Lagrangean dual problem L 1 (λ), the dual solution for L 1 (λ) may contains clusters connected by arcs. Figure 2 illustrates a dual solution with violations in an iteration of the subgradient method using L 1 (λ). The dotted lines can be interpreted as an indecision about the connection of those nodes. Moreover, the second type of violation corresponds to the nodes 2, 7, 10, 11, 14, 21 and 23 which are not medians, neither they are connected to a median. These kind of violations occurs quite often and it leads to the following questions: how does it impact the primal solutions? is it possible to take advantage of those violations to improve a primal heuristic such as the Classic LH ? These violations can be reduced once the subgradient method converges. However, earlier good upper bounds are met, better for the convergence of the subgradient method. To avoid the transfer of those indecisions (see Figure 2) from a dual solution to a primal solution, the heuristic proposed here, denoted Collecting medians, consists in taking the p first nodes with the smallest auxiliary costs as median, if there are no arcs between the medians in a dual solution. Thus, the Collecting medians considers the nodes in ascending order of f k , and it selects a node as a median if it is not connected to the previous medians. After evaluating f k until the position |V |, if less than p medians are selected, the procedure performs an additional step. It consists in considering the nodes with the smallest auxiliary cost from p + 1 to |V |, then from 1 to p as a median (this step is seldom performed). In doing so, feasibility is ensured. In the additional step, the test of connection with the previous medians is not performed. The |V | -p nodes are connected to the closest median. For example, using the Collecting medians based on the dual solution shown in Figure 2, node 3 is not chosen as a median since it has auxiliary cost f 3 bigger than f

Local search procedure

Two local search procedures are used. The first is called optimizing clusters local search and it is used at each iteration of the subgradient method. The second one is the swap local search introduced by [START_REF] Teitz | Heuristic methods for estimating the generalized vertex median of a weighted graph[END_REF]. Efficients implemen-tations for the swap local search is proposed by [START_REF] Whitaker | A fast algorithm for the greedy interchange of large-scale clustering and median location problems[END_REF][START_REF] Resende | On the implementation of a swapbased local search procedure for the p-median problem[END_REF]. The neighbourhood of the swap local search is bigger than the optimizing clusters local search, and it consumes a larger running time at each iteration. As a consequence, it is applied when a best upper bound is attained or after performing a number of iterations without improving the best upper bound found so far.

The optimizing cluster local search procedure is as follows: given a feasible solution S, for each cluster q i , a local search move consists in building a new cluster q i having the same set of vertices in q i , such that one of the vertices in this cluster {j 1 , j 2 , j 3 , ..., j l }, (l ≤ |V | -p), say j k , will act as its new median. A move is accepted under two conditions: first, it reduces the cost of S and second, it is the best move in a cluster q i . This step consumes p • (|V | -p) time in the worst case.

An iteration of this local search consists in investigating every cluster q i ∈ S. After that, if at least one move is done in a cluster, an additional test is performed. Given a node j connected to the median i, the test checks if there is a median l = i such that c lj ≤ c ij . This test is done for all node j that are not median and that do not belong to the cluster q i . This step requires (|V | -p) • p time in the worst case. Thus, an iteration of this local search consumes p • (|V | -p) time in the worst case. The local search procedure stops when no improving move is found. An example is shown in Figure 3. A cluster q i is shown in Figure 3-(a) where i is its median. All possible neighbour clusters are depicted in Figures 3-(b) to 3-(d). If at least a move is done in one cluster, the additional step mentioned above is performed. A typical local search for the p-median problem [START_REF] Teitz | Heuristic methods for estimating the generalized vertex median of a weighted graph[END_REF] consists in finding the best swap between a median and a non-median node. Given a solution S and a candidate to be median j, the procedure computes the highest cost gain of introducing j as a median in S and the smallest cost loss of removing a current median i in S. Whenever, the total cost of S is improved and it corresponds to the best move in the neighbourhood, the move is performed. The procedure stops when no improving move is found. [START_REF] Whitaker | A fast algorithm for the greedy interchange of large-scale clustering and median location problems[END_REF] and [START_REF] Resende | On the implementation of a swapbased local search procedure for the p-median problem[END_REF] implementations for this local search consume at each iteration, O(|V | 2 ) time in the worst case. The difference relies on updating the data structures which are speed up though the use of extra memory in [START_REF] Resende | On the implementation of a swapbased local search procedure for the p-median problem[END_REF]. [START_REF] Whitaker | A fast algorithm for the greedy interchange of large-scale clustering and median location problems[END_REF] implementation is used in this work.

i j 2 j 1 j 3 (a) i j 2 j 1 j 3 i j 2 j 1 j 3 i j 2 j 1 j 3 (b) (d) (c)

Problem reduction tests

Reduction tests allow variables to be fixed and thus the problem size is reduced. For the sake of clarity, fixing a variable associated to a node (x ii ) and to an arc (x ij ) is respectively referred to here as node fixing and as arc fixing. For the p-median problem, fixing a node to one implies that only p -1 medians need to be chosen afterward. Fixing a node to zero implies that the number of nodes able to be a median is reduced. Decisions can also be taken to fix arcs to zero or to one. The tests used here are adapted from [START_REF] Briant | The optimal diversity management problem[END_REF].

For every variable fixing test described in this section, the vector f k contains the auxiliary costs f k i in increasing order as mentioned in Section 4. Moreover, let V 0 and V 1 be respectively the set of medians fixed to 0 and fixed to 1, as well as A 0 and A 1 represent respectively the set of arcs fixed to 0 and fixed to 1.

The main idea to fix arcs to zero is to check if: including an arc in the solution will lead to a lower bound greater than the best upper bound found so far. If so, the arc cannot belong to an optimal solution. The first test to fix an arc to zero is as follows: given a median i, a node j not median, and d k ij the Lagrangean cost of arc (i, j). If (i, j) / ∈ A 0 , d k ij > 0 and Inequality (11) holds, arc (i, j) can be fixed to zero. Thus, A 0 = A 0 ∪ {(i, j)}.

LB k + d k ij > UB * (11)
The second test to fix an arc to zero is as follows: given two nodes j and l that are both not medians, thus, arc (j, l) is not in the current dual solution. Suppose that (j, l) is in an optimal solution. Then, j should be median and a median should be removed from the current dual solution. The dropped median is the one which contributes the least to the lower bound value. Its removal gives an under-estimation of the lower bound value with p -1 medians. If (j, l) / ∈ A 0 , d k jl > 0 and Inequality ( 12) is satisfied, then

A 0 = A 0 ∪ {(j, l)}. LB k -f k p + f k j + d k jl > UB * (12)
The general idea to fix nodes is similar to the one to fix arcs: if forcing a node to be a median (it implies that one of the current medians is removed) or if removing a current median (it means a new node is selected as a median) from a dual solution leads to a lower bound greater than the best upper bound found so far, variables are fixed. Fixing nodes result in fixing arcs afterwards.

The first test used to fix a median to zero is as follows: given a node j that is not a median in the current dual solution, suppose that j is in an optimal solution. Forcing j in the solution implies removing one of the current medians. The selected dropped median is the one which contributes the least to the lower bound (f k p ). If node j / ∈ V 0 and Inequality ( 13) is satisfied, j cannot be a median in an optimal solution and V 0 = V 0 ∪ {j}. Consequently, if j cannot be a median in an optimal solution, j has no ingoing arcs. Thus, A 0 = A 0 ∪{(j, l)} for all (j, l) ∈ V . This test starts with the node j with the highest associated auxiliary cost, that is (f k |V | ), and it is carried out until Inequality [START_REF] Garey | Computers and intractability: A guide to the theory of NP-Completeness[END_REF] does not hold anymore.

LB k -f k p + f k j > UB * (13)
The second test is applied to fix medians to one. It consists in assuming a current median is not in an optimal solution. The median i with the smallest auxiliary cost is kept because it is the one which most contributes to the current lower bound value. By doing so, a node j not median with the smallest associated auxiliary cost, that is f k p+1 , enters the solution. Whenever i is a median in the current dual solution, i / ∈ V 1 and Inequality (14) holds, node i is necessarily a median in an optimal solution. Thus,

V 1 = V 1 ∪ {i}.
If i is necessarily a median in an optimal solution, then every outgoing arc of i can be fixed to zero. In this case, A 0 = A 0 ∪ {(j, i)} for all (j, i) ∈ A. The test starts with the median with the smallest auxiliary cost and it is applied until Inequality [START_REF] Hanjoul | A comparasion of two dual-based procedures for solving the p-median problem[END_REF] does not hold anymore.

LB k -f k i + f k p+1 > UB * (14)
Another consequence of fixing a median i to one is: given an arc (i, j) that belongs to the current dual solution (that is d ij < 0). If (i, j) / ∈ A 1 and Inequality (15) holds, this arc necessarily belongs to an optimal solution. Then, A 1 = A 1 ∪ {(i, j)}. That means also node j is never a median in an optimal solution. Then, the consequences given above to fix a median to zero is applied to node j.

LB k -d k ij > UB * (15)
Some simple logical implications are used, basically to try to fix variables x ii to one. The aim is to take advantage of the large number of arcs eliminated from the problem. The first logical implication checks if a node is necessarily a median in an optimal solution: if j / ∈ V 1 , and if every outgoing arc of j is in A 0 , then j ∈ V 1 .

The second logical implication is as follows: given a node l ∈ V 0 with only one outgoing arc, say (i, l), and with all other outgoing arcs already fixed to zero. Then, arc (i, l) can be fixed to one, A 1 = A 1 ∪ {(i, l)}. Furthermore, in this case, i is necessarily a median in an optimal solution because l is assigned to node i.

Thus, if i / ∈ V , V 1 = V 1 ∪
and all consequences to fix a median to one are applied to node i.

Computational results

The experiments were carried out on a Core 2 Duo machine with 2.66 GHz of clock and 4 Gb of RAM memory. Cplex 11 is used to close the remaining gaps. The parameter uppercutoff is set to the UB * found by the heuristic Collecting medians. All other parameters are left to default values. Results are reported for the OR-library (OR-LIB) and for the TSP-Library (TSP-LIB) instances. The OR-LIB Instances with a bold name are those for which Cplex has run out of memory. The TSP-LIB instances with a bold name are those classified as difficult in [START_REF] Beltran | Solving the p-median problem with a semi-lagrangean relaxation[END_REF]. The Euclidean distances for the TSP-LIB instances are truncated as in [START_REF] Avella | Computational study of largescale p-median problems[END_REF][START_REF] Beltran | Solving the p-median problem with a semi-lagrangean relaxation[END_REF]. The parameters of subgradient method are set as suggested in [START_REF] Beasley | Lagrangean relaxation[END_REF]: 1000 subgradient iterations are run and the parameter π is divided by 2 each time 5% of the total number of iterations are attained.

In the first experiment, a comparison between the Classic LH and the Collecting medians is done. In this experiment, the variable fixing tests and the local search procedures are not used in the algorithm. The goal is to observe the real benefit of using the Collecting medians heuristic. The Classic LH is carried out at each iteration of the subgradient method. The same strategy is used for the Collecting medians. Results for a subset of the OR-LIB instances are presented in Table 1. The remaining instances of this group have similar results. Each line corresponds to an instance. Columns (Instances), (p) and (O * ) indicate respectively the instance name, the amount of medians and the optimal values. The linear relaxation (LR) obtained using the Cplex is given. Moreover, for both the Classic LH and the Collecting medians heuristic, the lower bound (LB), the upper bound (UB), For nine out of fifteen instances in this subset (values highlighted in bold on the column UB), the Collecting medians heuristic has met the optimal values. While, the Classic LH has found the optimal value for only one instance. For these nine instances, if there is a gap using the Collecting medians heuristic is due to the lower bound values. In terms of lower bounds, the Lagrangean relaxation attains the theoretical limit for almost all instances, except for the pmed27 and pmed32. For these instances in particularly, it seems the theoretical limit was attained independent of the upper bound quality. However, this is not the case for the TSP-LIB instances.

Cplex

Calibrating the variable fixing phase

Most work for the p-median problem does not check when the reduction tests are more likely to be efficient. Thus, a computational experiment was carried out to decide when to start the reduction tests. Variable fixing tests were introduced in the Lagrangean relaxation at each iteration after running the Collecting medians heuristic. Then, for each instance, the first iteration where the reduction tests start working was kept. Results are summarized in Table 2 for a subset of the OR-LIB instances. The remaining instances have similar results. Columns (Iteration), (LB), (UB) and (GAP) contain respectively the iteration number, the lower bound, the upper bound, and the relative gap which corresponds to the first iteration where the reduction tests start to work.

Results show that the reduction tests start to work when the gaps fall below 5%. Considering all the instances, the reduction tests begin to work earlier when the number of medians is smaller.

Results for the complete version of the Collecting medians heuristic

The complete version of the Collecting medians heuristic includes the two local search procedures and the variables fixing tests. At each iteration k of the subgradient method, a primal solution S k is computed using the Collecting medians heuristic. The TSP-LIB instances are used to illustrate the performance of the complete version of the Collecting medians because they are difficult instances containing a million to about fourteen millions of arcs. Cplex solver is not able to treat the TSP-LIB instances because it run out of memory. Results for a complete version of the Collecting medians heuristic are presented in Tables 3 and4. The follow instances were tested: rl1304 with 10, 100, 300 and 500 medians, fl1400 with 100, 200, 300, 400 and 500 medians, ul1432 with 20, 50, 100, 200, 300 and 400 medians, vm1748 with 10, 20, 50, 100, 300, 400 and 500 medians, d2103 with 10, 20, 50, 100, 200 and 300 medians, pcb3038 with 5, 100, 150, 200, 300, 400 and 500 medians, and fl3795 with 150, 200, 300, 400 and 500 medians. Results for a subset of the TSP-LIB instances is shown. The remaining instances have similar results. Table 3 contains the amount of variables fixed for each problem. The instance name (Instance), the number of nodes (|V |), and the number of arcs (|A|), and the amount of medians (p) are given. Columns (|V 0 |), (|V 1 |), (|A 0 |) and (|A 1 |) correspond respectively to the number of nodes fixed to zero, the number of nodes fixed to one, the number of arcs fixed to zero, and the number of arcs fixed to one. Moreover, the total percentage of fixed nodes (% fixed nodes) and of fixed arcs (% fixed arcs) are also given.

Most of the instances have a strong reduction of arcs fixed to zero with millions of arcs eliminated. Considering all the forty instances tested for the TSP-LIB, on average, 31.1% of nodes and 90.79% of arcs are fixed. For the TSP-LIB instances, in particularly, the variables fixing phase is an important tool to help proving optimality. After fixing several variables, it remains only a difficult core for each problem. Table 4 contains the results obtained for the TSP-LIB instances. Columns (Instances), (p), and (O * ) correspond respectively to the instance name, the amount of medians, and the optimal values. For the Collecting medians heuristics, the lower bound (LB), the upper bound (UB), the relative gap (GAP) (computed as (100 • (UB -LB)/LB)), and the time in seconds (time) round up are presented. Columns (final GAP) and (+time) give respectively the final gap and the extra time required to close the remaining gaps by using the Cplex solver. The symbol (-) means the solver has ran out of memory. Whenever there is a gap on the column (final GAP), it corresponds to the gap before the Cplex solver ran out of memory. That is the case of the instance fl1400 and p = 500 medians.

Instances |V | |A| p |V 0 | |V 1 | |A 0 | |A 1 | % fixed
For the forty TSP-LIB instances tested, the heuristic Collecting medians produces gaps really small. It allows to prove optimality for 30 out of 40 instances efficiently, specially considering its size. For some instances, even with a really small gap, cplex does not prove optimality because it ran out of memory. This happens for 10 out of 40 instances tested. They are fl1400 with 300, 400 and 500 medians, ul1432 with 400 medians, d2103 with 50 et 100 medians, and fl3795 with 150, 200, 400 and 500 medians. However, some difficult instances were solved as fl3795 with 300 nodes. For those 10 difficult instances, its core is now available and it can be exploited in future work using, for example, a specialized branch-and-cut tree. Using the Classic LH, it is possible to prove optimality for only 10 out of 40 TSP-LIB instances because of the produced gaps. For example, the best, the worst and the average gaps for this subset of instances are respectively 0.11%, 5.30% and 1.95%. It leads also to a weaker variables fixing: about 10% of nodes and 50% of arcs.

Conclusions

A new Lagrangean heuristic is proposed in this work. The Collecting medians heuristic uses two dual information to build primal solutions: the auxiliary costs and the selection of medians which is composed independent clusters in a dual solution. By doing so, it somehow avoids the transfer of indecisions from a dual to a primal solution. Computational results show that the Collecting medians outperforms the Classic LH. Additionally, variables fixing tests are used to reduce the size of the problems. In general, the amount of reductions is very significant. For the TSP-LIB instances, millions of arcs are eliminated (on average, 90% of arcs are eliminated). Moreover, it is also shown, the reduction tests start to work and to be more efficient when the gaps are within 5%. This is important because it avoids applying the reduction tests at every subgradient iteration, and consequently time is saved. Furthermore, two local search procedures are also used to improve the Collecting medians heuristic. Consequently, optimality is proved for difficult instances using the complete version of the Collecting medians and Cplex solver.

Collecting medians

Cplex

A simple idea is used here to improve the lower and the upper bounds qualities. It reinforces the fact that it is well worth using the problem characteristics to improve primal and dual solutions. As a future work, the Lagrangean relaxation can be used as a base for a more sophisticated algorithm such as a branch-and-bound tree or a relax-and-cut algorithm [START_REF] Escudero | A Lagrangean relax-and-cut approach for the sequential ordering problem with precedence relationships[END_REF][START_REF] Lucena | Non delay relax-and-cut algorithms[END_REF]. Another possibility is to use the Collecting medians heuristic as a preprocessing phase since it strongly reduces the size of the problems. Moreover, characteristics of the difficult core for the TSP-LIB instances could be also investigated.

  illustrates a feasible solution S for a graph with |V | = 25, p = 3, and a total cost equal to 546.

Figure 1 :

 1 Figure 1: Example of a solution with three clusters.

Figure 2 :

 2 Figure 2: Example of violations in a dual solution.

  22 and f 12 , and it has a direct connection with the median 12. The first step to select the medians takes O(p • |V |) in the worst case. The additional step consumes up to O(|V |) time in the worst case. Connecting the remaining nodes still remains O(p • |V |). Thus, the Collecting medians worst case complexity is O(p • |V |).

Figure 3 :

 3 Figure 3: Example of the optimizing cluster local search move.

Table 1 :

 1 Comparative results between the Classic LH and the Collecting medians for the OR-Library instances. the relative gap (GAP) (computed as (100 • (UB -LB)/LB)), and the time in seconds (time) are presented.The Collecting medians performs better than the Classic LH, closing gaps or reducing them. Results obtained by the Collecting medians are particularly promising because neither local search or reduction tests are used in this experiment. Results for the complete version of the Collecting medians heuristic is given later in this paper.

	Classic LH	Collecting medians

Table 2 :

 2 Then, S k is submitted to the optimizing cluster local Calibration results for the variable fixing phase using the OR-LIB instances.search procedure. The swap local search is run whenever an upper bound is better than the best upper bound found so far, or when 10 iterations is performed without improving the best upper bound known. Finally, the reduction tests are applied when the gap falls down 5%. 1000 iterations of the subgradient method are performed. After running 1000 iterations, if at least 10% of the current variables are fixed, data structures are cleaned and new subgradient iterations are authorized.

		|A|	p Iteration	LB	UB	GAP
	pmed32		10	158 9226 9422 2.12%
	pmed33 pmed34	700 489,300	70 140	223 4694 4753 1.26% 137 2985 3060 2.51%
	pmed35		5	105 10160 10538 3.72%
	pmed36	800 639,200	10	154 9764 10012 2.54%
	pmed37		80	162 5042 5089 0.93%
	pmed38		5	103 10723 11170 4.17%
	pmed39	900 809,100	10	156 9311 9480 1.82%
	pmed40		90	204 5119 5164 0.88%

Table 3 :

 3 Variables fixing results for the TSP-LIB instances.

		% fixed
	nodes	arcs

Table 4 :

 4 Results for the complete version of the Collecting medians for the TSP-LIB instances.

	Instances p	O *	LB	UB	GAP	time (s) GAP final	+time (s)
		100	491,639	491,496	491,664 0.034	270 0.00	1.63
	rl1304	300	177,326	177,318	177,326 0.005	423 0.00	0.01
		500	97,024	97,018	97,024 0.006	557 0.00	0.03
		100	15,962	15,960	15,970 0.063	323 0.00	3.55
	fl1400	200	8,806	8,791	8,846 0.626	520 0.00 3,293.44
		500	3,764	3,756	3,766 0.266	433 0.15 13,195.05
		50	362,072	361,597	362,427 0.230	378 0.00 2,601.75
	u1432	100	243,793	243,719	243,821 0.042	347 0.00	3.20
		200	159,887	159,838	159,934 0.060	370 0.00	11.69
		10 2,983,645 2,981,277 2,983,645 0.079	388 0.00	192.76
	vm1748	20 1,899,680 1,897,839 1,899,680 0.097	505 0.00	124.72
		50 1,004,331 1,004,203 1,004,331 0.013	507 0.00	0.95
		100 unknown	193,793	195,511 0.887 1364	-	-
	d2103	200	117,753	117,727	117,985 0.219 1361 0.00	78.14
		300	90,471	90,267	90,752 0.537 1393 0.00	443.95
		200	237,399	237,276	237,540 0.111 2558 0.00	448.36
	pcb3038	400	156,276	156,267	156,281 0.009 2483 0.00	7.58
		500	134,798	134,774	134,817 0.032 2697 0.00	59.08
		200	53,928	53,866	54,041 0.325 4754	-	-
	fl3795	300	39,586	39,570	39,611 0.104 5245 0.00 11,602.83
		400	31,354	31,331	31,452 0.386 6294	-	-