A primal-dual algorithm for the Fermat-Weber problem involving mixed gauges.(English)Zbl 0641.90034
Summary: We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed byJ. E. Spingarn [Appl. Math. Optimization 10, 247-265 (1983;Zbl 0524.90072)] simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal location can be obtained from the dual solution by making use of optimality conditions.
When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonempty interior and a counterexample to finite termination is given in case where this property is violated.
Finally, numerical results are reported and we discuss possible extensions of these results.
When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonempty interior and a counterexample to finite termination is given in case where this property is violated.
Finally, numerical results are reported and we discuss possible extensions of these results.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90C90 | Applications of mathematical programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
proximal point algorithm;Fermat-Weber location problem;mixed gauges;partial inverse method;polyhedral gaugesCitations:
Zbl 0524.90072Cite
Full Text:DOI
References:
| [1] | R.D. Armstrong, ”A primal simplex algorithm to solve a rectilinear distance facility location problem,”Naval Research Logistics Quarterly 24 (1977) 619–626. ·Zbl 0372.90080 ·doi:10.1002/nav.3800240409 |
| [2] | L. Cooper and I.N. Katz, ”The Weber problem revisited,”Computers and Mathematics with Applications 7 (1981) 225–234. ·Zbl 0457.65044 ·doi:10.1016/0898-1221(81)90082-1 |
| [3] | P.H. Calamai and A.R. Conn, ”A stable algorithm for solving the multifacility location problem involving Euclidean distances,”SIAM Journal on Scientific and Statistical Computing 1 (1980) 512–526. ·Zbl 0469.65040 ·doi:10.1137/0901037 |
| [4] | P.H. Calamai and A.R. Conn, ”A second order method for solving the continuous multifacility location problem,” in: G.A. Watson, ed.,Numerical Analysis: Proceedings of the Ninth Biennial Conference. Dundee, Scotland, Lecture Notes in Mathematics 912 (Springer-Verlag, Berlin, Heidelberg and New York, 1982), pp. 1–25. ·Zbl 0485.65013 |
| [5] | F. Cordellier and J.C. Fiorot, ”On the Fermat-Weber problem with convex cost functions,”Mathematical Programming 14 (1978) 295–311. ·Zbl 0374.90057 ·doi:10.1007/BF01588972 |
| [6] | A. Dax, ”The use of Newton’s method for solving Euclidean multifacility location problems,” Tech. Report. Hydrological Service (Jerusalem, 1985). |
| [7] | P.D. Dowling and R.F. Love, ”Bounding methods for facilities location algorithms,” Research and Working Paper Series No. 219, McMaster University (Hamilton, Ontario, 1984). ·Zbl 0614.90052 |
| [8] | P.D. Dowling and R.F. Love, ”An evaluation of the dual as a lower bound in facilities location problems,” Research and Working Paper Series No. 236, McMaster University (Hamilton, Ontario, 1985). |
| [9] | R. Durier, ”On efficient points and Fermat-Weber problem,” Working Paper, Université de Bourgogne, (Dijon, France, 1984). |
| [10] | R. Durier, ”Weighting factor results in vector optimization,” Working Paper, Université de Bourgogne (Dijon, France, 1984). |
| [11] | R. Durier and C. Michelot, ”Geometrical properties of the Fermat-Weber problem,”European Journal of Operational Research 20 (1985) 332–343. ·Zbl 0564.90013 ·doi:10.1016/0377-2217(85)90006-2 |
| [12] | R. Durier and C. Michelot, ”Sets of efficient points in a normed space,”Journal of Mathematical Analysis and Applications 117 (1986), 506–528. ·Zbl 0605.49020 ·doi:10.1016/0022-247X(86)90237-4 |
| [13] | U. Eckhardt, ”Theorems on the dimension of convex sets,”Linear Algebra and its Applications 12 (1975) 63–76. ·Zbl 0317.52004 ·doi:10.1016/0024-3795(75)90127-5 |
| [14] | D.J. Elzinga and D.W. Hearn, ”On stopping rules for facilities location algorithms,”IIE Transactions 15 (1983) 81–83. ·doi:10.1080/05695558308974616 |
| [15] | R.L. Francis and J.M. Goldstein, ”Location theory: A selective bibliography,”Operations Research 22 (1974) 400–410. ·Zbl 0274.90028 ·doi:10.1287/opre.22.2.400 |
| [16] | R.L. Francis and J.A. White,Facility Layout and Location: An Analytical Approach (Prentice-Hall, Englewood Cliffs, NJ, 1974). |
| [17] | I.N. Katz, ”Local convergence in Fermat’s problem,”Mathematical Programming 6 (1974), 89–104. ·Zbl 0291.90069 ·doi:10.1007/BF01580224 |
| [18] | H.W. Kuhn, ”A note on Fermat’s problem,”Mathematical Programming 4 (1973) 98–107. ·Zbl 0255.90063 ·doi:10.1007/BF01584648 |
| [19] | H.W. Kuhn and R.E. Kuenne, ”An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics”,Journal of Regional Science 4 (1962) 21–23. ·doi:10.1111/j.1467-9787.1962.tb00902.x |
| [20] | R.F. Love and W.Y. Yeong, ”A stopping rule for facilities location algorithms,”AIIE Transactions 13 (1981) 357–362. |
| [21] | L.M. Ostresch, ”On the convergence of a class of iterative methods for solving the Weber location problem,”Operations Research 26 (1978) 597–609. ·Zbl 0396.90073 ·doi:10.1287/opre.26.4.597 |
| [22] | L.M. Ostresh, ”Convergence and descent in the Fermat location problem,”Transportation Science 12 (1978) 153–164. ·doi:10.1287/trsc.12.2.153 |
| [23] | M.L. Overton, ”A quadratically convergent method for minimizing a sum of Euclidean norms,”Mathematical Programming 27 (1983) 34–63. ·Zbl 0536.65053 ·doi:10.1007/BF02591963 |
| [24] | A. Planchart and A.P. Hurter, ”An efficient algorithm for the solution of Weber problem with mixed norms,”SIAM Journal on Control 13 (1975) 650–665. ·doi:10.1137/0313036 |
| [25] | F. Plastria, ”Continuous location problems solved by cutting planes,” Working Paper, Vrije Universiteit brussels, (Bruxelles, 1982). |
| [26] | R.T. RockafellarConvex Analysis, (Princeton University Press, Princeton, NJ, 1970). |
| [27] | R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898. ·Zbl 0358.90053 ·doi:10.1137/0314056 |
| [28] | J.E. Spingarn, ”Partial inverse of a monotone operator,”Applied Mathematics and Optimization 10 (1983) 247–265. ·Zbl 0524.90072 ·doi:10.1007/BF01448388 |
| [29] | J.E. Spingarn, ”A primal-dual projection method for solving systems of linear inequalities,”Linear Algebra and its Applications 65 (1985) 45–62. ·Zbl 0564.65044 ·doi:10.1016/0024-3795(85)90086-2 |
| [30] | J.E. Ward and R.E. Wendell, ”Using block norms for location modeling,”Operations Research 33 (1985) 1074–1090. ·Zbl 0582.90026 ·doi:10.1287/opre.33.5.1074 |
| [31] | E. Weiszfeld, ”Sur le point pour lequel la somme des distances den points donnés est minimum,”The Tôhoku Mathematical Journal 43 (1937) 355–386. ·JFM 63.0583.01 |
| [32] | R.E. Wendell and E.L. Peterson, ”A dual approach for obtaining lower bounds to the Weber problem,”Journal of Regional Science 24 (1984) 219–228. ·doi:10.1111/j.1467-9787.1984.tb01033.x |
| [33] | C. Witzgall, ”Optimal location of a central facility: Mathematical models and Concepts,” National Bureau of Standards, Report 8388 (Washington, 1964). |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
