On a Decomposition Method for Designing Communication Networks

Cover Page

Cite item

Full Text

Abstract

This paper presents a communication network design algorithm for finding a guaranteed trans-portation plan of a given volume under uncertain factors. The volumes of production and the capacities of communication lines are expressed as linear functions of invested resources. The well-known Dantzig–Wolfe decomposition algorithm is applied to solve the dual problem due to its stepped block structure. In view of their specifics, the linear problems arising in iterations are solved using effective network and graph theory methods: the maximum flow, the minimum cutset in the network, the connectivity components, and the minimum spanning trees of the graphs are found. The existing algorithms for these problems have the complexity estimates О( ), О( ), and O(n + m), where n is the number of graph vertices and m is the number of edges.

About the authors

O. A Kosorukov

Moscow State University

Email: kosorukovoa@mail.ru
Moscow, Russia

D. V Lemtyuzhnikova

Moscow Aviation Institute (National Research University); Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: darabbt@gmail.com
Moscow, Russia

References

  1. Давыдов Э.Г. Игры, графы, ресурсы. – М.: Радио и связь, 1981. – 112 с. [Davydov, E.G. Games, Gaphs, Resources. – M.: Radio and svyaz, 1981. – 112 s. (In Russian)]
  2. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. – М.: Наука, 1975. – 118 с. [Adelson-Velsky, G.M., Dinits, E.A., Karzanov, A.V. Streaming Algorithms. – Moscow: Nauka, 1975. – 118 p. (In Russian)]
  3. Гейл Д. Теория линейных экономических моделей. – М.: Изд-во иностр. лит., 1963. – 418 с. [Gale, D. Theory of Linear Economic Models. – N.-Y.: McGraw-Hill, 1960.]
  4. Романовский И.В. Алгоритмы решения экстремальных задач. – М.: Наука, 1977. – 352 с. [Romanovsky, I.V. Algorithms for Solving Extreme Problems. – Moscow: Nauka, 1977. – 352 p. (In Russian)]
  5. Лемешко В.Ю. Методы оптимизации: лекции. – Новосибирск: Изд-во НГУ, 2009. – 126 с. [Lemeshko, V.Yu. Optimization Methods: Lectures. – Novosibirsk: Publishing House of NSU, 2009. – 126 p. (In Russian)]
  6. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. – М.: Радио и связь, 1982. – 240 с. [Raskin, L.G., Kirichenko, I.O. Multi-index Problems of Linear Programming. – Moscow: Radio and Communication, 1982. – 240 p. (In Russian)]
  7. Серая О.В. Многомерные модели логистики в условиях неопределенности: монография. – Харьков: ФОП Стеценко И.И., 2010. – 512с. [Seraya, O.V. Multidimensional Models of Logistics Under Uncertainty: monograph. – Kharkov: FOP Stetsenko, I.I., 2010. – 512p. (In Russian)]
  8. Конюховский П.В. Математические методы исследования операций в экономике. – СПб: Питер, 2000. – 208 с. [Konyukhovsky, P.V. Mathematical Methods for Researching Operations in Economics. – St. Petersburg: Peter, 2000. – 208 p. (In Russian)]
  9. Kosorukov, O. The Algorithm of the Method of Generalized Potentials for the Problem of Optimal Synthesis of Communication Network // International Journal of Communications. – 2017. – Vol. 2. – P. 77–85.
  10. Kosorukov, O.A. Algorithm of the Method of Generalized Potentials for Problems of the Optimum Synthesis of Communication Networks with Undefined Factors // Moscow University Computational Mathematics and Cybernetic. – 2019. – Vol. 43, no. 3. – P. 138–142.
  11. Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. – М.: Мир, 1981. – 324 c. [Minieka, E. Optimization Algorithms for Networks and Graphs. – N.-Y.: M. Dekker, 1978.]
  12. Лэсдон Л. С. Оптимизация больших систем. Пер. с англ. – М.: Наука, 1975. – 432 c. [Lasdon, L. S. Optimization Theory for Large Systems. – London: Macmillan & Co., 1970.]
  13. Берж К. Теория графов и ее применения. – М.: Изд-во иностр. лит. – 1967. – 320 с. [Berge, C. Theory of Graphs and Its Applications. – London : Methuen, 1962.]
  14. Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. – М.: Сов. радио, – 1974. – 303 с. [Berzin, E.A. Optimal Distribution of Resources and Elements of Systems Synthesis. – Moscow: Sov. Radio. – 1974. – 303 p. (In Russian)]
  15. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // ДАН СССР. – 1979. – T. 244. – С. 1093–1096. [Khachiyan, L. A Polynomial Algorithm in Linear Programming // Soviet Mathematics Doklady – 1979. – Vol. 20. – P. 191–194.]
  16. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс. – 2005. – 1296 с. [Cormen, T.H., Leiserson, Ch.E., Rivest, R.L, and Stein, C. Introduction to Algorithms, 3rd ed. Cambridge: MIT Press, 2009.]
  17. Седжвик P. Алгоритмы на графах. – Россия, Санкт-Петербург: «ДиаСофтЮП». – 2002. – 496 с. [Sedgwick, R. Algorithms on Graphs. – Boston: Addison-Wesley Professional, 2002. – 496 p.]
  18. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. Пер. с англ. – М.: Мир, 1966. – 277 с. [Ford, L.R., Fulkerson, D.R. Flows in Networks. – Princeton, N.J.: Princeton University Press, 1962.]
  19. Hanaka, T., Kanemoto, K., Kagawa, S. Multi-perspective Structural Analysis of Supply Chain Networks // Economic Systems Research. – 2022. – Vol. 34, iss. 2. – P. 199–214.
  20. Turken, N., Cannataro, V., Geda, A., Dixit, A. Nature Inspired Supply Chain Solutions: Definitions, Analogies, and Future Research Directions // International Journal of Production Research. – 2020. – Vol. 58, iss. 15. – P. 91–102.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).