Abstract

We consider the problem of locating a facility amongst a given collection of attraction and repulsion points. The goal is to find a location x in the Euclidean space Rn\mathbb{R}^n for a facility, such that the difference between the weighted sum of distances from x to the attraction points and the weighted sum of distances to the repulsion points is minimized. The corresponding objective function constitutes as a D.C. function. Based on the duality theory by Toland and Singer for the class of D.C. programs, we formulate a dual problem to the given location problem. Taking into account the special structure of the location problem, we present geometrical properties of the model, give conditions for the existence of an optimal solution, obtain duality results, describe the relationship between primal and dual elements, and formulate an algorithm which determines exact solutions for the location problem by reducing this non-convex optimization problem to a finite number of linear programs.

Author information

Contact details are reproduced from the original publication and may be historical.

Andrea Wagner

Dept. of Finance, Accounting and Statistics, Institute for Statistics and Mathematics,
Vienna University of Economics and Business, Welthandelsplatz 1, 1020 Vienna, Austria

andrea.wagner@wu.ac.at

Juan-Enrique Martínez-Legaz

Dep. d'Economia i d'Història Econòmica, Universitat Autónoma de Barcelona, 08193 Bellaterra, Spain
and: MOVE (Markets, Organizations and Votes in Economics)

JuanEnrique.Martinez.Legaz@uab.cat

Keywords

  • Locational analysis
  • conjugate duality
  • obnoxious facilities
  • D.C. optimization
  • geometric duality
  • linear vector optimization

References

  1. A. D. Aleksandrov: On the surfaces representable as difference of convex functions, Izv. Akad. Nauk Kazakh. SSR 3 (1949) 3–20 (in Russian).Google Scholar
  2. A. D. Aleksandrov: Surfaces representable as difference of convex functions, Dokl. Akad. Nauk SSSR, n. Ser. 72 (1950) 613–616 (in Russian).Google Scholar
  3. J. Borwein, A. Lewis: Convex Analysis and Nonlinear Optimization, 2nd Ed., Springer, New York (2006).https://doi.org/10.1007/978-0-387-31256-9Google Scholar
  4. P. C. Chen, P. Hansen, B. Jaumard, H. Tuy: Weber’s problem with attraction and repulsion, J. Region. Sci. 32 (1992) 467–486.https://doi.org/10.1111/j.1467-9787.1992.tb00200.xGoogle Scholar
  5. R. L. Church, R. S. Garfinkel: Locating an obnoxious facility on a network, Transp. Sci. 12(2) (1978) 107–118.https://doi.org/10.1287/trsc.12.2.107Google Scholar
  6. Z. Drezner (ed.): Facility Location: A Survey of Applications and Methods, Springer Series in Operations Research, Springer, New York (1995).Google Scholar
  7. Z. Drezner, H. W. Hamacher (eds.): Facility Location: Application and Theory, Contributions to Management Science, Physica, Heidelberg (2002).https://doi.org/10.1007/978-3-642-56082-8Google Scholar
  8. Z. Drezner, G. O. Wesolowsky: The Weber problem on the plane with some negative weights, INFOR 29(2) (1991) 87–99.https://doi.org/10.1080/03155986.1991.11732158Google Scholar
  9. R. Durier, C. Michelot: Geometrical properties of the Fermat-Weber problem, Eur. J. Oper. Res. 20(3) (1985) 332–343.https://doi.org/10.1016/0377-2217(85)90006-2Google Scholar
  10. A. J. Goldman: Concepts of optimal location for partially noxious facilities, Bull. Oper. Res. Soc. Amer. 23(1) (1975) B–31.Google Scholar
  11. H. W. Hamacher: Mathematische Lösungsverfahren für planare Standortprobleme, Vieweg, Wiesbaden (1995).https://doi.org/10.1007/978-3-663-01968-8Google Scholar
  12. P. Hartman: On functions representable as a difference of convex functions, Pac. J. Math. 9(3) (1959) 707–713.https://doi.org/10.2140/pjm.1959.9.707Google Scholar
  13. F. Heyde: Geometric duality for convex vector optimization problems, J. Convex Analysis 20(3) (2013) 813–832.https://doi.org/10.68381/jca20044Google Scholar
  14. J. B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms II. Advanced Theory and Bundle Methods, Grundlehren der Mathematischen Wissenschaften 306, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-06409-2Google Scholar
  15. R. Horst, N. V. Thoai: DC programming: overview, J. Optimization Theory Appl. 103(1) (1999) 1–43.https://doi.org/10.1023/A:1021765131316Google Scholar
  16. R. F. Love, J. G. Morris, G. O. Wesolowsky (eds.): Facilities Location: Models and Methods, North-Holland, Amsterdam (1988).Google Scholar
  17. C. D. Maranas, C. Floudas: A global optimization method for Weber’s problem with attraction and repulsion, in: Large Scale Optimization (Gainesville, 1993), W. W. Hager, D. W. Hearn, P. M. Pardalos (eds.), Kluwer, Dordrecht (1994) 259–285.https://doi.org/10.1007/978-1-4613-3632-7_14Google Scholar
  18. J. E. Martínez-Legaz: Generalized conjugation and related topics, in: Generalized Convexity and Fractional Programming with Economic Applications (Pisa, 1988), A. Cambini et al. (ed.), Lecture Notes in Econom. and Math. Systems 345, Springer, Berlin (1990) 168–197.https://doi.org/10.1007/978-3-642-46709-7_13Google Scholar
  19. J. E. Martínez-Legaz, A. Seeger: A formula on the approximate subdifferential of the difference of convex functions, Bull. Aust. Math. Soc. 45(1) (1992) 37–41.https://doi.org/10.1017/S0004972700036984Google Scholar
  20. J. E. Martínez-Legaz, I. Singer: An extension of d.c. duality theory, with an appendix on ∗-subdifferentials, Optimization 42(1) (1997) 9–37.https://doi.org/10.1080/02331939708844348Google Scholar
  21. J. E. Martínez-Legaz, M. Volle: Duality in D.C. programming: the case of several D.C. constraints, J. Math. Anal. Appl. 237(2) (1999) 657–671.https://doi.org/10.1006/jmaa.1999.6496Google Scholar
  22. J. J. Moreau: Fonctionnelles convexes, Séminaire Jean Leray 2 (1966–67) 1–108.Google Scholar
  23. S. Nickel, E. M. Dudenhöffer: Weber’s problem with attraction and repulsion under polyhedral gauges, J. Glob. Optim. 11(4) (1997) 409–432.https://doi.org/10.1023/A:1008235107372Google Scholar
  24. R. T. Rockafellar: Convex Analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton (1997).Google Scholar
  25. D. Romero-Morales, E. Carrizosa, E. Conde: Semi-obnoxious location models: A global optimization approach, Eur. J. Oper. Res. 102(2) (1997) 295–301.https://doi.org/10.1016/S0377-2217(97)00110-0Google Scholar
  26. I. Singer: A Fenchel-Rockafellar type duality theorem for maximization, Bull. Aust. Math. Soc. 20(2) (1979) 193–198.https://doi.org/10.1017/S0004972700010844Google Scholar
  27. I. Singer: Duality for Nonconvex Approximation and Optimization, CMS Books in Mathematics 24, Springer, New York (2006).https://doi.org/10.1007/0-387-28395-1Google Scholar
  28. J. F. Toland: Duality in nonconvex optimization, J. Math. Anal. Appl. 66(2) (1978) 399–415.https://doi.org/10.1016/0022-247X(78)90243-3Google Scholar
  29. H. Tuy: A general d.c. approach to location problems, in: State of the Art in Global Optimization: Computational Methods and Applications (Princeton, 1995), C. A. Floudas, P. M. Pardalos (eds.), Nonconvex Optimization and its Applications 7, Kluwer, Dordrecht (1996) 413–432.https://doi.org/10.1007/978-1-4613-3437-8_26Google Scholar
  30. H. Tuy: Convex Analysis and Global Optimization, Nonconvex Optimization and its Applications 22, Kluwer, Dordrecht (1998).https://doi.org/10.1007/978-1-4757-2809-5Google Scholar
  31. H. Tuy, F. Al-Khayyal, F. Zhou: A d.c. optimization method for single facility location problems, J. Glob. Optim. 7(2) (1995) 209–227.https://doi.org/10.1007/BF01097061Google Scholar
  32. A. Wagner: A new Duality-Based Approach for the Problem of Locating a Semi-Obnoxious Facility, PhD Thesis, Martin-Luther-University Halle-Wittenberg, Halle/Saale (2014).Google Scholar
  33. A. Weber: Über den Standort der Industrien. Erster Teil: Reine Theorie des Standortes, Mohr, Tübingen (1909).Google Scholar

Suggested citation

A. Wagner, J.-E. Martínez-Legaz, C. Tammer. “Locating a Semi-Obnoxious Facility – A Toland-Singer Duality Based Approach.” Journal of Convex Analysis 23 (2016), No. 4, 1185–1204. https://doi.org/10.68381/jca23044

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2016. Rights now held by Banach Press.