А.А. Агеев, Э.Х. Гимади, О.Ю. Цидулко, А.А. Штепа. Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида ... С. 24-44

УДК 519.8

MSC: 90-02, 90B80

DOI: 10.21538/0134-4889-2022-28-2-24-44

Полный текст статьи (Full text)

Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091).

В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы производства всех предприятий одинаковые. Мы показываем, что UCFLP на звезде решается за линейное время, если в одной вершине графа не могут одновременно находиться предприятие и клиент, и $\mathcal{NP}$-трудна, если в каждой вершине могут находиться и предприятие, и клиент. Известно, что задача UCFLP на цепи полиномиально разрешима, мы улучшаем известную схему динамического программирования для этой задачи до оценки $\mathcal O(m^2n^2)$, где $m$ — количество предприятий, $n$ — количество клиентов. Для CFLP на цепи мы предлагаем псевдополиномиальный алгоритм ее решения на основе подхода из работы Мирчандани и др. (1996) с улучшенной временной сложностью $\mathcal O(mB)$, где $B$ — суммарный спрос клиентов.

Ключевые слова: задача размещения с ограничениями на объемы производства, однородная задача размещения с ограничениями на объемы производства, NP-трудная задача, звезда, цепь, полиномиальный алгоритм, псевдополиномиальный алгоритм, динамическое программирование

СПИСОК ЛИТЕРАТУРЫ

1.   Агеев А.А. Графы, матрицы и простейшая задача размещения // Управляемые системы. 1989. Вып. 29. С. 3–11.

2.   Агеев А.А. Полиномиальный алгоритм решения задачи размещения на последовательно-параллельной сети // Управляемые системы. 1990. Вып. 30. С. 3–16.

3.   Агеев А.А., Гимади Э.Х., Курочкин А.А, Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощностями предприятий // Дискретный анализ и исследование операций. 2009. Т. 16, вып. 5. С. 3–18.

4.   Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.

5.   Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 333 с.

6.   Вознюк И.П. Задача размещения на сети с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций. Сер. 2. 1999. Т. 6, вып. 1. С. 3–11.

7.   Вознюк И.П. Задача размещения пунктов производства на два-дереве с ограниченными пропускными способностями коммуникаций // Дискретный анализ и исследование операций. Сер. 2. 2000. Т. 7, вып. 1. С. 3–8.

8.   Гимади Э.Х. Эффективный алгоритм размещения с областями обслуживания, связными относительно ациклической сети // Управляемые системы. Вып. 23. Новосибирск, 1983. С. 12–23.

9.   Гимади Э.Х. Точный алгоритм решения внешнепланарной задачи размещения с улучшенной временной сложностью // Тр. Ин-та математики и механики УрО РАН. 2017. Т. 23, вып. 3. С. 74–81.

10.   Трубин В.А. Эффективный алгоритм решения задачи размещения на сети в форме дерева // Докл. АН СССР. 1976. Т. 231, вып. 3. С. 547–550.

11.   Ageev A.A. A Criterion of polynomial-time solvability for the network location problem // Integer Programming and Combinatorial Optimization: Proc. IPCO II Conf. Campus Printing. Pittsburg: Carnegi Mellon University, 1992. P. 237–245.

12.   Ageev A.A. Complexity of the network median problem on planar grids // Siberian Adv. Math. 1995. Vol. 5. P. 1–9.

13.   Ageev A.A. A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graph // Proc. of the 2-nd Intern. Workshop Discrete Optimization Methods in Production and Logistics (DOM’2004). Omsk, 2004. P. 28–32.

14.   Aggarwal A., Klawe M.M., Moran S., Shor P., Wilber R. Geometric applications of a matrix searching algorithm // Algorthmica. 1987. Vol. 2. P. 195–208. doi: 10.1007/BF01840359 

15.   Aggarwal A., Louis A., Bansal M. et al. A 3-approximation algorithm for the facility location problem with uniform capacities // Math. Programming. 2013. Vol. 141. P. 527–547. doi: 10.1007/s10107-012-0565-4 

16.   Bansal M., Garg N., Gupta N. A 5-approximation algorithm for capacitated facility location // Algorithms — ESA 2012 / eds. L. Epstein, P. Ferragina. 2012. P. 133–144. (Ser. Lecture Notes in Computer Science; vol. 7501). doi: 10.1007/978-3-642-33090-2_13 

17.   Bilde O., Krarup J., Sharp lower bounds and efficient algorithms for the simple plant location problem // Annals Discret. Math. 1977. Vol. 1. P. 79–97. doi: 10.1016/S0167-5060(08)70728-3 

18.   Billionet A., Costa M.-C. Solving the uncapacitated plant location problem on trees // Discret. Appl. Math. 1994. Vol. 49, iss. 1–3. P. 51–59.

19.   Blum M., Floyd R.W., Pratt V., Rivest R.L., Tarjan E. Time bounds for selection // Journal of Computer and System Sciences, 1973, Vol. 7, No. 4, P. 448–461, doi: 10.1016/S0022-0000(73)80033-9 

20.   Cornuéjols G., Nemhauser G.L., Wolsey L.A. The uncapacitated facility location problem // Discret. Location Theory. NY: Wiley, 1990. P. 119–171.

21.   Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco, 1990. 338 p. doi: 10.5555/574848 

22.   Gimadi E.Kh., Kurochkina A.A. Time complexity of the Ageev’s algorithm to solve the uniform hard capacities facility location problem // Optimization and Applications — 9th Internat. Conf. (OPTIMA 2018). Communications in Computer and Information Science. 2019. Vol. 974. doi: 10.1007/978-3-030-10934-9_9 

23.   Gimadi E.Kh., Tsidulko O.Yu. On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines // Proc. Steklov Institute Math. 2021. Vol. 313, suppl. 1. P. 1–15. doi: 10.1134/S0081543821030081 

24.   Granot D., Skorin-Kapov D. On some optimization problems on k-trees and partial k-trees // Discret. Appl. Math. 1994, Vol. 48, no. 2. P. 129–145. doi: 10.1016/0166-218X(92)00122-3 

25.   Hassin R., Tamir A. Efficient algorithms for optimization and selection on series-parallel graphs // SIAM J. Alg. Disc. Meth. 1986. Vol. 7. P. 379–389. doi: 10.1137/0607043 

26.   Hassin R., Tamir A. Improved complexity bounds for location problems on the real line // Operations Research Letters. 1991. Vol. 10, iss. 7. P. 395–402. doi: 10.1016/0167-6377(91)90041-M .

27.   Laporte G., Nickel S., Saldanha da Gama F. Location science. Switzerland: Springer Internat. Publ., 2015. 644 p. doi: 10.1007/978-3-319-13111-5_1 .

28.   Mirchandani P., Kohli R., Tamir A. Capacitated location problems on a line // Transportation Science. 1996. Vol. 30, iss. 1. P. 75–80. doi: 10.1287/trsc.30.1.75 .

29.   Pál M., Tardos E., Wexler T. Facility location with hard capacities // Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS). 2001. P. 329–338. doi: 10.1109/SFCS.2001.959907 

30.   Shah D. An unified limited column generation approach for facility location problem on trees // Ann. Oper. Research. 1999. Vol. 87. P. 363–382.

31.   Shah R., Farach-Colton V. Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees // Proc. 13th Ann. ACM-SIAM Symp. on discrete algorithms (San Francisco). California: SODA, 2002. P. 108–115. doi: 10.5555/545381.545395 

Поступила 28.04.2022

После доработки 16.05.2022

Принята к публикации 20.05.2022

Агеев Александр Александрович
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики им. С.Л. Соболева СО РАН
г. Новосибирск
e-mail: ageev@math.nsc.ru

Гимади Эдуард Хайрутдинович
д-р физ.-мат. наук, профессор
главный научн. сотрудник
Институт математики им. С.Л. Соболева СО РАН
г. Новосибирск
e-mail: gimadi@math.nsc.ru

Цидулко Оксана Юрьевна
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики им. С.Л. Соболева СО РАН
г. Новосибирск
e-mail: tsidulko@math.nsc.ru

Штепа Александр Александрович
аспирант
Новосибирский национальный исследовательский государственный университет (НГУ)
г. Новосибирск
e-mail: shoomath@gmail.com

Ссылка на статью: А.А. Агеев, Э.Х. Гимади, О.Ю. Цидулко, А.А. Штепа. Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 24-44

English

A.A. Ageev, E.Kh. Gimadi, O.Yu. Tsidulko, A.A. Shtepa. Capacitated Facility Location Problem on tree-like graphs

We consider the network Capacitated Facility Location Problem (CFLP) and its special case - the Uniform Capacitated Facility Location Problem (UCFLP), where all facilities have the same capacity. We show that the UCFLP on a star graph is linear-time solvable if every vertex of the star can be either a facility or a client but not both. We further prove that the UCFLP on a star graph is $\mathcal{NP}$-hard if the facilities and clients can be located at each vertex of the graph. The UCFLP on a path graph is known to be polynomially solvable. We give a version of the known dynamic programming algorithm for this problem with the improved time complexity $\mathcal O(m^2n^2)$, where $m$ is the number of facilities and $n$ is the number of clients. For the CFLP on a path graph we propose a pseudo-polynomial time algorithm based on the work of Mirchandani et al.  (1996) with improved time complexity $\mathcal O(mB)$, where $B$ is the total demand of the clients.

Keywords: Capacitated Facility Location Problem, Uniform Capacitated Facility Location Problem, NP-hard problem, star graph, path graph, polynomial time algorithm, pseudo-polynomial time algorithm, dynamic programming

Received April 28, 2022

Revised May 16, 2022

Accepted May 20, 2022

Funding Agency: This work was supported within the State Assignment to the Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences (project no. FWNF-2022-0019) and by the Russian Foundation for Basic Research (project no. 20-31-90091).

Alexander Alexandrovich Ageev, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: ageev@math.nsc.ru

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

Alexandr Alexandrovich Shtepa, Post-grad. student, Novosibirsk State University (NSU), Novosibirsk, 630090 Russia, e-mail: shoomath@gmail.com

Oxana Yurievna Tsidulko, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: tsidulko@math.nsc.ru

Cite this article as: A.A. Ageev, E.Kh. Gimadi, O.Yu. Tsidulko, A.A. Shtepa. Capacitated Facility Location Problem on tree-like graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 24–44.

[References -> on the "English" button bottom right]