Abstract
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 by J.E. Spingarn, 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 locations 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 nonepty interior and a counterexample to finite termination is given in a case where this property is violated. Finally, numerical results are reported and we discuss possible extensions of these results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.D. Armstrong, “A primal simplex algorithm to solve a rectilinear distance facility location problem,”Naval Research Logistics Quarterly 24 (1977) 619–626.
L. Cooper and I.N. Katz, “The Weber problem revisited,”Computers and Mathematics with Applications 7 (1981) 225–234.
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.
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.
F. Cordellier and J.C. Fiorot, “On the Fermat-Weber problem with convex cost functions,”Mathematical Programming 14 (1978) 295–311.
A. Dax, “The use of Newton's method for solving Euclidean multifacility location problems,” Tech. Report. Hydrological Service (Jerusalem, 1985).
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).
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).
R. Durier, “On efficient points and Fermat-Weber problem,” Working Paper, Université de Bourgogne, (Dijon, France, 1984).
R. Durier, “Weighting factor results in vector optimization,” Working Paper, Université de Bourgogne (Dijon, France, 1984).
R. Durier and C. Michelot, “Geometrical properties of the Fermat-Weber problem,”European Journal of Operational Research 20 (1985) 332–343.
R. Durier and C. Michelot, “Sets of efficient points in a normed space,”Journal of Mathematical Analysis and Applications 117 (1986), 506–528.
U. Eckhardt, “Theorems on the dimension of convex sets,”Linear Algebra and its Applications 12 (1975) 63–76.
D.J. Elzinga and D.W. Hearn, “On stopping rules for facilities location algorithms,”IIE Transactions 15 (1983) 81–83.
R.L. Francis and J.M. Goldstein, “Location theory: A selective bibliography,”Operations Research 22 (1974) 400–410.
R.L. Francis and J.A. White,Facility Layout and Location: An Analytical Approach (Prentice-Hall, Englewood Cliffs, NJ, 1974).
I.N. Katz, “Local convergence in Fermat's problem,”Mathematical Programming 6 (1974), 89–104.
H.W. Kuhn, “A note on Fermat's problem,”Mathematical Programming 4 (1973) 98–107.
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.
R.F. Love and W.Y. Yeong, “A stopping rule for facilities location algorithms,”AIIE Transactions 13 (1981) 357–362.
L.M. Ostresch, “On the convergence of a class of iterative methods for solving the Weber location problem,”Operations Research 26 (1978) 597–609.
L.M. Ostresh, “Convergence and descent in the Fermat location problem,”Transportation Science 12 (1978) 153–164.
M.L. Overton, “A quadratically convergent method for minimizing a sum of Euclidean norms,”Mathematical Programming 27 (1983) 34–63.
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.
F. Plastria, “Continuous location problems solved by cutting planes,” Working Paper, Vrije Universiteit brussels, (Bruxelles, 1982).
R.T. RockafellarConvex Analysis, (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898.
J.E. Spingarn, “Partial inverse of a monotone operator,”Applied Mathematics and Optimization 10 (1983) 247–265.
J.E. Spingarn, “A primal-dual projection method for solving systems of linear inequalities,”Linear Algebra and its Applications 65 (1985) 45–62.
J.E. Ward and R.E. Wendell, “Using block norms for location modeling,”Operations Research 33 (1985) 1074–1090.
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.
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.
C. Witzgall, “Optimal location of a central facility: Mathematical models and Concepts,” National Bureau of Standards, Report 8388 (Washington, 1964).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Michelot, C., Lefebvre, O. A primal-dual algorithm for the fermat-weber problem involving mixed gauges. Mathematical Programming 39, 319–335 (1987). https://doi.org/10.1007/BF02592080
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02592080