Skip to main content
SpringerLink
Log in

Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The minisum multifacility location problem is regarded as hard to solve, due to nondifferentiabilities whenever two or more facilities coincide. Recently, several authors have published conditions for the coincidence of facilities. In the present paper, these conditions are extended to more general location problems and improved with respect to new sufficient coincidence conditions for location problems with mixed asymmetric gauges. Some of these conditions are formulated only in terms of the given weights and certain values from a preprocessing step.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. MINKOWSKI, H., Gesammelte Abhandlungen, Vol. 2, Chelsea Publishing Company, New York, New York, 1967.

    Google Scholar 

  2. CALAMAI, P. H., and CONN, A. R., A Projected Newton Method for l p -Norm Location Problems, Mathematical Programming, Vol. 38, pp. 75–109, 1987.

    Google Scholar 

  3. PLASTRIA, F., Continuous Location Problems, Facility Location: A Survey of Applications and Methods, Edited by Z. Drezner, Springer Verlag, New York, New York, pp. 225–262, 1995.

    Google Scholar 

  4. WARD, J. E., and WENDELL, R. E., Using Block Norms for Location Modelling, Operation Research, Vol. 33, pp. 1074–1090, 1985.

    Google Scholar 

  5. JUEL, H., and LOVE, R. F., Sufficient Conditions for Optimal Facility Locations to Coincide, Transportation Science, Vol. 14, pp. 125–129, 1980.

    Google Scholar 

  6. LEFEBVRE, O., MICHELOT, C., and PLASTRIA, F., Sufficient Conditions for Coincidence in Minisum Multifacility Location Problems with a General Metric, Operation Research, Vol. 39, pp. 437–442, 1991.

    Google Scholar 

  7. FLIEGE, J., Nichtdiskrete Multilokationsprobleme: Koinzidenzbedingungen und Effiziente Punkte, Diplomarbeit, Universität Dortmund, Dortmund, Germany, 1993.

    Google Scholar 

  8. PLASTRIA, F., When Facilities Coincide: Exact Optimality Conditions in Multifacility Location, Journal of Mathematical Analysis and Applications, Vol. 169, pp. 476–498, 1992.

    Google Scholar 

  9. IDRISSI, H., LEFEBVRE, O., and MICHELOT, C., Duality for Constrained Multifacility Location Problems with Mixed Norms and Applications, Annals of Operations Research, J. C. Baltzer AG Scientific Publishing Company, Basel, Switzerland, Vol. 18, pp. 71–92, 1989.

    Google Scholar 

  10. MICHELOT, C., and LEFEBVRE, O., A Primal-Dual Algorithm for the Fermat-Weber Problem Involving Mixed Gauges, Mathematical Programming, Vol. 39, pp. 319–335, 1987.

    Google Scholar 

  11. PLASTRIA, F., Solving General Continuous Single-Facility Location Problems by Cutting Planes, European Journal of Operation Research, Vol. 29, pp. 98–110, 1987.

    Google Scholar 

  12. EYSTER, J. W., WHITE, J. A., and WIERWILLE, W. W., On Solving Multifacility Location Problems Using a Hyperboloid Approximation Procedure, AIIE Transactions, Vol. 5, pp. 1–6, 1973.

    Google Scholar 

  13. MORRIS, J. G., and VERDINI, W. A., Minisum l p -Distance Location Problems Solved via a Perturbed Problem and Weizsfeld's Algorithm, Operation Research, Vol. 27, pp. 1180–1188, 1979.

    Google Scholar 

  14. FRENK, J. B. G., and KLEIJN, M. J., On Miehle's Algorithm and the Perturbed ℒ p -Distance Multifacility Location Problem, Discussion Paper TI 94–54, Tinbergen Institute, Rotterdam, Netherlands, 1994.

    Google Scholar 

  15. FRENK, J. B. G., and KLEIJN, M. J., On a Class of Algorithms Solving the Multifacility Location Problem with Perturbed L p -Distances, Discussion Paper TI 94–74, Tinbergen Institute, Rotterdam, Netherlands, 1994.

    Google Scholar 

  16. FRENK, J. B. G., MELO, M. T., and ZHANG, S., The Weiszfeld Method in Single Facility Location, Investigação Operacional, Vol. 14, pp. 35–59, 1994.

    Google Scholar 

  17. DURIER, R., and MICHELOT, C., Geometrical Properties of the Fermat-Weber Problem, European Journal of Operation Research, Vol. 20, pp. 332–343, 1985.

    Google Scholar 

  18. BERENS, W., The Suitability of the Weighted l p -Norm in Estimating Actual Road Distances, European Journal of Operation Research, Vol. 34, pp. 39–43, 1988.

    Google Scholar 

  19. PLASTRIA, F., A Majority Theorem for Fermat-Weber Problems in Quasimetric Spaces with Applications to Semidirected Networks, Proceedings of the 6th Meeting of the EURO Working Group on Locational Analysis, Puerto de la Cruz, Tenerife, Spain, pp. 153–165, 1992.

  20. PLASTRIA, F., Private Communication, 1993.

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik, University of Dortmund, Dortmund, Germany

    J. Fliege (Assistant)

Authors
  1. J. Fliege
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fliege, J. Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems. Journal of Optimization Theory and Applications 94, 365–380 (1997). https://doi.org/10.1023/A:1022635712721

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022635712721

Search

Navigation