zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand. (English) Zbl 1243.90097
Summary: We are interested in locations of multiple facilities in the plane with the aim of minimizing the sum of weighted distance between these facilities and regional customers, where the distance between a facility and a regional customer is evaluated by the farthest distance from this facility to the demand region. By applying the well-known location-allocation heuristic, the main task for solving such a problem turns out to solve a number of constrained Weber problems (CWPs). This paper focuses on the computational contribution in this topic by developing a variant of the classical Barzilai-Borwein (BB) gradient method to solve the reduced CWPs. Consequently, a hybrid Cooper type method is developed to solve the problem under consideration. Preliminary numerical results are reported to verify the evident effectiveness of the new method.
MSC:
90B85Continuous location
References:
[1]Barzilai, J., Borwein, J.M.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[2]Bennett, C.D., Mirakhor, A.: Optimal facility location with respect to several regions. J. Reg. Sci. 14, 131–136 (1974) · doi:10.1111/j.1467-9787.1974.tb00435.x
[3]Birgin, E.G., Martinez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods for convex sets. SIAM J. Optim. 10, 1196–1211 (2000) · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[4]Brimberg, J., Wesolowsky, G.O.: Minisum location with closest Euclidean distances. Ann. Oper. Res. 111, 151–165 (2002) · Zbl 1040.90020 · doi:10.1023/A:1020901719463
[5]Brimberg, J., Wesolowsky, G.O.: Locating facilities by minimax relative to closest points of demand areas. Comput. Oper. Res. 29, 625–636 (2002) · Zbl 1001.90042 · doi:10.1016/S0305-0548(00)00106-4
[6]Carrizosa, E., Munoz, M., Puerto, J.: The Weber problem with regional demand. Eur. J. Oper. Res. 104, 358–365 (1998) · Zbl 0955.90063 · doi:10.1016/S0377-2217(97)00190-2
[7]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 · doi:10.1007/BF01587094
[8]Cooper, L.: Heuristic methods for location-allocation problems. SIAM Rev. 6, 37–53 (1964) · doi:10.1137/1006005
[9]Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005) · Zbl 1068.65073 · doi:10.1007/s00211-004-0569-y
[10]Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002) · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[11]Dai, Y.H., Zhang, H.C.: Adaptive two-point stepsize gradient algorithm. Numer. Algorithms 27, 377–385 (2001) · Zbl 0992.65063 · doi:10.1023/A:1013844413130
[12]Dai, Y.H., Yuan, J.Y., Yuan, Y.X.: Modified two-point stepsize gradient methods for unconstrained optimization. Comput. Optim. Appl. 22, 103–109 (2002) · Zbl 1008.90056 · doi:10.1023/A:1014838419611
[13]Dai, Y.H., Hager, W.W., Zhang, H.C.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26, 604–627 (2006) · Zbl 1147.65315 · doi:10.1093/imanum/drl006
[14]Drezner, Z.: Facility Location: A Survey of Applications and Methods. Springer, New York (1995)
[15]Drezner, Z., Wesolowsky, G.O.: Optimal location of a facility relative to area demands. Nav. Res. Logist. Q. 27, 199–206 (1980) · Zbl 0443.90028 · doi:10.1002/nav.3800270204
[16]Drezner, Z., Wesolowsky, G.O.: Location models with groups of demand points. Inf. Syst. Oper. Res. 38, 359–372 (2000)
[17]Fletcher, R.: Low storage methods for unconstrained optimization. Lect. Appl. Math., 26, 165–179 (1999)
[18]Fletcher, R.: On the Barzilai-Borwein method. In: Qi, L.Q., Teo, K., Yang, X.Q. (eds.) Optimization and Control with Applications (Applied Optimization), pp. 235–256. Springer, New York (2001)
[19]Friedlander, A., Martinez, J.M., Molina, B., Raydan, M.: Gradient method with retards and generalizations. SIAM J. Numer. Anal. 36, 275–289 (1999) · Zbl 0940.65032 · doi:10.1137/S003614299427315X
[20]Fukunaga, K.: Introduction to Statistical Pattern Recognition. Academic Press, Boston (1990)
[21]Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput. Optim. Appl. 23, 143–169 (2002) · Zbl 1028.90061 · doi:10.1023/A:1020587701058
[22]Hager, W.W., Zhang, H.C.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17, 526–557 (2006) · Zbl 1165.90570 · doi:10.1137/050635225
[23]Hager, W.W., Mair, B.A., Zhang, H.C.: An affine-scaling interior-point CBB method for box-constrained optimization. Math. Program. 119, 1–32 (2009) · Zbl 1168.90007 · doi:10.1007/s10107-007-0199-0
[24]Hansen, P., Peeters, D., Thisse, J.F.: An algorithm for a constrained Weber problem. Manag. Sci. 28, 1285–1295 (1982) · Zbl 0512.90038 · doi:10.1287/mnsc.28.11.1285
[25]Jiang, J.L., Xu, Y.: Minisum location problem with farthest Euclidean distances. Math. Methods Oper. Res. 64, 285–308 (2006) · Zbl 1132.90344 · doi:10.1007/s00186-006-0084-2
[26]Jiang, J.L., Yuan, X.M.: A heuristic algorithm for constrained multi-source Weber problem–the variational inequality approach. Eur. J. Oper. Res. 187, 357–370 (2008) · Zbl 1149.90091 · doi:10.1016/j.ejor.2007.02.043
[27]Kuhn, H.W.: A note on Fermat’s problem. Math. Program. 4, 98–107 (1973) · Zbl 0255.90063 · doi:10.1007/BF01584648
[28]Kuhn, H.W., Kuenne, R.E.: An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics. J. Reg. Sci. 4, 21–33 (1962) · doi:10.1111/j.1467-9787.1962.tb00902.x
[29]Love, R.F.: A computational procedure for optimally locating a facility with respect to several rectangular regions. J. Reg. Sci. 12, 233–242 (1972) · doi:10.1111/j.1467-9787.1972.tb00345.x
[30]Love, R.F., Morris, J.G., Wesolowsky, G.O.: Facilities Location: Models and Methods. North-Holland, Amsterdam (1988)
[31]Michelot, C., Lefebvre, O.: A primal-dual algorithm for the Fermat-Weber problem involving mixed gauges. Math. Program. 39, 319–335 (1987) · Zbl 0641.90034 · doi:10.1007/BF02592080
[32]Nickel, S., Puerto, J.: An approach to location models involving sets as existing facilities. Math. Oper. Res., 28, 693–715 (2003) · Zbl 1082.90059 · doi:10.1287/moor.28.4.693.20521
[33]Ostresh, L.M.: An efficient algorithm for solving the two-center location-allocation problem. J. Reg. Sci. 15, 209–216 (1975) · doi:10.1111/j.1467-9787.1975.tb00921.x
[34]Ostresh, L.M.: On the convergence of a class of iterative methods for solving the Weber location problem. Oper. Res. 26, 597–609 (1978) · Zbl 0396.90073 · doi:10.1287/opre.26.4.597
[35]Rado, F.: The Euclidean multifacility location problem. Oper. Res. 36, 485–492 (1988) · Zbl 0651.90024 · doi:10.1287/opre.36.3.485
[36]Raydan, M.: On the Barzilai and Borwein choice of step length for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[37]Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimzation problem. SIAM J. Optim. 7, 26–33 (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[38]Raydan, M., Svaiter, B.F.: Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21, 155–167 (2002) · Zbl 0988.90049 · doi:10.1023/A:1013708715892
[39]Stone, R.E.: Some average distance results. Transp. Sci. 25, 83–91 (1991) · doi:10.1287/trsc.25.1.83
[40]Suzuki, A., Drezner, Z.: The p-center location problem in an area. Location Sci. 4, 69–82 (1996) · Zbl 0917.90233 · doi:10.1016/S0966-8349(96)00012-5
[41]Vardi, Y., Zhang, C.H.: A modified Weiszfeld algorithm for the Fermat-Weber location problem. Math. Program., 90, 559–566 (2001) · doi:10.1007/PL00011435
[42]Weiszfeld, E.: Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math. J., 43, 355–386 (1937)
[43]Wesolowsky, G.O., Love, R.F.: Location of facilities with rectangular distances among point and area destinations. Nav. Res. Logist. Q. 18, 83–90 (1971) · Zbl 0216.54202 · doi:10.1002/nav.3800180107
[44]Zhang, H.C., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM Journal on Optimization 14, 1043–1056 (2004) · Zbl 1073.90024 · doi:10.1137/S1052623403428208
[45]Zhang, H.C., Hager, W.W.: PCBB: a projected cyclic Barzilai-Borwein algorithm for box constrained optimization. In: Hager, W.W., Huang, S.J., Pardalos, P.M., Prokopyev, O.A. (eds.) Multiscale Optimization Methods and Applications, pp. 387–392. Springer, New York (2005)