×

Revisiting several problems and algorithms in continuous location with \(\ell _\tau \) norms. (English) Zbl 1297.90073

Summary: This paper addresses the general continuous single facility location problems in finite dimension spaces under possibly different \(\ell _\tau \) norms, \(\tau \geq 1\), in the demand points. We analyze the difficulty of this family of problems and revisit convergence properties of some well-known algorithms. The ultimate goal is to provide a common approach to solve the family of continuous \(\ell _\tau \) ordered median location problems [S. Nickel and J. Puerto, Location theory. A unified approach. Berlin: Springer (2005; Zbl 1229.90001)] in dimension \(d\) (including of course the \(\ell _\tau \) minisum or Fermat-Weber location problem for any \(\tau \geq 1\)). We prove that this approach has a polynomial worst case complexity for monotone lambda weights and can be also applied to constrained and even non-convex problems.

MSC:

90B85 Continuous location
90C22 Semidefinite programming
65K05 Numerical mathematical programming methods
12Y05 Computational aspects of field theory and polynomials (MSC2010)
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics

Citations:

Zbl 1229.90001

Software:

SDPT3; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows. Theory, algorithms, and applications. Prentice Hall Inc, Englewood Cliffs, NJ. xvi+846 pp. ISBN: 0-13-617549-X (1993) · Zbl 1201.90001
[2] Blanco, V., Ben-Ali, S., Puerto, J.: Minimizing ordered weighted averaging of rational functions with applications to continuous location. Comput. Oper. Res. 40(5), 1448-1460 (2013) · Zbl 1352.90058
[3] Boland, N; Domínguez-Marín, P; Nickel, S; Puerto, J, Exact procedures for solving the discrete ordered Median problem, Comput. Oper. Res., 33, 3270-3300, (2006) · Zbl 1113.90099
[4] Brimberg, J; Love, RF, Local convergence in a generalized Fermat-Weber problem, Ann. Oper. Res., 40, 33-65, (1992) · Zbl 0787.90040
[5] Brimberg, J; Love, RF, Global convergence of a generalized iterative procedure for the minisum location problem with \(l_p\) distances, Oper. Res., 41, 1153-1163, (1993) · Zbl 0795.90037
[6] Brimberg, J, The Fermat-Weber location problem revisited, Math. Program., 71, 71-76, (1995) · Zbl 0855.90075
[7] Brimberg, J; Wesolowsky, GO, Minisum location with closest Euclidean distances, Ann. Oper. Res., 111, 151-165, (2002) · Zbl 1040.90020
[8] Brimberg, J, Further notes on convergence of the weiszfeld algorithm, Yugosl. J. Oper. Res., 13, 199-206, (2003) · Zbl 1274.90207
[9] Brimberg, J; Chen, R, A note on convergence in the single facility minisum location problem, Comput. Math. Appl., 35, 25-31, (1998) · Zbl 0992.90043
[10] Brimberg, J; Chen, R; Chen, D, Accelerating convergence in the Fermat-Weber location problem, Oper. Res. Lett., 22, 151-157, (1998) · Zbl 0911.90239
[11] Canovas, L; Cañavate, R; Marin, A, On the convergence of the weiszfeld algorithm, Math. Program., 93, 327-330, (2002) · Zbl 1065.90054
[12] Chandrasekaran, R; Tamir, A, Open questions concerning weiszfeld’s algorithm for the Fermat-Weber location problem, Math. Program., 44, 293-295, (1989) · Zbl 0683.90026
[13] Chen, R, Optimal location of a single facility with circular demand areas, Comput. Math. Appl., 41, 1049-1061, (2001) · Zbl 0980.90047
[14] Chen, R, Solution of location problems with radial cost functions, Comput. Math. Appl., 10, 87-94, (1984) · Zbl 0524.65046
[15] Chen, R, Location problems with costs being sums of powers of Euclidean distances, Comput. Oper. Res., 11, 285-294, (1984) · Zbl 0608.90018
[16] Cooper, L, An extension of the generalized Weber problem, J. Reg. Sci., 8, 181-197, (1968)
[17] Drezner, Z, A note on the Weber location problem, Ann. Oper. Res., 40, 153-161, (1992) · Zbl 0787.90042
[18] Drezner, Z, A note on accelerating the weiszfeld procedure, Locat. Sci., 3, 275-279, (1995) · Zbl 0916.90178
[19] Drezner, Z.: A general global optimization approach for solving location problems in the plane. J. Global Optim. 37(2), 305-319 (2007) · Zbl 1138.90010
[20] Drezner, Z., Hamacher, H.W. (eds.): Facility Location: Applications and Theory. Springer, New York (2002) · Zbl 0988.00044
[21] Drezner, Z; Nickel, S, Solving the ordered one-Median problem in the plane, Eur. J. Oper. Res., 195, 46-61, (2009) · Zbl 1161.90009
[22] Drezner, Z; Nickel, S, Constructing a DC decomposition for ordered Median problems, J. Global Optim., 195, 187-201, (2009) · Zbl 1191.90043
[23] Eckhardt, U, Weber’s problem and weiszfeld’s algorithm in general spaces, Math. Program., 18, 186-196, (1980) · Zbl 0433.65035
[24] Espejo, I; Rodriguez-Chia, AM; Valero, C, Convex ordered Median problem with \(ℓ _p\)-norms, Comput. Oper. Res., 36, 2250-2262, (2009) · Zbl 1158.90375
[25] Harris, B, Speeding up iterative algorithms-the generalized Weber problem, J. Reg. Sci., 16, 411-413, (1976)
[26] Helton, J.W., Nie, J.: Semidefinite representation of convex sets. Math. Program. 122(1), 21-64 (2010) · Zbl 1192.90143
[27] Kalcsics, J; Nickel, S; Puerto, J, Multi-facility ordered Median problems: a further analysis, Networks, 41, 1-12, (2003) · Zbl 1026.90056
[28] Kalcsics, J; Nickel, S; Puerto, J; Tamir, A, Algorithmic results for ordered Median problems defined on networks and the plane, Oper. Res. Lett., 30, 149-158, (2002) · Zbl 1010.90036
[29] Kuhn, HW, A note on fermat’s problem, Math. Program., 4, 98-107, (1973) · Zbl 0255.90063
[30] Katz, IN, Local convergence in fermat’s problem, Math. Program., 6, 26, (1974) · Zbl 0291.90069
[31] Katz, IN, On the convergence of a numerical scheme for solving some locational equilibrium problems, SIAM J. Appl. Math., 17, 1224-1231, (1969) · Zbl 0187.18001
[32] Toh, K.-C., Todd, M.J., Tütüncü, R.H.: On the implementation and usage of SDPT3—A Matlab software package for semidefinite-quadratic-linear programming, version 4.0. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science, vol. 166, pp. 715-754. Springer (2012) · Zbl 1334.90117
[33] Koulaei, M.H., Terlaky, T.: On the complexity analysis of a Mehrotra-type primal-dual feasible algorithm for semidefinite optimization. Optim. Method. Softw. 25(3), 467-485 (2010) · Zbl 1220.90082
[34] Lasserre, JB, Moments and sums of squares for polynomial optimization and related problems, J. Global Optim., 45, 39-61, (2009) · Zbl 1177.90324
[35] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)
[36] Mittelmann, HD, The state-of-the-art in conic optimization software, SIAM J. Optim., 166, 671-686, (2012) · Zbl 1334.90112
[37] Marín, A; Nickel, S; Puerto, J; Velten, S, A flexible model and efficient solution strategies for discrete location problems, Discret. Appl. Math., 157, 1128-1145, (2009) · Zbl 1163.90609
[38] Mehrotra, S, On the implementation of a (primal-dual) interior point method, SIAM. J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[39] Morris, JG; Verdini, WA, Minisum l p distance location problems solved via a perturbed problem and weiszfeld’s algorithm, Oper. Res., 27, 1180-1188, (1979) · Zbl 0442.90023
[40] Morris, JG, Convergence of the weiszfeld algorithm for Weber problems using a generalized “distance” function, Oper. Res., 29, 37-48, (1981) · Zbl 0452.90023
[41] Nickel, S; Puerto, J, A unified approach to network location problems, Networks, 34, 283-290, (1999) · Zbl 0948.90086
[42] Nickel, S., Puerto, J.: Facility Location: A Unified Approach. Springer, New York (2005) · Zbl 1229.90001
[43] Ostresh, LM, On the convergence of a class of iterative methods for solving the Weber location problem, Oper. Res., 26, 597-609, (1978) · Zbl 0396.90073
[44] Puerto, J; Fernández, FR, Geometrical properties of the symmetric single facility location problem, J. Nonlinear Convex Anal., 1, 321-342, (2000) · Zbl 0974.90009
[45] Puerto, J; Rodriguez-Chia, AM, Location of a moving service facility, Math. Methods Oper. Res., 49, 373-393, (1999) · Zbl 0941.90047
[46] Puerto, J; Rodriguez-Chia, AM, New models for locating a moving service facility, Math. Methods Oper. Res., 63, 31-51, (2006) · Zbl 1103.90063
[47] Puerto, J; Tamir, A, Locating tree-shaped facilities using the ordered Median objective, Math. Program., 102, 313-338, (2005) · Zbl 1079.90081
[48] Putinar, M, Positive polynomials on compact semi-algebraic sets, Ind. Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[49] Rodríguez-Chía, AM; Espejo, I; Drezner, Z, On solving the planar k-centrum problem with Euclidean distances, Eur. J. Oper. Res., 207, 1169-1186, (2010) · Zbl 1206.90076
[50] Rodríguez-Chía, A.M., Valero, C.: On the global convergence of a generalized iterative procedure for the minisum location problem with \(l_p\) distances for \(p > 2\). Math. Program. 137(1-2), 477-502 (2013) · Zbl 0787.90040
[51] Sturm, JF, Using sedumi 1.02 A Matlab toolbox for optimization over symmetric cones, Optim. Method Softw., 11, 625-653, (1999) · Zbl 0973.90526
[52] Franco, Valero C; Rodriguez-Chia, AM; Espejo Miranda, I, The single facility location problem with average-distances, TOP, 16, 164-194, (2008) · Zbl 1162.90500
[53] Waki, H; Kim, S; Kojima, M; Muramatsu, M, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17, 218-242, (2006) · Zbl 1109.65058
[54] Weber, A.: Uber der Standort der Industrien. University of Chicago, Translated as Alfred Weber’s Theory of the Location of Industries (1909). · Zbl 0017.18007
[55] Weiszfeld, E, Sur le point pour lequel la somme des distances de n points donns est minimum, Tohoku Math. J., 43, 355-386, (1937) · JFM 63.0583.01
[56] Zhang, L, On the convergence of a modified algorithm for the spherical facility location problem, Oper. Res. Lett., 31, 161-166, (2003) · Zbl 1041.90024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.