Dynamic programming analysis of the tv game Who Wants to Be a Millionaire?

UNCORRECTED PROOF DAM: 7027 Model 3G pp. 1–19 (col. fig: nil) ARTICLE IN PRESS Discrete Applied Mathematics xx (xxxx) xxx–xxx Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam A flexible model and efficient solution strategies for discrete location problems Alfredo Marína, Stefan Nickelb,∗, Justo Puertoc, Sebastian Veltenb aUniversidad de Murcia, Departamento de Estadística e Investigación Operativa, 30100 Murcia, Spain bSaarland University, Faculty of Law and Economics, P.O. Box 15 11 50, 66041 Saarbrücken, Germany cUniversity of Seville, Faculty of Mathematics, 41012 Seville, Spain article info Article history: Received 5 April 2007 Received in revised form 27 February 2008 Accepted 9 March 2008 Available online xxxx Keywords: Discrete location Discrete ordered median problem Valid inequalities Variable fixing abstract Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers. In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported. © 2008 Published by Elsevier B.V. 1. Introduction 1 Location Analysis is one of the most active fields in Operations Research. Especially, discrete location problems have been 2 widely studied due to their importance in practical applications and also due to their interesting structural properties (see for 3 example [1–3] and references therein). Discrete location problems typically involve a finite set of sites at which facilities can 4 be located, and a finite set of clients, whose demands for service or goods have to be fulfilled by these facilities. The simplest 5 and well studied discrete location problems are the discrete p-Median Problem and the Uncapacitated (and Capacitated) 6 Facility Location Problem (see [4,5]). Evidently many extensions of these basic location problems have been developed. The 7 extensions range from capacity restrictions, over multi-echelon structures (see [6]), to time dynamic models and models 8 with choice of facilities (see [7]). Recently several articles have been published addressing strategic supply chain decisions 9 in the context of location problems (see [8] and references therein). This development led to a highly flexible and general 10 framework of location models in terms of side constraints. 11 Another important aspect of a location model is the right choice of the objective function, and in most classical location 12 models the objective function is the main differentiator. Therefore, a great variety of objective functions has been considered. 13 The median objective is to minimize the sum of the costs of fulfilling all demand requests from clients. The center objective 14 is to minimize the maximum cost of fulfilling the demand of a client, from amongst the sites chosen, over all clients. The 15 centdian objective is a convex combination of median and center objectives; it aims to keep both the average cost behavior 16 as well as the highest cost in balance. Despite the fact that all three objectives (and some more) are frequently encountered 17 in the literature (see for example [1,2]), not much has been done in the direction of a unified framework for handling all 18 these objectives. 19 ∗Corresponding author. Tel.: +49 0 681 302 64738; fax: +49 0 681 302 64737. E-mail addresses: [email protected] (A. Marín), [email protected] (S. Nickel), [email protected] (J. Puerto), s.velt[email protected] (S. Velten). 0166-218X/$ – see front matter © 2008 Published by Elsevier B.V. doi:10.1016/j.dam.2008.03.013 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 2A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx The increasing need for discrete location models in strategic supply chain planning, see for example [8], has made it1 necessary to develop new and flexible location models. To that end, [9] introduced a new type of objective function which2 generalizes the most popular objective functions mentioned above. This objective function applies a penalty to the cost of3 fulfilling the demand of a client which is dependent on the position of that cost relative to the costs of supplying other4 customers. For example, a different penalty might be applied if the cost of supplying the client was the 5th-most expensive5 cost rather than the 2nd-most expensive. It is even possible to neglect some customers by assigning a zero penalty. This adds6 a “sorting”-problem to the underlying facility location problem, making formulation and solution much more challenging.7 For planar and network location problems the generalized model was studied in [10–12]. The research in this area even8 led to a recent monograph, see [13]. In [9], a formulation of the discrete case, later called the Discrete Ordered Median9 Problem, is discussed. Starting with a nonlinear formulation, several linearizations were developed. Structural results as10 well as a specially tailored branch and bound procedure are presented in [14]. Moreover, modeling and solution approaches11 for special cases in which the objective can be represented as a sum of k-centrum objectives are given in [15].12 However, none of these approaches leads to satisfactory results concerning solution times of even medium size instances.13 Therefore, we provide a different formulation which is based in part on the idea of sorting radii already used in [16] (see14 also [17]) and, recently, by [18] for modeling the p-center problem. This new formulation will be the basis of our specialized15 branch & cut approach. In this context, we use a heuristic approach developed in [19], to get good upper bounds. This heuristic16 is based on Variable Neighborhood Search, first introduced in [23], and by employing this heuristic, high quality heuristic17 solutions for up to 900 possible locations can be obtained.18 The rest of the paper is organized as follows. First we will recall the Discrete Ordered Median Problem formally and give19 a new mathematical programming formulation. In Section 3we strengthen the initial formulation by using variable fixing20 and by adding valid inequalities. These results are put together in Section 4to get a specialized Branch & Cut approach. In21 Section 5we will show the efficiency of the described approach by reporting on extensive numerical experiments. The paper22 ends with some conclusions and an outlook to future research.23 2. The discrete ordered median problem24 In order to introduce the Discrete Ordered Median Problem (DOMP) formally, we define a set Vof Mdiscrete locations.25 These locations represent clients as well as potential plant locations.26 Moreover, let C=(cij)(i,j=1,...,M) be a non-negative M×Mcost matrix, where cij denotes the cost of satisfying27 the total demand of client ifrom a plant at location j. Thereby, we assume that cii =0 (∀i=1,...,M). This property of C28 is called free self-service (FSS) and will be needed for some of the subsequent results. For i6= jwe assume cij >0. 29 Let Nwith 1 ≤N≤M−1 be the number of new plants which have to be located at the candidate sites. Then the costs30 for satisfying the demand of the respective clients, given a feasible solution X⊂Vwith |X| = N, can be represented by the31 following vector32 c(X):= (c1(X), . . . , cM(X)) with ci(X)=min j∈X{cij} ∀ i∈V.33 However, due to the desired flexibility, c(X)cannot directly be used to define the objective function of the DOMP. Instead,34 consider a permutation σXon {1,...,M}for which the inequalities35 cσX(1)(X)≤cσX(2)(X)≤ · · · ≤ cσX(M)(X)36 hold. Using this permutation we define the sorted cost vector c≤(X)corresponding to a feasible solution Xas follows:37 c≤(X):= (cσX(1)(X), . . . , cσX(M)(X))38 or for short39 c≤(X):= (c(1)(X), . . . , c(M)(X)).40 Furthermore, let λ=(λ1,...,λM)be an M-dimensional vector, with λi≥0 (∀i=1,...,M) representing a weight on41 the i-th lowest component of the cost vector c(X). With respect to these assumptions the DOMP is defined as:42 min X⊂V |X|=N fλ(X), (1)43 with44 fλ(X)= M X i=1 c(i)(X)·λi.(2)45 The function fλ(X)is called ordered median function (omf). An example illustrating the structure of the DOMP and the46 calculation of the ordered median function is given below.47 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 3 Table 1 Modeling possibilities λfλ(X)Meaning (1,...,1)PM i=1ci(X)N-median (0,...,0,1)max1≤i≤Mci(X)N-center (α,...,α,1)α∈ [0,1]α·PM i=1ci(X)+(1−α)·max1≤i≤Mci(X)α-centdian (0,...,0,1,...,1 | {z } k )PM i=M−k+1c(i)(X)k-centrum Example 1. Let V= {1,...,5}and assume that N=2 plants have to be located. Moreover, let the cost matrix Cbe as 1 follows: 2 C=    06548 4 0 8 5 7 6 2 0 8 5 6 5 4 0 1 55260    .3 With λ=(2,0,1,1,0), the unique optimal solution of this problem instance is X= {2,5}. Therefore, the demands 4 of locations 1 and 3 are satisfied by plant 2 whereas the demand of location 4 is satisfied by plant 5. Hence, c≤(X)=5 (0,0,1,2,6)and 6 fλ(X)=0·2+0·0+1·1+2·1+6·0=3.7 Note that by using appropriate values for λ, nearly all classical discrete facility location problems can be modeled by 8 the above definition. In addition, a wide range of new and interesting problems can be derived. Some of these modeling 9 possibilities are given in Table 1. For a more extensive list the interested reader is referred to [13,20]. 10 Since the DOMP contains the discrete N-median problem, which is N P -hard (see [21]), as a special instance, the DOMP 11 is N P -hard, too. Moreover, due to the sorting process in the objective function, the above formulation of the DOMP is non- 12 linear. But different formulations have also been proposed which are quadratic (see [9]) or even linear (see [9] and [14]). 13 Nevertheless, none of these approaches provides satisfactory results concerning solution times for large problem instances. 14 Therefore, we will develop a different formulation for the DOMP which is based in part on the idea of [18] for modeling the 15 N-center problem. 16 In order to introduce this new formulation we first define Gas the number of different non-zero elements of the cost 17 matrix C. Hence, we can order different values of Cin increasing sequence: 18 c(0):= 0<c(1)<c(2)<· · · <c(G):= max 1≤i,j≤M{cij}.19 Given a feasible solution (i.e. X⊂V,|X| = N) we can use this ordering to perform a sorting process of allocation costs. 20 Thereby, we omit allocation costs of plant locations, because they are equal to zero anyway. Consequently, we only have to 21 sort M−Ncost elements. This can be done by the following variables (j=1,...,M−Nand k=1,...,G): 22 xjk := 1 if the j-th smallest allocation cost is at least c(k), 0 otherwise. (3) 23 With respect to this definition the j-th smallest cost element is equal to c(k)if and only if xjk =1 and xj,k+1=0. Using 24 these variables the ordered median function can be reformulated as follows: 25 Let Xbe feasible solution, i.e. |X| = N. Then, for j=1,...,N,C(j)(X)=0 because of free self service. On the other hand, 26 if i∈ {N+1,...,M}, there exists a 1 ≤k0≤Gso that C(j)(X)=c(k0). Therefore, by choosing values for the xjk-variables 27 according to their definitions, it holds: 28 xjk =1∀k=1,...,k0and xjk =0∀k=k0+1,...,G29 Hence, by using a telescopic sum, we get 30 C(j)(X)= G X k=1c(k)−c(k−1)·xjk 31 and the ordered median function can be written as: 32 fλ= M X j=1 λj·C(j)(X)= M−N X j=1 G X k=1 λN+j·(c(k)−c(k−1))·xjk.(4) 33 The role of xjk-variables in the sorting process is further demonstrated by the following example. 34 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 4A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx Example 2. We consider the same problem instance as in Example 1. Then, since the sorted cost vector of matrix Cis1 (0,1,2,4,5,6,7,8), the values of the xjk-variables corresponding to the optimal solution X= {2,5}are given by:2 x11 =1;x12 =x13 =x14 =x15 =x16 =x17 =0(location 4)3 x21 =1;x22 =1;x23 =x24 =x25 =x26 =x27 =0(location 3)4 x31 =1;x32 =1;x33 =1;x34 =1;x35 =1;x36 =x37 =0(location 1).5 Furthermore, the objective function value can be calculated by6 M−N X j=1 G X k=1 λN+j·(c(k)−c(k−1))·xjk =λ3·(x11 +x12 +2·x13 +x14 +x15 +x16 +x17)7 +λ4·(x21 +x22 +2·x23 +x24 +x25 +x26 +x27)8 +λ5·(x31 +x32 +2·x33 +x34 +x35 +x36 +x37)9 =1·1+1·(1+1)+0·(1+1+2+1+1)=3.10 Next, we are interested in variables reflecting the location decisions of a feasible solution X. In this regard we define for11 each row i(i=1,...,M) of the cost matrix C,Gias the number of different non-zero elements in this row. Thus, we obtain,12 as for the whole matrix C, the ordering13 ci (0):= 0<ci (1)<· · · <ci (Gi):= max j=1,...,M{cij}14 of the cost elements of row i. Then we can define the following variables (i=1,...,Mand k=1,...,Gi):15 zik := 1 if the allocation cost for location iis at least ci (k), 0 otherwise. (5)16 In addition, for convenience we define ziGi+1:= 0, for all i=1,...,M. These definitions imply that, if zik =1, no plants17 are established at locations jwith cij <ci (k). Moreover, notice that a plant is opened at location iif and only if zik =0 for all18 k=1,...,Giwhich is due to the fact that the allocation cost of a plant is equal to zero. An example illustrating the meaning19 of these variables is given below.20 Example 3. We reconsider the data of Example 1 and recall that X= {2,5}is the optimal solution. Furthermore, consider21 the first row in matrix C(i.e. (0 6 5 4 8)). Then the variables z11,z12,z13 and z14 are associated with the sorted non-zero22 entries 4, 5, 6 and 8, and they assume, with respect to the optimal solution, the values23 z11 =1,z12 =1,z13 =1,z14 =0,24 since location 1 is allocated to the plant at location 2 with a cost of 6. On the other hand, the variables z51,z52 and z53 are25 all equal to 0, because there is a plant at location 5.26 From the definition of zik it follows that a plant is opened at location iif and only if zi1=0, which is equivalent to the27 condition 1 −zi1=1. Furthermore, one can observe that zik −zik+1=1 if and only if the client at location iis allocated28 to an open plant at cost ci (k). Hence, we can write the cost for allocating a client at location ito a plant, like in the objective29 function, as30 Gi X k=1 (ci (k)−ci (k−1))·zik = Gi−1 X k=1 ci (k)·(zik −zik+1). (6) 31 Therefore, the location and allocation decisions can be totally modeled by these variables whereas the following32 constraints ensure that only correct values will be assumed:33 zik ≥1−X j=1,...,M cij<ci (k) (1−zj1)∀i=1,...,M,k=2,...,Gi.(7)34 That these constraints indeed accomplish the desired task can be seen as follows. On the one hand, if no plant can be35 reached by customer iat a cost less than ci (k)then the constraint for pair (i,k)becomes zik ≥1. On the other hand, if a plant36 can be reached at a cost less than ci (k)then it holds37 X j=1,...,M cij<ci (k) (1−zj1)≥1,38 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 5 Fig. 1. Relationship between z- and x-variables. and for (i,k)the constraint is redundant. Nonetheless, we still need to guarantee that exactly Nplants will be opened among 1 the Mpossibilities. This can be ensured by the constraint 2 M X i=1 zi1=M−N(8) 3 since zi1=0 if and only if there is a plant at location i.4 Up to now we have defined two kinds of variables where, for a feasible solution, the xjk can be used to sort allocation 5 costs and the zik are capable of modeling the location and allocation decisions. However, to obtain the new formulation of 6 the DOMP we need to link these variables. This can be done by enforcing the number of locations with allocation costs at 7 least c(k), once represented by xjk- and once by zik-variables, to be equal: 8 M−N X j=1 xjk =X i=1,...,M li k≤Gi zili k ∀k=1,...,G(9) 9 where 10 li k:= min{s:ci (s)≥c(k)}if c(k)≤ci (Gi), Gi+1 otherwise.(10) 11 Observe that these constraints ensure that if zili k0=1 then, given the definition of xjk-variables, there exists at least one j12 so that xjk =1 for all kwith c(k)≤ci (k0). Because of this, it is guaranteed that xjk-variables take the correct values, according 13 to the location and allocation decision induced by zik-variables, even if cost elements are missing in the respective rows. 14 Therefore, values of xjk-variables always represent sorted costs corresponding to the location and allocation decision of 15 a solution. Furthermore, by using (4) as objective, the ordered median function is minimized. 16 The relationship between these variables is illustrated by the following example: 17 Example 4. Given again the problem data of Example 1, the graphic provided in Fig. 1 demonstrates how the z- and x-18 variables are linked to each another. Thereby, values for the optimal solution X= {2,5}have been used. 19 At last, to complete the new formulation of the DOMP, we need to impose the following group of sorting constraints on 20 the xjk-variables: 21 xjk ≥xj−1kj=2,...,M−N;k=1,...,G.(11) 22 Summarizing the constraints (7)–(9) and (11) and the objective function (4), the DOMP can be formulated as 23 (DOMP)24 Min M−N X j=1 G X k=1 λN+j·(c(k)−c(k−1))·xjk (4) 25 s.t. zik ≥1−X j=1,...,M cij<ci (k) (1−zj1)i=1,...,M;k=2,...,Gi(7) 26 M X i=1 zi1=M−N(8) 27 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 6A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx M−N X j=1 xjk =X i=1,...,M li k≤Gi zili k k=1,...,G(9)1 xjk ≥xj−1kj=2,...,M−N;k=1,...,G(11)2 xjk ∈ {0,1}j=1,...,M−N;k=1,...,G(12)3 zik ∈ {0,1}i=1,...,M;k=1,...,Gi.(13)4 Remark 1. Note that there may be feasible, and even optimal, solutions for the model (DOMP)which, by definition, are not5 feasible for the problem. For example, in the case of some λ-values being 0, a zik-variable may be equal to 1 even if zik0,6 k0<k, is already equal to 0. However, for each of these solutions a feasible solution for the problem can be derived easily7 by allocating locations according to location decisions, i.e. the values of the zi1-variables.8 Since the proposed formulation contains O(M3)binary variables and O(M3)constraints, fast solution times for large9 problem instances, using standard software-tools, are very unlikely (see Section 5. Therefore, we propose a specialized branch10 & cut procedure and several variable fixing strategies, exploiting the special structure of the presented model.11 Remark 2. With respect to the definition of the xjk- and zik-variables there are two more groups of sorting constraints which12 have to be satisfied. Namely,13 •If the j-th smallest positive allocation cost is at least c(k), it is also at least c(k−1):14 xjk−1≥xjk j=1,...,M−N;k=2,...,G(14)15 •If the allocation cost of location iis at least ci (k), it is also at least ci (k−1):16 zik−1≥zik i=1,...,M;k=2,...,Gi.(15)17 If the model given by (DOMP)is optimized, these constraints are fulfilled automatically. However, they are needed for18 some of the variables fixing strategies detailed in the next section.19 3. Variable fixing and valid inequalities20 In this section we describe a number of variable fixing possibilities which are useful in the overall solution process. More-21 over, a group of valid inequalities is introduced which leads to a specialized branch & cut procedure for solving the DOMP.22 First of all, the following proposition states that we only need to enforce zi1-variables (i=1,...,M) to be binary:23 Proposition 1. In (DOMP),zik ∈ {0,1}can be replaced by 0≤zik ≤1for i=1,...,Mand k=2,...,Gi, since each optimal24 solution of the relaxed problem leads to an optimal solution of the original problem, too.25 Proof. Let (˜x,˜z)be an optimal solution of (DOMP)with zik ∈ {0,1}replaced by 0 ≤zik ≤1 for i=1,...,Mand26 k=2,...,Gi. If all variables in (˜x,˜z)are binary, we are done. Otherwise, there are at least two pairs of indices (i0,k0)and27 (i00,k00)(i0,i00 ∈ {1,...,M}and k0,k00 ∈ {2,...,Gi}) so that 0 <˜zi0k0,˜zi00k00 <1. This is because of the Constraints (9)28 and all ˜xjk-variables being binary. Moreover, for these variables the Constraints (7) reduce zi0k0≥0, since zi1∈ {0,1}29 (i=1,...,M). Hence, fractional variables can be changed to 0 without violating these constraints. However, in order to30 maintain feasibility, some of the ˜xjk-variables have to be reduced to 0 as well. But obviously, this can be done without violating31 any constraints and without increasing the objective function value, because λN+j·(c(k)−c(k−1))(j=1,...,M−Nand32 k=1,...,G) is always greater than or equal to 0. Therefore, we obtain a new solution which is feasible, optimal and fulfills33 all binary constraints. 34 Furthermore, some of the x- and z-variables can be fixed to 0 or 1 in a preprocessing step. For some of these variable fixing35 strategies an upper bound on the optimal objective value is needed, which can be obtained, for example, by the Variable36 Neighborhood Search (VNS) presented in [13,19].37 3.1. Fixing xjk-variables to 138 Following the definition of the xjk-variables, we first observe that xj1=1 for j=1,...,M−N. This is true because if a39 location has to be allocated, the corresponding cost is at least c(1)(i.e. the smallest positive element in C). Now assume, for40 fixed jand kwith 1 ≤j≤M−Nand 2 ≤k≤G, that xjk =0. Moreover, we define a set Las follows:41 L:= ni∈ {1,...,M} : li k=1o.42 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 7 Then, a solution with xjk =0 can only be feasible if it holds: 1 M−N−j≥ M−N X j0=1 xj0k=X i=1,...,M li k≤Gi zili k ≥ |L| − N.(16) 2 Thereby, the first inequality is due to the definition of the xjk-variables: 3 xjk =0⇒xj0k=0∀j0≤j.4 Therefore, at most M−N−jxj0k-variables can be equal to 1 if xjk =0. In addition, the second inequality follows from the 5 fact that |L|is the number of locations the smallest allocation costs of which are at least c(k). Hence, in a feasible solution, 6 the number of locations which are allocated with costs at least c(k)has to be at least |L| − N, since at Nlocations a facility 7 could be opened. At last, the equation in the middle follows from (9).8 Consequently, if (16) does not hold (i.e. M−j<|L|), a solution with xjk =0 can never be feasible. Thus, in this case, xjk 9 has to be equal to 1. 10 Using this test, each xjk-variable can be checked, whether it has to be equal to 1 or not. However, not all combinations of 11 jand kneed to be tested as indicated by the subsequent remark. 12 Remark 1. If xjk has been fixed to 1 (applying the test of this subsection), then xj0k0=1 for j0=j+1,...,M−Nand 13 k0=1,...,k−1, too. This follows directly from the definition of the xjk-variables. 14 3.2. Fixing xjk-variables to 0 15 In order to derive a test for fixing some of the xjk-variables to 0, we first assume that xjk =1 (for some fixed j16 (1 ≤j≤M−N) and k(1 ≤k≤G)). On the one hand, this means that the j-th smallest allocation cost is at least 17 equal to c(k). Therefore, the (j+1)-th to (M−N)-th smallest allocation costs are also at least c(k), and hence, xj0k=1 for 18 j0=j+1,...,M−N. On the other hand we know that xj01=1 for all j0=1,...,j−1 (see Section 3.1). Given this 19 information, it is easy to see that the following expression provides a lower bound on the optimal objective value for the 20 case where xjk =1: 21 c(1)· j−1 X l=N+1 λl! | {z } (∗) +c(k)·  M−N X l=j λl  | {z } (∗∗) .(17) 22 (∗)The 1-st to (j−1)-th smallest allocation costs are at least c(1).23 (∗∗)The j-th to (M−N)-th smallest allocation costs are at least c(k).24 This lower bound can now be compared to the upper bound mentioned above or another heuristic. Then, if the lower bound 25 for the case xjk =1 is greater than the upper bound, a solution with xjk =1 can never be optimal. Thus, xjk can be 26 fixed to 0 without losing any optimal solution. Moreover, by the following remark, this test needs not to be executed for 27 all combinations of jand k.28 Remark 2. If xjk has been fixed to 0 (applying the test of this subsection), then xj0k0=0 for j0=1,...,jand k0=k,...,G,29 too. This follows directly from the definition of the xjk-variables. 30 3.3. Fixing zik-variables to 0 31 As in the previous section, assume that zik =1 for some fixed 1 ≤i≤Mand 1 ≤k≤Gi. Then we know, for an associated 32 feasible solution, that no plant (including plant i) is opened within cost radius ci (k−1)around location i. Otherwise, location i33 would be allocated to such a plant and zik would be equal to 0. Consequently, facilities can only be opened at locations lying 34 outside this cost radius. This set of locations we denote by W(see Fig. 2). 35 If now, on the one hand, the cardinality of Wis less than N, it is easy to observe that a solution with zik =1 can never 36 be feasible, since exactly Nfacilities have to be located. Moreover, if on the other hand the cardinality of Wis greater than 37 or equal to N, we can again derive a lower bound on the optimal objective value for the case zik =1. For that purpose we 38 define a cost vector ˜c(W)=(˜c1(W), . . . , ˜cM(W)) in the following way: 39 ˜ci0(W)=   min j∈W\{i0} {ci0j}if i0∈W min j∈W{ci0j}otherwise. (18) 40 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 8A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx Fig. 2. Illustration of cost radius ci (k−1)around location i. This cost vector contains, for each i0∈V, the smallest cost for allocating location i0to a possible plant in W(which is not1 i0itself). If we now change the Nlargest entries of this vector to 0 (i.e. we assume a plant is located there), ˜c(W)contains2 only the costs which have at least to be paid if zik =1. Therefore, the scalar product <λ,˜c≤(W)>, whereas ˜c≤(W)is3 equal to ˜c(W)with elements sorted in non-decreasing sequence, provides a lower bound for the case zik =1. Hence, this4 lower bound can be compared to a given upper bound and in case it is greater zik has to be equal to 0 in any optimal solution.5 However, this test has again not to be performed for all iand j:6 Remark 3. If zik has been fixed to 0 (applying the test of this subsection), then zik0=0 for k0=k,...,Gi, too. This follows7 directly from the definition of the zik-variables.8 3.4. Valid Inequalities9 In designing the specialized branch & cut procedure for the new formulation of the DOMP, the following family of10 inequalities turned out to be very useful. The subsequent proposition proves that they are valid for the proposed formulation.11 |A| X j=1 x(M−N+1−j)k≥X i∈A li k≤Gi zi li k ∀A⊂V,|A| ≤ M−N;k=2,...,G.(19)12 Proposition 2. The family of inequalities (19) is valid for the formulation of the DOMP given in Section 2, i.e. they are fulfilled for13 all feasible solutions.14 Proof. Let (˜x,˜z)be a feasible solution for the formulation of the DOMP given in Section 2. Moreover, let A⊂Vwith15 |A| ≤ M−Nand k=2,...,Gbe arbitrarily chosen. Then by (11) it holds:16 |A| X j=1 ˜x(M−N+1−j)k=min (|A|, M−N X j=1 ˜xj k). 17 On the other hand, we know by (9) and 0 ≤ ˜zik ≤1 that18 X i∈A li k≤Gi ˜zi li k ≤ M−N X j=1 ˜xj k and X i∈A li k≤Gi ˜zi li k ≤ |A|.19 Thus,20 |A| X j=1 ˜x(M−N+1−j)k≥X i∈A li k≤Gi ˜zi li k .21 Furthermore, apart from being valid for the proposed formulation, the inequalities (19) can be used to replace binary22 restrictions on xjk-variables. This statement is proved by the following proposition.23 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 9 Proposition 3. If a feasible solution satisfies zik ∈ {0,1}for all i=1,...,Mand k=1,...,Gi, then the family of Valid 1 Inequalities (19) enforces xjk to be binary for all j=1,...,M−Nand k=1,...,Gas well. 2 Proof. Let (˜x,˜z)be feasible for (7)–(11),zik ∈ {0,1}for all i=1,...,Mand k=1,...,Gi. Take k0, 1 ≤k0≤G, arbitrary 3 but fixed. Moreover, let 4 X i=1,...,M li k0≤Gi zi li k0=q∈Z+ 0.5 Then, if q=0, Constraints (9) imply xjk =0 for all j=1,...,M−N. Otherwise, if q=1, the Valid Inequalities (19) 6 imply (with |A| = 1) that 7 ˜xM−N k0≥max i=1,...,M{˜zili k0} = 1,8 and thus ˜xM−N k0=1. Furthermore, if q>1, again the Valid Inequalities (19) imply (with |A| = 2) that 9 ˜xM−N k0+ ˜xM−N−1k0≥max i,r=1,...,M{˜zili k0+ ˜zrlr k0} = 2,10 which yields ˜xM−N−1k0=1. Repeating the same argument one can observe that ˜xM−N−2k0to ˜xM−N−(q−1)k0have also to 11 be equal to 1. At last, by Constraints (9),˜xN−M−q k0to ˜x1k0have to be equal to 0, which completes the proof. 12 Given Propositions 1 and 3, the DOMP can be formulated as a mixed-integer linear program with only Mbinary variables 13 (zi1for all i=1,...,M). However, as the family of Valid Inequalities (19) is exponential in size, a solution, using standard 14 software-tools, seems not to be appropriate. Therefore, the next section is dedicated to a specialized branch & cut procedure, 15 which applies the valid inequalities dynamically whenever they are violated. 16 4. Specialized branch & cut 17 As already explained in the previous section, a solution for the presented model of DOMP can be found using a branch & 18 cut procedure with only Mbinary variables, whereas Valid Inequalities (19) are added whenever they are needed. Thereby, 19 the solution of a subproblem of the branching tree can be obtained as follows: 20 (1) Solve the LP-relaxation. 21 (2) Add, for each 2 ≤k≤G, all (or some) violated cuts of type (19) (if there are any). If some cuts have been added, goto 22 Step 1. 23 However, because of the exponential size of (19), adding all violated cuts in each iteration proved to be inefficient. Therefore, 24 only cuts of a specific type have been tested and, if violated, added. 25 Let 2 ≤k≤Gand ˜xand ˜zbe the solution of the linear relaxation of a node in the branching tree. Moreover, let j0be 26 the largest index so that ˜xj0k=0 and let j1be the smallest index so that ˜xj1k=1. In addition, let ˜z≥ lkbe the vector of ˜zili k 27 variables with li k≤Giand sorted in non-increasing order. Then, for each j0+2≤j∗<j1with M−N−(j∗−1)being less 28 than or equal to the number of elements in ˜z≥ lk, the following cut has been tested: 29 M−N X j=j∗ xjk ≥ M−N−(j∗−1) X i=1z≥ lki.(20) 30 Note that these cuts are maximal in some sense, since if they are not violated, no valid inequality of type (19) with 31 |A| = M−N−(j∗−1)is violated. Hence, by Proposition 3, we only need to test them in order to skip binary restrictions on 32 x-variables. Thus, the specialized branch & cut procedure for solving the proposed model of the DOMP is given in Algorithm 1. 33 However, the number of cuts which have to be checked in order to omit binary restrictions on x-variables can even be 34 further reduced. Observe that if for some 2 ≤k≤Gnot all ˜xjk-variables are binary, ˜x(j0+1)khas to have a fractional value 35 and, if ˜z≥ lkis binary (which will be the case at some point in the branching tree), cut (20) for j∗=j0+2 is violated. Therefore, 36 only these valid inequalities need to be tested and, furthermore, the test is only necessary if all z-variables are binary. 37 As can be seen from this discussion, we need, on the one hand, only some cuts of type (20) to replace binary constraints on 38 the x-variables. This leads to relatively small linear programs in each iteration. On the other hand, adding all cuts of type (20) 39 leads to better lower bounds in each node. On this account we tested three different cutting strategies (see Section 5.2): 40 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 16 A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx Table 12 Complete results (M=30) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 30 T1 3 0.16 / 0.52 0.18 / 1.01 0.19 / 1.64 0.04 0.20 9 472 0.11 8 0.55 / 0.61 0.66 / 0.79 0.75 / 1.19 0.00 0.02 21 478 0.08 M/3 0.75 / 0.77 0.92 / 0.96 1.09 / 1.11 0.00 0.02 4 516 0.04 T2 3 0.13 / 1.14 0.16 / 1.73 0.19 / 3.09 0.05 0.16 12 374 0.59 8 0.41 / 0.69 0.57 / 1.83 0.81 / 5.39 0.01 0.04 65 1 418 0.47 M/3 0.61 / 1.47 0.94 / 2.62 1.56 / 5.38 0.03 0.11 26 2 194 0.40 T3 3 0.19 / 3.95 0.19 / 25.08 0.22 / 44.53 0.01 0.07 112 12 904 0.55 8 0.50 / 1.00 0.59 / 3.69 0.69 / 8.83 0.02 0.08 116 3 126 0.36 M/3 0.73 / 1.00 1.02 / 2.39 1.27 / 6.61 0.00 0.00 16 1 835 0.26 T4 3 0.17 / 0.97 0.18 / 1.30 0.19 / 2.00 0.02 0.09 25 2 783 0.22 8 0.61 / 0.77 0.68 / 0.95 0.80 / 1.22 0.00 0.00 29 759 0.13 M/3 0.81 / 0.97 1.07 / 1.40 1.27 / 1.92 0.00 0.00 9 737 0.11 T5 3 0.19 / 0.89 0.20 / 2.47 0.22 / 4.33 0.00 0.00 14 983 0.15 8 0.58 / 0.98 0.80 / 1.56 1.00 / 2.86 0.00 0.00 34 593 0.12 M/3 0.80 / 1.08 0.98 / 1.62 1.09 / 2.89 0.01 0.02 27 727 0.09 T6 3 0.17 / 1.05 0.18 / 2.76 0.19 / 4.11 0.03 0.17 14 571 0.14 8 0.55 / 1.09 0.68 / 1.88 0.86 / 4.09 0.00 0.02 56 619 0.11 M/3 0.72 / 1.03 0.89 / 2.11 1.20 / 2.92 0.02 0.10 53 939 0.08 T7 3 0.17 / 1.06 0.20 / 2.25 0.22 / 3.55 0.00 0.00 11 464 0.14 8 0.58 / 1.03 0.64 / 1.39 0.72 / 1.97 0.00 0.02 39 635 0.12 M/3 0.75 / 0.95 0.98 / 1.54 1.06 / 2.75 0.00 0.00 29 692 0.08 T8 3 0.19 / 1.83 0.20 / 3.97 0.22 / 8.97 0.00 0.00 18 1 006 0.18 8 0.48 / 1.11 0.57 / 2.86 0.67 / 3.59 0.01 0.03 96 1 751 0.17 M/3 0.77 / 1.67 0.96 / 2.97 1.27 / 6.22 0.01 0.03 77 1 981 0.13 T9 3 0.16 / 0.84 0.18 / 1.07 0.20 / 1.53 0.00 0.00 6 243 0.11 8 0.56 / 0.63 0.70 / 0.82 0.91 / 1.00 0.00 0.00 21 364 0.06 M/3 0.78 / 0.83 1.08 / 1.12 1.67 / 1.69 0.00 0.00 16 404 0.03 T10 3 0.17 / 3.69 0.19 / 8.27 0.20 / 15.02 0.00 0.00 32 1 918 0.27 8 0.53 / 1.11 0.57 / 3.49 0.59 / 5.69 0.02 0.10 75 2 282 0.22 M/3 0.75 / 1.11 0.89 / 3.97 1.05 / 14.20 0.00 0.00 16 2 196 0.17 Table 13 Complete results (M=40) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 40 T1 3 0.41 / 4.84 0.44 / 7.75 0.48 / 10.94 0.01 0.03 28 1 435 0.21 8 1.34 / 1.67 1.83 / 2.19 2.77 / 3.31 0.01 0.04 48 1 059 0.09 M/3 3.38 / 3.50 4.37 / 4.41 5.61 / 5.64 0.00 0.00 4 445 0.04 T2 3 0.30 / 3.72 0.35 / 11.95 0.44 / 25.17 0.14 0.32 34 1 007 0.64 8 0.95 / 1.41 1.23 / 4.32 2.16 / 9.83 0.08 0.27 93 1 764 0.53 M/3 2.78 / 3.44 3.46 / 5.42 4.83 / 8.16 0.13 0.30 35 2 236 0.42 T3 3 0.42 / 89.23 0.44 / 131.00 0.47 / 163.30 0.00 0.00 234 22 156 0.61 8 1.09 / 9.42 1.42 / 34.98 2.13 / 68.11 0.02 0.05 564 14 690 0.42 M/3 3.58 / 4.03 4.37 / 11.01 5.69 / 30.13 0.00 0.02 44 4 034 0.27 T4 3 0.42 / 7.77 0.43 / 14.25 0.44 / 18.61 0.01 0.05 65 5 632 0.31 8 1.09 / 1.39 1.60 / 4.15 2.69 / 10.67 0.00 0.00 142 3 574 0.17 M/3 3.27 / 3.30 3.82 / 3.99 4.55 / 5.03 0.00 0.00 11 1 029 0.09 T5 3 0.42 / 7.75 0.45 / 15.87 0.48 / 19.47 0.00 0.02 37 1 784 0.24 8 1.30 / 1.95 1.55 / 2.89 1.97 / 3.78 0.00 0.00 52 955 0.11 M/3 3.52 / 3.78 3.99 / 4.88 4.67 / 5.70 0.01 0.02 39 925 0.08 T6 3 0.41 / 6.47 0.46 / 14.61 0.50 / 21.16 0.00 0.02 28 957 0.21 8 1.11 / 4.23 1.28 / 6.18 1.45 / 10.03 0.01 0.06 83 901 0.11 M/3 3.59 / 4.05 3.80 / 4.65 4.03 / 5.55 0.01 0.06 49 681 0.07 T7 3 0.41 / 6.83 0.44 / 13.91 0.45 / 20.91 0.00 0.00 27 710 0.22 8 1.06 / 2.30 1.45 / 3.28 2.02 / 4.88 0.00 0.00 44 475 0.11 M/3 3.59 / 3.80 4.65 / 5.00 5.97 / 6.17 0.00 0.00 23 433 0.06 T8 3 0.44 / 12.91 0.45 / 25.60 0.47 / 36.05 0.00 0.00 47 2 219 0.26 8 1.25 / 5.23 1.73 / 9.20 2.09 / 13.72 0.00 0.02 144 2 030 0.15 M/3 3.41 / 4.47 5.74 / 7.54 8.98 / 11.27 0.01 0.02 76 1 497 0.10 T9 3 0.41 / 11.22 0.43 / 15.78 0.48 / 20.92 0.01 0.07 27 854 0.22 8 1.02 / 1.31 1.40 / 2.86 1.97 / 4.61 0.00 0.00 46 438 0.09 M/3 3.66 / 3.72 4.15 / 4.19 4.92 / 4.95 0.00 0.00 16 301 0.03 T10 3 0.41 / 41.61 0.44 / 67.59 0.48 / 112.25 0.00 0.01 92 6 652 0.32 8 1.16 / 8.41 1.73 / 16.60 3.45 / 40.03 0.00 0.00 214 5 158 0.24 M/3 3.52 / 4.20 4.90 / 7.32 6.95 / 11.27 0.00 0.00 14 1 835 0.17 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 17 Table 14 Complete results (M=50) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 50 T1 3 0.88 / 6.92 0.92 / 23.42 1.00 / 42.88 0.00 0.00 38 1 870 0.19 8 2.06 / 4.23 3.43 / 6.46 5.17 / 11.97 0.00 0.00 342 8 169 0.14 M/3 10.27 / 10.28 11.96 / 12.00 14.34 / 14.38 0.00 0.00 5 531 0.04 T2 3 0.89 / 10.22 1.11 / 24.57 1.23 / 36.98 0.03 0.10 27 232 0.65 8 6.31 / 8.64 6.76 / 13.35 7.63 / 22.05 0.17 0.27 105 1 238 0.56 M/3 6.02 / 9.31 8.11 / 28.29 12.33 / 42.95 0.32 0.67 110 8846 0.43 T3 3 0.86 / 375.52 0.94 / 543.26 1.06 / 911.48 0.05 0.21 426 54103 0.63 8 1.98 / 242.58 2.67 / 1717.30 3.63 / 3600 0.02 0.09 5890 187 349 0.51 M/3 10.41 / 11.41 11.66 / 15.99 14.31 / 19.34 0.00 0.00 45 4 073 0.26 T4 3 0.86 / 12.55 0.92 / 35.76 1.02 / 64.11 0.00 0.00 109 12 134 0.29 8 2.09 / 5.27 2.23 / 12.47 2.48 / 24.48 0.00 0.00 1235 38 768 0.21 M/3 10.05 / 10.34 12.61 / 16.17 16.08 / 29.25 0.00 0.00 45 2 291 0.10 T5 3 0.86 / 10.00 0.90 / 36.42 0.95 / 67.39 0.01 0.06 47 3 119 0.22 8 2.05 / 7.41 3.15 / 11.54 4.45 / 17.20 0.00 0.00 309 8 166 0.16 M/3 9.94 / 9.97 13.24 / 13.79 16.95 / 17.53 0.00 0.02 30 881 0.06 T6 3 0.86 / 15.11 0.93 / 35.66 1.00 / 75.59 0.02 0.08 32 1 190 0.19 8 2.16 / 9.17 2.78 / 13.75 3.95 / 18.61 0.00 0.00 120 2 079 0.14 M/3 10.52 / 11.00 13.21 / 15.46 17.47 / 22.42 0.00 0.00 78 1 048 0.05 T7 3 0.88 / 13.55 0.90 / 33.83 0.94 / 56.17 0.01 0.06 30 836 0.19 8 2.11 / 6.23 2.79 / 11.09 3.73 / 20.13 0.01 0.03 90 852 0.15 M/3 10.64 / 10.80 14.22 / 15.14 23.28 / 25.78 0.00 0.00 44 734 0.05 T8 3 0.84 / 19.38 0.92 / 55.63 1.06 / 96.66 0.01 0.07 46 1 653 0.22 8 1.86 / 12.14 2.81 / 25.90 3.94 / 35.58 0.01 0.02 234 2 837 0.18 M/3 10.00 / 11.42 12.63 / 16.19 17.52 / 20.91 0.01 0.04 113 1 889 0.08 T9 3 0.84 / 30.44 0.93 / 48.38 1.02 / 88.16 0.00 0.01 37 919 0.22 8 2.14 / 4.95 2.34 / 10.06 2.58 / 17.09 0.00 0.00 82 689 0.11 M/3 10.05 / 10.11 12.89 / 13.03 17.39 / 17.44 0.00 0.00 25 396 0.02 T10 3 0.86 / 50.28 0.92 / 196.93 1.00 / 399.92 0.00 0.00 128 8 938 0.31 8 2.05 / 72.84 2.54 / 271.21 3.36 / 607.36 0.00 0.05 1626 40 688 0.28 M/3 11.47 / 11.92 13.33 / 18.40 16.20 / 26.61 0.01 0.03 19 2 311 0.16 Table 15 Complete results (M=60) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 60 T1 3 1.64 / 57.22 1.68 / 106.38 1.73 / 216.77 0.01 0.03 112 9 109 0.26 8 3.42 / 11.22 4.73 / 23.43 6.13 / 52.14 0.01 0.02 1055 26 202 0.18 M/3 25.42 / 25.45 29.98 / 30.07 34.44 / 34.55 0.00 0.00 11 1 331 0.04 T2 3 1.73 / 51.95 1.94 / 87.48 2.08 / 113.44 0.09 0.15 63 173 0.68 8 9.22 / 11.64 11.22 / 31.72 15.44 / 86.56 0.10 0.18 180 1 565 0.60 M/3 12.80 / 31.75 18.80 / 139.72 23.78 / 475.27 0.28 0.67 640 34 474 0.43 T3 3 1.53 / 1483.02 1.69 / 2078.92 1.78 / 2774.53 0.01 0.03 907 129 980 0.68 8 4.59 / 2492.08 5.63 / 3379.75 7.61 / 3600 0.00 0.00 9194 217 361 0.57 M/3 28.94 / 40.19 39.76 / 71.35 55.31 / 144.33 0.00 0.01 231 16 461 0.28 T4 3 1.66 / 39.89 1.72 / 78.68 1.84 / 149.28 0.00 0.02 218 27 240 0.34 8 3.73 / 21.81 4.54 / 47.74 5.95 / 69.00 0.00 0.02 1942 45 557 0.25 M/3 23.84 / 24.00 27.84 / 44.28 38.27 / 76.95 0.00 0.00 183 7 908 0.10 T5 3 1.64 / 87.09 1.68 / 176.49 1.70 / 353.95 0.01 0.03 105 6 772 0.28 8 3.56 / 22.58 4.74 / 42.48 5.30 / 88.52 0.00 0.01 522 9 537 0.19 M/3 25.41 / 26.64 33.90 / 34.97 45.61 / 46.53 0.00 0.00 74 2 151 0.06 T6 3 1.63 / 73.86 1.70 / 121.03 1.80 / 213.56 0.01 0.03 63 2 009 0.25 8 3.69 / 19.14 4.58 / 60.48 7.05 / 128.80 0.01 0.06 255 2 731 0.17 M/3 24.03 / 25.92 29.48 / 31.61 36.81 / 37.28 0.00 0.02 71 1 108 0.04 T7 3 1.58 / 86.83 1.67 / 166.65 1.72 / 342.38 0.01 0.04 69 1 535 0.26 8 3.39 / 16.73 4.22 / 47.02 5.11 / 107.98 0.04 0.13 209 1 050 0.17 M/3 25.31 / 25.47 30.17 / 31.03 37.70 / 38.48 0.00 0.01 37 669 0.04 T8 3 1.64 / 106.52 1.70 / 243.07 1.78 / 538.84 0.01 0.05 110 4 999 0.29 8 3.20 / 24.03 4.49 / 93.29 5.77 / 200.84 0.01 0.02 458 4 400 0.20 M/3 21.11 / 32.75 33.07 / 42.69 53.31 / 65.77 0.01 0.04 241 3 822 0.06 T9 3 1.66 / 52.69 1.71 / 154.15 1.80 / 313.33 0.00 0.01 60 1 455 0.26 8 3.69 / 19.14 4.73 / 54.03 6.86 / 113.72 0.00 0.00 189 1 195 0.15 M/3 24.94 / 25.00 34.29 / 34.67 49.33 / 50.36 0.00 0.00 53 786 0.02 T10 3 1.59 / 750.88 1.78 / 1214.11 2.14 / 2018.92 0.01 0.07 406 44 862 0.37 8 3.73 / 304.63 5.77 / 1999.35 7.89 / 3600 0.00 0.02 5022 130 801 0.33 M/3 26.91 / 35.08 33.90 / 57.88 40.05 / 104.86 0.00 0.01 47 6 215 0.17 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS 18 A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx Table 16 Complete results (M=70) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 70 T1 3 2.61 / 113.25 2.84 / 198.89 3.25 / 397.53 0.00 0.02 27 111 0.18 8 6.77 / 20.03 7.39 / 39.64 8.36 / 66.44 0.00 0.02 49 34 0.11 M/3 57.61 / 57.64 87.96 / 88.10 162.80 / 163.02 0.00 0.00 12 983 0.04 T2 3 2.70 / 156.08 2.89 / 544.15 3.14 / 1179.95 0.08 0.13 288 1 116 0.70 8 13.98 / 93.39 15.98 / 372.69 18.67 / 1147.52 0.18 0.25 1647 12 742 0.62 M/3 24.34 / 35.48 26.99 / 63.37 31.91 / 137.13 0.83 1.17 96 8 736 0.39 T3 3 – / – – / – – / – – – – – – 8 – / – – / – – / – – – – – – 24 57.81 / 64.08 71.64 / 93.12 105.66 / 143.19 0.00 0.00 107 8 285 0.24 T4 3 2.67 / 115.38 2.89 / 147.47 3.23 / 173.98 0.01 0.03 118 2 205 0.36 8 5.42 / 35.91 6.08 / 118.48 7.84 / 235.00 0.01 0.05 1282 16 876 0.27 M/3 48.75 / 55.77 59.65 / 64.03 68.77 / 74.61 0.00 0.00 48 2 773 0.07 T5 3 2.69 / 157.72 2.93 / 290.69 3.28 / 555.11 0.00 0.02 71 1 329 0.27 8 6.36 / 40.61 9.10 / 91.36 11.83 / 183.20 0.00 0.00 379 3 854 0.19 M/3 55.05 / 57.55 61.35 / 62.93 70.25 / 71.08 0.01 0.02 62 1 421 0.05 T6 3 2.67 / 149.09 2.86 / 250.62 3.11 / 493.36 0.00 0.00 55 1 010 0.24 8 5.89 / 59.16 6.80 / 115.19 7.64 / 183.14 0.01 0.03 229 1 394 0.17 M/3 55.33 / 57.52 60.44 / 68.80 75.95 / 83.45 0.00 0.02 202 2 209 0.04 T7 3 2.69 / 185.73 2.89 / 302.94 3.11 / 618.64 0.00 0.00 58 1 057 0.25 8 6.06 / 33.50 7.76 / 88.23 11.11 / 169.59 0.01 0.02 187 747 0.17 M/3 56.78 / 57.69 68.07 / 71.40 92.02 / 92.48 0.00 0.01 114 1 322 0.04 T8 3 2.69 / 211.36 2.93 / 389.43 3.20 / 767.75 0.00 0.00 79 1 764 0.27 8 5.27 / 42.34 7.99 / 162.98 9.92 / 362.38 0.01 0.06 340 2 695 0.19 M/3 56.83 / 57.27 65.77 / 68.28 77.05 / 79.83 0.00 0.02 94 1 281 0.05 T9 3 2.67 / 274.95 2.82 / 360.12 3.02 / 420.27 0.00 0.01 71 1 298 0.28 8 5.44 / 27.73 6.59 / 65.58 7.72 / 123.80 132 0.00 0.00 678 0.14 M/3 59.70 / 59.77 78.43 / 78.53 114.63 / 114.81 0.00 0.01 19 257 0.01 T10 3 – / – – / – – / – – – – – – 8 – / – – / – – / – – – – – – M/3 58.72 / 62.39 73.14 / 86.93 86.44 / 118.45 0.00 0.00 39 4 118 0.15 Table 17 Complete results (M=80) MλNMin. time Ave. time Max. time Ave. H.gap Max. H.gap # N. # C. R.-N. gap 80 T1 3 4.25 / 226.06 4.36 / 449.46 4.69 / 673.59 0.01 0.03 36 167 0.18 8 8.73 / 77.61 12.36 / 178.58 17.73 / 248.89 0.00 0.01 98 59 0.14 M/3 113.38 / 113.42 138.93 / 139.05 192.14 / 192.20 0.00 0.00 46 5 168 0.04 T2 3 3.17 / 493.98 3.42 / 950.00 3.75 / 1300.17 0.08 0.23 345 1 268 0.73 8 6.44 / 498.95 8.36 / 1752.73 12.88 / 3600 0.15 0.23 4287 26 109 0.67 M/3 48.11 / 106.63 66.24 / 206.01 81.55 / 534.58 0.62 0.83 167 18 941 0.44 T3 3 – / – – / – – / – – – – – – 8 – / – – / – – / – – – – – – M/3 113.00 / 143.00 133.76 / 243.82 163.30 / 424.98 0.00 0.00 230 21 730 0.26 T4 3 4.14 / 119.72 4.26 / 217.31 4.58 / 370.92 0.02 0.09 106 1 410 0.34 8 7.91 / 148.89 9.32 / 365.37 11.03 / 769.67 0.00 0.00 1160 10 065 0.28 M/3 102.25 / 107.81 126.35 / 132.66 147.61 / 151.61 0.00 0.02 71 5 570 0.08 T5 3 4.19 / 361.53 4.33 / 633.52 4.72 / 908.78 0.01 0.03 80 1 223 0.27 8 7.61 / 140.47 9.89 / 378.96 11.94 / 509.33 0.01 0.03 571 3 280 0.22 M/3 102.17 / 103.17 155.99 / 157.27 203.83 / 205.52 0.00 0.01 46 1 695 0.04 T6 3 4.22 / 216.55 4.36 / 423.55 4.70 / 605.80 0.00 0.00 66 919 0.24 8 8.92 / 145.06 10.92 / 342.31 16.84 / 557.34 0.01 0.03 323 1 278 0.19 M/3 105.33 / 115.39 123.68 / 131.93 138.92 / 154.73 0.01 0.01 112 1 420 0.03 T7 3 4.20 / 283.09 4.35 / 587.86 4.70 / 896.86 0.01 0.02 68 876 0.24 8 8.56 / 163.73 11.96 / 320.00 19.11 / 395.48 0.00 0.02 292 936 0.20 M/3 106.42 / 111.02 125.99 / 130.18 169.11 / 169.41 0.00 0.01 94 1 580 0.03 T8 3 4.17 / 436.36 4.23 / 855.20 4.31 / 1265.75 0.01 0.02 98 2 350 0.27 8 8.78 / 285.47 11.25 / 670.93 14.78 / 1007.44 0.00 0.01 663 4 666 0.23 M/3 94.16 / 101.80 122.59 / 126.52 157.27 / 158.17 0.00 0.02 100 1 862 0.04 T9 3 4.19 / 438.31 4.28 / 621.11 4.58 / 933.38 0.01 0.07 69 1 207 0.26 8 7.69 / 221.36 9.06 / 500.14 13.20 / 1222.34 0.00 0.00 391 1 801 0.18 M/3 120.64 / 120.95 159.73 / 159.92 228.17 / 228.47 0.00 0.01 21 372 0.01 T10 3 – / – – / – – / – – – – – – 8 – / – – / – – / – – – – – – M/3 152.84 / 212.98 184.10 / 351.64 257.14 / 590.39 0.00 0.01 220 25 319 0.16 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013 UNCORRECTED PROOF DAM: 7027 ARTICLE IN PRESS A. Marín et al. / Discrete Applied Mathematics xx (xxxx) xxx–xxx 19 Acknowledgements 1 Alfredo Marín greatefully acknowledges support provided by Plan Nacional de Investigación Científica, Desarrollo e Innovaci 2 ón Tecnológica (I+D+I), projects HA2005-0056 and MTM2006-14961-C05-04, RDEF funds and Fundación Séneca, project 3 02911/PI/05. Stefan Nickel and Sebastian Velten thank the German Academic Exchange Service (DAAD) (grant number: 4 D/05/5D/05/59) for partial support. Justo Puerto thanks partial support through grant numbers P06-FQM-01366 and 5 MTM2007-67433-C02-01. 6 Appendix 7 See Tables 12–17.8 References 9 [1] M. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, Wiley, 1995. 10 [2] Z. Drezner, H. Hamacher, Facility Location: Applications and Theory, Springer, Berlin Heidelberg, New York, 2002. 11 [3] P. Mirchandani, R. Francis, Discrete Location Theory, Wiley, New York, NY, 1990. 12 [4] L. Cánovas, M. Landete, A. Marín, On the facets of the simple plant location packing polytope, Discrete Applied Mathematics 124 (2002) 27–53. 13 [5] K. Aardal, Capacitated facility location: Separation algorithms and computational experience, Mathemathical Programming 81 (1998) 149–175. 14 [6] A. Marín, Lower bounds for the two-stage uncapacitated facility location problem, European Journal of Operational Research 179 (2007) 1126–1142. 15 [7] L. Cánovas, S. García, M. Labbé, A. Marín, A strengthened formulation for the simple plant location problem with order, Operations Research Letters 16 35 (2) (2007) 141–150. 17 [8] M. Melo, S. Nickel, F. Saldanha da Gama, Dynamic multi-commodity capacitated facility location: A mathematical modeling framework for strategic 18 supply chain planning, Computers and Operations Research 33 (2006) 181–208. 19 [9] S. Nickel, Discrete Ordered Weber Problems, in: Operations Research Proceedings 2000, Springer Verlag, 2001, pp. 71–76. 20 [10] R. Francis, T. Lowe, A. Tamir, Aggregation error bounds for a class of location models, Operations Research 48 (2000) 294–307. 21 [11] S. Nickel, J. Puerto, A unified approach to network location problems, Networks 34 (1999) 283–290. 22 [12] A. Rodríguez-Chía, S. Nickel, J. Puerto, F. Fernández, A flexible approach to location problems, Mathematical Methods of Operations Research 51 (2000) 23 69–89. 24 [13] S. Nickel, J. Puerto, Facility Location - A Unified Approach, Springer Verlag, 2005. 25 [14] N. Boland, P. Domínguez-Marín, S. Nickel, J. Puerto, Exact procedures for solving the discrete ordered median problem, Computers and Operations 26 Research 33 (2005) 3270–3300. 27 [15] W. Ogryczak, A. Tamir, Minimizing the sum of the klargest functions in linear time, Information Processing Letters 85 (3). 28 [16] G. Cornuéjols, G. Nemhauser, L. Wolsey, A canonial representation of simple plant location problems and its applications, SIAM Journal on Algebraic 29 and Discrete Methods 1 (3) (1980) 261–272. 30 [17] A. Kolen, Solving covering problems and the uncapacitated plant location problem on trees, European Journal of Operational Research 12 (1983) 31 266–278. 32 [18] S. Elloumi, M. Labbé, Y. Pochet, A new formulation and resolution method for the p-center problem, INFORMS Journal on Computing 16 (1) (2004) 33 84–94. 34 [19] P. Domínguez-Marín, S. Nickel, N. Mladenović, P. Hansen, Heuristic procedures for solving the discrete ordered median problem, Annals of Operations 35 Research 136 (2005) 145–173. 36 [20] P. Domínguez-Marín, The discrete ordered median problem: Models and solution methods, Ph.D. Thesis, University of Kaiserslautern, 2003. 37 [21] O. Kariv, S. Hakimi, An algorithmic approach to network location problems II: The p-medians, SIAM Journal on Applied Mathematics 37 (1979) 539–560. 38 [22] J. Beasley, Or-library: Distributing test problems by electronic mail, Journal of the Operational Research Society 41 (1990) 1069–1072, available at 39 http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files.40 [23] N. Mladenović, P. Hansen, Variable neighborhood search, Computers and Operations Research 24 (1997) 1097–1100. 41 Please cite this article in press as: A. Marín, et al., A flexible model and efficient solution strategies for discrete location problems, Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.03.013