УДК 519.8+518.25
MSC: 05C09, 05C12, 05C92
DOI: 10.21538/0134-4889-2025-31-3-77-90
Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019).
В данной работе рассматривается задача размещения предприятий без ограничения на объемы производства. Эта задача является NP-трудной в сильном смысле. Для ее решения предлагается прямо-двойственный полиномиальный приближенный алгоритм с апостериорной оценкой точности. Он состоит из двух полиномиальных приближенных алгоритмов: алгоритма $\mathcal A_1$, основанного на жадной эвристике, и алгоритма $\mathcal A_2$, основанного на отыскании некоторого решения задачи, двойственной к релаксированной исходной постановке. Трудоемкость объединенного алгоритма $\mathcal A$ равна $\mathcal O(mn(m + \log n))$, где $m$ – количество возможных мест размещения предприятий, $n$ – количество клиентов. В двойственном алгоритме используется бинарная куча, что позволило существенно уменьшить реальное время работы алгоритма. Уменьшение времени работы особенно проявилось на многоразмерных примерах. Результаты численных экспериментов со случайно сгенерированными данными подтверждают эффективность предлагаемого алгоритма.
Ключевые слова: задача размещения предприятий, NP-трудная задача, приближенный алгоритм, алгоритм с апостериорной оценкой точности, прямо-двойственный алгоритм, бинарная куча.
СПИСОК ЛИТЕРАТУРЫ
1. Jiaa H., Ordocez F., Dessouky M. A modeling framework for facility location of medical services for large-scale emergencies // IIE Transactions. 2007. Vol. 39, no. 1. P. 41–55. https://doi.org/10.1080/07408170500539113
2. Frank C., Romer K. Distributed facility location algorithms for flexible configuration of wireless sensor networks // Proc. Third IEEE Inter. Conf. “Distributed computing in sensor systems” (DCOSS 2007). Ser. Lecture Notes in Computer Science, vol. 4549. Berlin; Heidelberg: Springer, 2007. 124–141.
https://doi.org/10.1007/978-3-540-73090-3_9
3. Frey B.J., Delbert D. Clustering by passing messages between data points // Science. 2007. Vol. 315. Art. no. 5814. P. 972–976. https://doi.org/10.1126/science.1136800
4. Wang Q., Batta R., Rump C.M. Facility location models for immobile servers with stochastic demand // Naval Research Logistics. 2004. Vol. 51, no. 1. P. 137–152.
5. Andreas Klose, Andreas Drexl. Facility location models for distribution system design // Eur. J. Operat. Research. 2005. Vol. 162, no. 1. P. 4–29. https://doi.org/10.1016/j.ejor.2003.10.031
6. Ulukan Z., Demircioglu E. A survey of discrete facility location problems // Inter. J. Industrial and Manufacturing Engineering. 2015. Vol. 9, no. 7. P. 2487–2492. https://doi.org/10.5281/zenodo.1108652
7. Sevaux M., Sörensen K., Pillay N. Adaptive and multilevel metaheuristics // Handbook of heuristics / eds. R. Marti, P. Pardalos, M. Resende. Cham: Springer Inter. Publ., 2018. P. 3–21.
https://doi.org/10.1007/978-3-319-07124-4_16
8. Cornuéjols G., Nemhauser G. L., Wolsey L. A. The uncapacitated facility location problem // Discrete Location Theory / eds. P. Mirchandani, R. Francis. NY: Wiley, 1990. P. 119–171.
9. Vazirani V. Springer: Approximation algorithms, 2002. 378 p.
11. Dinur I., Steurer D. Analytical approach to parallel repetition // Proc. of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC’14). NY: ACM, 2014. P. 624–633.
10. Hansen P., Brimberg J., Urosevic D., Mladenovic N. Primal-dual variable neighborhood search for the simple plant-location problem // INFORMS J. Computing. 2007. Vol. 19, no. 4. P. 552–564. https://doi.org/10.1287/ijoc.1060.0196
12. Гимади Э.Х., Глебов Н.И., Дементьев В.Т. Об одном методе построения нижней оценки и приближенного решения с апостериорной оценкой точности для задачи стандартизации // Управляемые системы. 1974. № 13. C. 26–31.
13. Береснев В.Л., Гимади Э.X., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.
14. Клейнберг Д., Тардос Е. Алгоритмы. Разработка и применение. М.: Питер, 2016. 800 с.
15. Sonuc E., Ozcan E. An adaptive parallel evolutionary algorithm for solving the uncapacitated facility location problem // Expert Systems with Applications. Expert Syst. Appl. 2023. Vol. 224. Art. no. 119956. https://doi.org/10.1016/j.eswa.2023.119956
Поступила 23.04.2025
После доработки 18.07.2025
Принята к публикации 21.07.2025
Гимади Эдуард Хайрутдинович
д-р физ.-мат. наук, профессор
главный науч. сотрудник
Институт математики им. С.Л. Соболева СО РАН
г. Новосибирск
e-mail: gimadi@math.nsc.ru
Гончаров Евгений Николаевич
канд. физ.-мат. наук
старший науч. сотрудник
Институт математики им. С.Л. Соболева СО РАН
г. Новосибирск
e-mail: gon@math.nsc.ru
Штепа Александр Александрович†
e-mail: gimadi@math.nsc.ru
Ссылка на статью: Э.Х. Гимади, Е.Н. Гончаров, А.А. Штепа. Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 3. С. 77–90.
English
E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A primal-dual polynomial approximation algorithm for the uncapacitated facility location problem
The Uncapacitated Facility Location Problem is a well-known discrete optimization problem. We consider a problem with unsplittable demands and without triangle inequality. These problem is NP-hard in the strong sense. We propose a primal-dual approximate polynomial algorithm with a posteriori performance guarantee. The approach comprises two polynomial approximation algorithms: $\mathcal A_1$, which utilises the greedy heuristic, and $\mathcal A_2$, as proposed by the authors, based on identifying the dead-end solution to the dual problem. The complexity of the proposed algorithm is $\mathcal O(mn(m + \log n))$, where $m$ is the number of facilities and $n$ is the number of customers. In the dual algorithm, a binary heap is used, which significantly reduced the actual runtime of the algorithm. The reduction in runtime was especially noticeable on multidimensional examples. Numerical experiments with randomly generated instances demonstrate the effectiveness of the proposed algorithms through their computational results.
Keywords: Facility Location Problem, NP-hard problem, approximation algorithm, algorithm with a posteriori performance guarantee, primal-dual algorithm, binary heap.
Received April 23, 2025
Revised July 18, 2025
Accepted July 21, 2025
Funding Agency: The work was supported under state contract IM SB RAS no. FWNF-2022-0019.
Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gimadi@math.nsc.ru
Evgenii Nikolaevich Goncharov, Cand. Sci. (Phys.-Math.), Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gon@math.nsc.ru
Alexandr Alexandrovich Shtepa†, e-mail: gimadi@math.nsc.ru
Cite this article as: E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A primal-dual polynomial approximation algorithm for the uncapacitated facility location problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 77–90.
[References -> on the "English" button bottom right]
