×

Kantorovich-Rubinstein distance minimization: application to location problems. (English) Zbl 1442.90119

Velásquez-Bermúdez, Jesús M. (ed.) et al., Large scale optimization in supply chains and smart manufacturing. Theory and applications. Cham: Springer. Springer Optim. Appl. 149, 59-68 (2019).
Summary: The paper considers optimization algorithms for location planning, which specifies positions of facilities providing demanded services. Examples of facilities include hospitals, restaurants, ambulances, retail and grocery stores, schools, and fire stations. We reduced the initial problem to approximation of a discrete distribution with a large number of atoms by some other discrete distribution with a smaller number of atoms. The approximation is done by minimizing the Kantorovich-Rubinstein distance between distributions. Positions and probabilities of atoms of the approximating distribution are optimized. The algorithm solves a sequence of optimization problems reducing the distance between distributions. We conducted a case study using Portfolio Safeguard (PSG) optimization package in MATLAB environment.
For the entire collection see [Zbl 1427.90005].

MSC:

90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] American Optimal Decisions (AORDA), Portfolio Safeguard (PSG), http://www.aorda.com
[2] Ahmadian S., Norouzi-Fard A., Svensson O., Ward, J. (2017) Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), https://doi.org/10.1109/FOCS.2017.15. · doi:10.1109/FOCS.2017.15
[3] Chen K. (2006) On k-Median Clustering in High Dimensions, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 1177-1185. · Zbl 1192.68882
[4] Chung J.K., Kannappan P.L., Ng C.T., Sahoo P.K. (1989) Measures of Distance between Probability Distributions, Journal of mathematical analysis and applications, Vol. 138, pp. 280-292. · Zbl 0669.60025 · doi:10.1016/0022-247X(89)90335-1
[5] David A., Vassilvitskii S. (2007) K-means++: The Advantages of Careful Seeding, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 07, 1027-1035. · Zbl 1302.68273
[6] Deng Y., Du W. (2009) The Kantorovich Metric in Computer Science: A Brief Survey, Electronic Notes in Theoretical Computer Science, Elsevier, Vol. 253, Iss. 3, 73-82. https://doi.org/10.1016/j.entcs.2009.10.006. · doi:10.1016/j.entcs.2009.10.006
[7] Fayed A., Atiya A. (2013) A Mixed Breadth-depth First Strategy for the Branch and Bound Tree of Euclidean k-Center Problems, Computational Optimization and Applications, Springer, Vol. 30, Iss. 2, https://doi.org/10.1007/s10589-012-9503-x. · Zbl 1271.90094 · doi:10.1007/s10589-012-9503-x
[8] Fernandes I.F., Aloise D., Aloise D.J., Hansen P., Liberti L. (2014) On the Weber facility location problem with limited distances and side constraints, Optimization Letters, Springer, Vol. 8, Iss. 2, 407-424. https://doi.org/10.1007/s11590-012-0538-9 · Zbl 1294.90033 · doi:10.1007/s11590-012-0538-9
[9] Geunes J., Pardalos P.M. (Editors) (2005) Supply Chain Optimization. Applied optimization, Springer, Vol. 98, 414. · Zbl 1078.90002
[10] Kantorovich L.V. (1942) On the Translocation of Masses, Dokl. Akad. Nauk SSSR, Vol. 37, N-s. 7-8, 227-229.
[11] Kantorovich L.V. (1948) On a Problem of Monge, Uspekhi Mat. Nauk, Vol. 3, No. 2, 225-226.
[12] Kantorovich L.V., Rubinstein G.Sh. (1958) On a Space of Totally Additive Functions, Vestn. Lening. Univ., Vol. 13, No. 7, 52-59. · Zbl 0082.11001
[13] Kantorovich L. (1958) On the Translocation of Masses, Management Science, Vol. 5, No. 1, 1-4. · Zbl 0995.90585 · doi:10.1287/mnsc.5.1.1
[14] Kumar A. (2016) Capacitated k-Center Problem with Vertex Weights, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), No. 8, 1-14. · Zbl 1391.68042
[15] Lattanzi S., Vassilvitskii S. (2017) Consistent k-Clustering, Proceedings of the 34th International Conference on Machine Learning, Sydney, Australia, PMLR 70.
[16] Li S., Svensson O. (2016) Approximating k-Median via Pseudo-approximation, SIAM J. Comput., 45(2), 530-547. · Zbl 1338.90346 · doi:10.1137/130938645
[17] Meloa M.T., Nickelab S., Saldanha da Gamac F. (2006) Dynamic Multi-commodity Capacitated Facility Location: a Mathematical Modeling Framework for Strategic Supply Chain Planning, Computers and Operations Research, Vol. 33, Iss. 1, 181-208. · Zbl 1077.90006
[18] Pavlikov K., Uryasev S. (2018) CVaR Distance Between Univariate Probability Distributions and Approximation Problems, Annals of Operations Research, Vol. 262, Iss. 1, 67-88. https://doi.org/10.1007/s10479-017-2732-8 · Zbl 1391.62025 · doi:10.1007/s10479-017-2732-8
[19] Pflug G.Ch., Pichler A. (2011) Approximations for Probability Distributions and Stochastic Optimization Problems, Stochastic Optimization Methods in Finance and Energy, Springer, Vol. 163, 343-387. · Zbl 1405.90093
[20] Rachev S.T., Stoyanov S.V., Fabozzi F.G. (2011) A Probability Metrics Approach to Financial Risk Measures, New York: John Wiley & Sons. · doi:10.1002/9781444392715
[21] Vershik A.M. (2006) Kantorovich Metric: Initial History and Little-Known Applications, Journal of Mathematical Sciences, Springer, Vol. 133, Iss. 4, 1410-1417. · Zbl 1090.28009
[22] Zarinbal M. (2009) Distance Functions in Location Problems, Facility Location. Contributions to Management Science, Springer, 5- · doi:10.1007/978-3-7908-2151-2_1
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.