zbMATH — the first resource for mathematics

Solution methods for the $$p$$-median problem: an annotated bibliography. (English) Zbl 1133.90357
Summary: The $$p$$-median problem is a network problem that was originally designed for, and has been extensively applied to, facility location. In this bibliography, we summarize the literature on solution methods for the uncapacitated and capacitated $$p$$-median problem on a network.

MSC:
 90B60 Marketing, advertising 90-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to operations research and mathematical programming
Software:
 [1] Alp, Ann Oper Res 122 pp 21– (2003) [2] , , Lagrangian relaxation for the k-median problem: New insights and continuity properties, Proc 11th Ann Eur Symp Algorithms, Springer-Verlag, Berlin, 2003, pp. 31–42. Shows that a modification to the algorithm in [71] attains a ”continuity” property. The paper also shows that an algorithm originally developed for the UFLP can be used for the p-median problem due to its capability of preserving the Lagrangian multipliers. This algorithm is described and a proof of its approximation factor of 3 is presented. [3] Ardalan, Int J Oper Production Manage 8 pp 52– (1988) [4] Arya, SIAM J Comput 33 pp 544– (2004) [5] Ashayeri, Robotics Comput-Integrated Manufact 21 pp 451– (2005) [6] Avella, Math Program 89 pp 395– (2001) [7] , , Computational study of large-scale p-median problems, Technical report 08-03, Università di Roma ”La Sapienza,” 2003. Presents a branch-and-price-and-cut algorithm to solve large-scale instances of the p-median problem. This involves a column-and-row generation strategy to solve a relaxed LP and cutting planes to strengthen the formulation. The authors report computational results on large problems involving at least 900 vertices. [8] Avella, Electron Notes Discrete Math 13 pp 14– (2003) [9] Avella, Ann Oper Res 86 pp 105– (1999) [10] Baker, Logist Transportation Review 10 pp 195– (1974) [11] Balinski, Manage Sci 12 pp 253– (1965) [12] Beasley, Eur J Oper Res 21 pp 270– (1985) [13] Beasley, Eur J Oper Res 65 pp 383– (1993) [14] , , Solving the p-median problem with a semi-Lagrangian relaxation, Technical report, Logilab, HEC, University of Geneva, 2004. Describes a semi-Lagrangian relaxation that, under certain conditions, closes the integrality gap for any linear combinatorial problem with equality constraints. For large enough Lagrangian multipliers, this relaxation closes the integrality gap. The p-median problem is easier to solve, however, when the multipliers are small. The insight here is to increase the Lagrangian multipliers but keep them small enough to keep an associated subproblem easy until an integer optimal solution is found. Computational results are presented, showing that this method solved to optimality several ”easy” problems, and improved the best known dual bounds on several unsolved ”difficult” problems. The method was able to solve to optimality one of the previously unsolved ”difficult” problems. [15] , A new template for solving p-median problems for trees in sub-quadratic time (extended abstract), ESA 2005: 13th Ann Eur Symp Algorithms, Lecture Notes in Comput Sci, Springer-Verlag, Berlin, 2005, pp. 271–282. Proposes a subquadratic time algorithm for the p-median problem defined on a tree with fixed p. The algorithm uses dynamic programming and spine decomposition techniques and runs in O(n log p + 2(n)) time. This improves the previous best known dynamic programming algorithm in [124], with running time O(pn2). [16] , , ” An efficient genetic algorithm for the p-median problem,” Facility location: Applications and theory, (Editors), Springer Verlag, Berlin, 2002, pp. 179–205. A genetic algorithm that models solutions with chromosomes is developed. Each gene of the chromosome is an index of a p-median vertex. Three crossover operators are presented and tested. These variations are compared with the genetic algorithm in [68] and favorable results are reported. The genetic algorithm here improves solutions slowly but steadily, and the authors claim that it is less likely than vertex substitution [126] to be trapped in local optima. [17] Captivo, Eur J Oper Res 52 pp 65– (1991) [18] Ceselli, 4OR: Q J Belgian, French Italian Oper Res Soc 1 pp 319– (2003) [19] Ceselli, Networks 45 pp 125– (2005) [20] , , , Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median, STOC ’98: Proc Thirtieth Ann ACM Symp Theory Comput, ACM Press, New York, 1998, pp. 114–123. A deterministic approximation algorithm that matches the best known randomized approximation is presented. This algorithm has an approximation ratio of O(log p log log p). [21] , Improved combinatorial algorithms for the facility location and k-median problems, FOCS ’99: Proc 40th Ann Symp Foundations Comput Sci, IEEE Computer Society, Washington, DC, 1999, pp. 378–388. This modifies and improves the algorithm in [71], providing a 4-approximation algorithm for the metric p-median problem in O(n2(L + n) log n) time, where L is the number of bits needed to represent cij, or the metric distance. [22] , , , A constant-factor approximation algorithm for the k-median problem (extended abstract), STOC ’99: Proc Thirty-First Ann ACM Symp Theory Comput, ACM Press, New York, 1999, pp. 1–10. Provides a 20/3-approximation algorithm for the metric p-median problem. The authors claim that this is the first constant factor approximation algorithm presented for the p-median problem. The algorithm solves a relaxed LP and builds a collection of trees from the solution. It then solves the problem optimally on this collection. [23] , Approximation algorithms for network problems, lecture notes, webpage. http://www.tepper.cmu.edu/andrew/ravi/. Provides, for any > 0, an approximation algorithm for the p-median problem that finds a solution within (1 + ) of the optimal value and using no more than (1 + (1/)H(n)p) medians, where H(n) is the nth harmonic number. [24] Chiou, Eur J Oper Res 135 pp 413– (2001) [25] Chiyoshi, Ann Oper Res 96 pp 61– (2000) [26] Graph theory: An algorithmic approach, Academic Press, New York, 1975. Contains a section on solution methods for the p-median problem, summarizing many of the methods present in 1979 and introducing a direct tree search algorithm. This algorithm allocates vertices v1 to vn sequentially to their nearest neighboring vertex. Several informed observations are used to limit the number of alternative possible allocations of a vertex vi at any stage. A method for calculating a lower bound on the objective function to further limit the search is also presented. [27] Christofides, Eur J Oper Res 10 pp 196– (1982) [28] Chrobak, Informat Process Lett 97 pp 68– (2006) [29] Church, Ann Oper Res 122 pp 103– (2003) [30] Cornuéjols, Manage Sci 23 pp 789– (1977) [31] Correa, Numer Algorithms 35 pp 373– (2004) [32] , , , Parallel variable neighborhood search for the p-median, Les Cahiers du GERAD G-2003-4 ( 2003). Summarizes the methods in [55] and offers a new strategy entitled Cooperative Neighborhood VNS (CNVNS). This is a master–slave procedure where the master process initiates several VNS threads, each of which randomly chooses a neighborhood to explore. Threads report improved solutions to the master process in order to find an overall solution. [33] Crainic, J Heuristics 10 pp 293– (2004) [34] Network and discrete location: Models, algorithms, and applications, John Wiley & Sons, Inc., New York, 1995. Contains a chapter entitled ”Median Problems,” which describes in detail three types of heuristics: myopic (greedy), exchange (vertex substitution), and neighborhood search. A Lagrangian relaxation approach is also presented. A software implementation of these methods accompanies the book, and computational results of these approaches are given. [35] de Farias, Oper Res Lett 28 pp 161– (2001) [36] , Designing and implementing strategies for solving large location–allocation problems with heuristic methods, Technical report 91-10, National Center for Geographic Information and Analysis, Buffalo, NY, 1991. Discusses how to implement vertex substitution [126], specifically detailing speedup strategies. These include minimizing the volume of data and access times to that data, and exploiting the spatial structure of the problem to reduce the number of vertices to check after each substitution. The authors also discuss using an allocation table as an alternative method of keeping track of the changes in the objective function as vertices are substituted. [37] Densham, Papers in Regional Sci 71 pp 307– (1992) [38] Densham, Environ Plan A 24 pp 289– (1992) [39] Díaz, Eur J Oper Res 169 pp 570– (2006) [40] , Applying bio-inspired techniques to the p-median problem, IWANN 2005: Computational Intelligence Bioinspired Syst, 8th Int Workshop Artificial Neural Networks, Lecture Notes in Comput Science, Springer-Verlag, Berlin, 2005, pp. 67–74. Presents a genetic algorithm and a stochastic neural network. The genetic algorithm uses some specialized operations such as bit-flip mutation and uniform recombination. The stochastic neural network is based upon the recurrent neural network but is claimed to be more accurate here. The experimental results compare the genetic algorithm and both stochastic and recurrent neural networks to benchmarks. The authors note that on medium-scale instances, the neural networks outperform the genetic algorithm. [41] , Location and layout planning: An international bibliography, Lecture Notes in Economics and Mathematical Systems 238, Springer-Verlag, Berlin, 1985. Lists over 1800 references pertaining to location theory. · Zbl 0554.90028 [42] , Proximal ACCPM, a cutting plane method for column generation and Lagrangian relaxation: Application to the p-median problem, Technical report 2002.23, HEC Genève, Université de Genève, 2002. Presents a variant of the analytic center cutting plane method (ACCPM) that incorporates two features from the Bundle method. A proximal term is added to the logarithmic barrier function and a step to reduce the number of columns in the localization set is implemented. Extensive computational results are presented. [43] Compatibility-based genetic algorithm: A new approach to the p-median problem, Technical report, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 1999. Presents a compatibility measure that helps genetic algorithms to make better guesses when selecting solutions for the reproduction and crossover stages. The compatibility measure considers candidate parents together rather than choosing the two parents independently. Computational results are presented, comparing this method with greedy heuristics [30,78], vertex substitution [126], and the alternate heuristic [87]. The authors show that in some instances, the genetic algorithm outperforms other heuristics. [44] Efroymson, Oper Res 14 pp 361– (1966) [45] Eilon, Manage Sci 24 pp 1763– (1978) [46] El-Shaieb, Manage Sci 20 pp 221– (1973) [47] Erlenkotter, Oper Res 26 pp 992– (1978) [48] , Hybrid genetic algorithm for solving the p-median problem, SEAL ’98: Selected Papers from Second Asia-Pacific Conference Simulated Evolution Learning, Springer-Verlag, Berlin, 1999, pp. 19–25. Combines genetic algorithms and vertex substitution [126]. This hybrid technique is useful for avoiding local optima that vertex substitution is prone to finding. The authors claim that this method outperforms both ordinary genetic algorithms and stand-alone vertex substitution. [49] Fathali, Eur J Oper Res 170 pp 440– (2006) [50] Galvão, Oper Res 28 pp 1112– (1980) [51] Galvão, Eur J Oper Res 6 pp 162– (1981) [52] Galvão, Transportation Sci 15 pp 175– (1981) [53] Galvão, Eur J Oper Res 17 pp 128– (1984) [54] Galvão, Ann Oper Res 18 pp 225– (1989) [55] García-López, J Heuristics 8 pp 375– (2002) [56] García-López, Parallel Comput 29 pp 575– (2003) [57] , Computers and intractibility: A guide to the theory of NP-completeness, W.H. Freeman and Co., San Francisco, 1979. Shows that the p-median problem is NP-hard. If p is fixed then it is solvable in polynomial time. It is also solvable in polynomial time for arbitrary p if the network is a tree. [58] Garfinkel, Transportation Sci 8 pp 217– (1974) [59] Tabu search for the p-median problem, unpublished manuscript, 1990. Proposes an implementation of tabu search for the p-median problem and details its associated interchange, strategic oscillation, candidate list, intensification and diversification strategies. [60] , Location-allocation for small computers, Monograph No. 8, Technical report, University of Iowa, Department of Geography, 1983. Implements several shortest path algorithms and ALLOC [116] in BASIC for solving location–allocation problems. The implementation was tested with favorable results on the p-median problem. [61] Hakimi, Oper Res 12 pp 450– (1964) [62] Hakimi, Oper Res 13 pp 462– (1965) [63] , Location on networks: Theory and algorithms, MIT Press, Cambridge, MA, 1979. Provides an excellent overview of the computational methods for the p-median problem up to 1979. The solution methods are classified into five different categories: (1) enumeration, (2) graph theoretic, (3) heuristic, (4) primal-based LP methods, and (5) dual-based LP methods. [64] Hanjoul, Eur J Oper Res 20 pp 387– (1985) [65] Hansen, Location Sci 5 pp 207– (1997) [66] Hansen, J Heuristics 7 pp 335– (2001) [67] Horn, Environ Plan A 28 pp 1699– (1996) [68] Hosage, Ann Oper Res 6 pp 35– (1986) [69] Hribar, Eur J Oper Res 101 pp 499– (1997) [70] , , A new greedy approach for facility location problems, STOC ’02: Proc Thirty-Fourth Ann ACM Symp Theory Comput, New York, 2002, pp. 731–740. Presents a lower bound on the approximability of the metric p-median problem, showing that it may not be approximated with a factor strictly smaller than 1 + 2/. [71] Jain, J ACM 48 pp 274– (2001) [72] Järvinen, Oper Res 20 pp 173– (1972) [73] Kariv, SIAM J Appl Math 37 pp 539– (1979) [74] Khumawala, Manage Sci 18 pp 718– (1972) [75] Khumawala, Manage Sci 21 pp 230– (1974) [76] , A nearly linear-time approximation scheme for the Euclidean k-median problem, ESA ’99: Proc 7th Ann Eur Symp Algorithms, Springer-Verlag, Berlin, 1999, pp. 378–389. Presents the first polynomial time -approximation scheme for the p-median problem in d-dimensional Euclidean space for fixed d > 2. The running time for any fixed > 0 is O(2O((log(1/)/)d - 1)n log 6n). This is nearly linear for any fixed > 0 and d. [77] Korupolu, J Algorithms 37 pp 146– (2000) [78] Kuehn, Manage Sci 9 pp 643– (1963) [79] , , ” Location on networks”, Handbooks in operations research and management science, 8: Network routing, , , (Editors), North-Holland, Amsterdam, 1995, pp. 551–624. Provides an excellent theoretical survey of network location problems. The authors discuss the formulation and complexity of the p-median problem as well as several exact and heuristic solution methods. [80] Levanova, Automat Remote Control 65 pp 431– (2004) [81] Lim, Lecture Notes in Computer Science 2724 pp 1596– (2003) [82] Lin, Informa Process Lett 44 pp 245– (1992) [83] Lorena, Evolut Comput 9 pp 309– (2001) [84] Lorena, Networks Spatial Econo 3 pp 409– (2003) [85] Lorena, Comput Oper Res 31 pp 863– (2004) [86] Maniezzo, J Heuristics 4 pp 263– (1998) [87] Maranzana, Oper Res Q 15 pp 261– (1964) [88] An algorithm for finding almost all the medians of a network, Technical report 23, Center for Math Studies in Economics and Management Science, Northwestern University, ( 1972). Shows that for a network of n vertices every p-median (1 p n) is an extreme point of a polyhedron. An algorithm that tours these extreme points is presented. Some extreme points correspond to p-median solutions with a fractional value of p. Furthermore, the tour may not hit a p-median for every value of p. Aside from these exceptions the algorithm is shown to create a complete set of medians. [89] , An efficient neural network algorithm for the p-median problem, IBERAMIA 2002: Proceedings 8th Ibero-American Conference AI, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2002, pp. 460–469. Presents an alternate formulation of the p-median problem and then applies a Hopfield neural network model to solve it. The problem formulation involves two types of neurons: one for location and the other for allocation. The constrained formulation is turned into an unconstrained problem by introducing a penalty function that penalizes the objective function if constraints are violated. Computational results are presented comparing this method with vertex substitution [126]. [90] , , Neural network algorithms for the p-median problem, Proc 2003 ur Symp Artificial Neural Networks (ESANN 2003), D-Facto, Brussels, 2003, pp. 385–391. Offers three different variations of a neural network algorithm for the p-median problem. The objective function is modelled as an energy function, which is guaranteed to decrease or remain unchanged as the system changes according to a given dynamical rule. The different variations, iterative, agglomerative, and stepwise, are tested against vertex substitution [126] and the results are presented. [91] Approximation algorithms for NP-hard clustering problems, Ph.D. Thesis, Department of Computer Science, University of Texas at Austin, 2002. Develops a randomized O(1)-approximate algorithm for the p-median problem that runs in O(n(p + log n) + p2 log 2n) time. For a wide range of p values, i.e., $$\log n \leq p \leq {{n}\over{\log^2 n}}$$, the complexity is shown to reduce to O(np). [92] ” The p-median problem and generalizations”, Discrete location theory, (Editors), John Wiley & Sons, Inc., New York, 1990, pp. 55–117. Describes the classical p-median problem and discusses variations such as the p-median problem on oriented networks, probabilistic costs and demands, and multidimensional networks. The author then gives a survey of solution methods, classifying them into the same five categories as [63]. [93] Mirchandani, Eur J Oper Res 21 pp 121– (1985) [94] , , , The p-median problem: A survey of metaheuristic approaches, Les Cahiers du GERAD G-2005-39 ( 2005). Provides an overview of some of the most common heuristic and metaheuristic approaches applied to the p-median problem. [95] Moreno-Pérez, Stud Locat Anal 7 pp 131– (1994) [96] Morgenstern, Eur J Oper Res 12 pp 404– (1983) [97] Narula, Oper Res 25 pp 709– (1977) [98] , A subgradient approach to the m-median problem, Technical report 75-12, University of North Carolina, Chapel Hill, ( 1975). Presents a subgradient method for solving the dual of the relaxed LP to overcome degeneracy in decomposition techniques. This procedure often terminates with the maximum dual objective value, and in some cases it leads to integer values for all of the primal variables. If not, the bounds may be used in a branch-and-bound algorithm. [99] Pirkul, Dec Support Syst 26 pp 209– (1999) [100] Pizzolato, Ann Oper Res 50 pp 473– (1994) [101] Rahman, Int J Oper Product Manage 11 pp 76– (1991) [102] , On the implementation of a swap-based local search procedure for the p-median problem, Proc Fifth Workshop Algorithm Eng Experiments (ALENEX), SIAM, Philadelphia, 2003, pp. 119–127. Develops a more efficient variant of vertex substitution [126] known as fast interchange. Several techniques to hasten the algorithm are developed. These include storing partial results in a matrix to speed up later steps, compressing this matrix, and preprocessing techniques. They report obtaining speedups of up to three orders of magnitude over the original fast interchange method. [103] , A fast swap-based local search procedure for location problems, Technical report TD-5R3KBH, AT&T Labs Research, ( 2004). Provides an implementation of vertex substitution [126] that builds on the implementation in [131]. This method uses gain, loss, extra, and netloss functions to determine the value of different substitutions. Values for these functions are stored in data structures so that the best swap may easily be found. [104] Resende, J Heuristics 10 pp 59– (2004) [105] ReVelle, Geographi Anal 2 pp 30– (1970) [106] Righini, Eur J Oper Res 86 pp 452– (1995) [107] Rolland, Eur J Oper Res 96 pp 329– (1996) [108] Rosing, Environ Plan B 24 pp 59– (1997) [109] Rosing, Geograp Anal 11 pp 86– (1979) [110] Rosing, Environ Plan A 11 pp 373– (1979) [111] Rosing, Comput Oper Res 29 pp 1317– (2002) [112] Rosing, Eur J Oper Res 97 pp 75– (1997) [113] Rosing, Eur J Oper Res 104 pp 93– (1998) [114] Rosing, J Oper Res Soc 30 pp 815– (1979) [115] Rosing, Eur J Oper Res 117 pp 522– (1999) [116] , ” ALLOC: Heuristic solutions to multifacility location problems on a graph,” Computer programs for location-allocation problems, , (Editors), Monograph No. 6, University of Iowa, Department of Geography, 1973, pp. 163–187. Presents a FORTRAN implementation of two common heuristics for solving the p-median problem. The alternate heuristic [87] and vertex substitution [126] are implemented. The authors note that in 75 test runs, vertex substitution almost invariably outperformed the alternate heuristic. [117] Salhi, J Oper Res Soc 48 pp 1233– (1997) [118] Salhi, Comput Oper Res 29 pp 67– (2002) [119] , ” Lagrangean/surrogate heuristics for p-median problems,” Computing tools for modeling, optimization and simulation: Interfaces in computer science and operations research, (Editors), Kluwer Academic Publishers, Boston, 2000, pp. 115–130. Relaxes Constraint (1) (see Section 2.3) using a surrogate relaxation. This relaxation is not easily solved, so a Lagrangian relaxation is used on the surrogate formulation of the problem. Heuristic techniques are used to find a range of Lagrangian/surrogate multiplier values that improve the bounds of the usual Lagrangian relaxation technique. This approach was able to generate approximate solutions at least as good as the traditional Lagrangian relaxation technique while reducing computational effort for larger problems. [120] , Stabilizing column generation using Lagrangean/surrogate relaxation: An application to p-median location problems, Unpublished manuscript, ( 2001). Describes relationships between the Lagrangian/surrogate relaxation technique in [119] and column generation. This paper applies a column generation approach to the p-median problem that uses Lagrangian/surrogate relaxation as an acceleration process, generating new productive sets of columns at each iteration. Computational results show some improvement over the traditional column generation techniques. [121] , Complementary approaches for a clustering problem, XI CLAIO: Latin-Iberian American Congress Oper Res, University of Concepción, Chile, 2002, Proceedings on CD-ROM. Combines the Lagrangian/surrogate relaxation techniques in [119] with subgradient optimization and column generation to create two new heuristics. Computation results are presented, and the authors note that the heuristic using column generation is best when used on large-scale instances. The subgradient heuristic performed better on small-scale instances. [122] Senne, Comput Oper Res 32 pp 1655– (2005) [123] Heuristic methods for large centroid clustering problems, Technical report 96-96, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, Switzerland, ( 1996). Applies three new clustering methods to solving the p-median problem–candidate list search (CLS), local optimization (LOPT), and decomposition/recombination (DEC). CLS begins with the alternate heuristic [87], obtaining a locally optimal solution. This solution is perturbed by eliminating a vertex and adding another, similar to vertex substitution [126]. The new solution is chosen only if it is better than the initial one. LOPT selects a median and some nearby medians and generates and solves a corresponding subproblem. DEC uses LOPT to obtain a good solution for the overall problem. [124] Tamir, Oper Res Lett 19 pp 59– (1996) [125] Tansel, Manage Sci 29 pp 482– (1983) [126] Teitz, Oper Res 16 pp 955– (1968) [127] Quick k-median, k-center, and facility location for sparse graphs, ICALP ’01: Proceedings 28th Int Colloq Automata, Languages Program, Springer-Verlag, Berlin, 2001, pp. 249–260. Presents a 12 + o(1) constant factor approximation algorithm for the p-median problem. [128] Voß, Stud Locat Anal 8 pp 49– (1996) [129] Whitaker, Environ Plan A 13 pp 669– (1981) [130] Whitaker, Environ Plan B 9 pp 119– (1982) [131] Whitaker, INFOR 21 pp 95– (1983) [132] Greedy approximation algorithms for k-medians by randomized rounding, Technical report PCS-TR99-344, Department of Computer Science, Dartmouth College, Hanover, NH, ( 1999). Applies randomized rounding and other probabilistic methods to understanding the operation of greedy approximation algorithms. An approximation algorithm is presented that, for any > 0, finds a solution using at most ln(n + (n/))p medians and with objective value no more than (1 + ) times the optimal solution. This algorithm requires ln(n + (n/))p linear time iterations.