Моделирование и оптимизация крупномасштабных транспортно-экспедиционных систем

Моделирование и оптимизация крупномасштабных транспортно-экспедиционных систем

Нурминский Е. А., Шамрай Н. Б.
Дискретный анализ и исследование операций, 29, 3, 64-84 (2022)
Скачать статью

УДК 519.863 
DOI: 10.33048/daio.2022.29.736

Аннотация:

Моделирование масштабных экономических систем стало актуальной проблемой для крупного бизнеса. Такие реалии вынуждают плановые и аналитические отделы погружаться в сферу анализа и управления большими данными. Программные пакеты общего назначения не всегда подходят для решения возникающих проблем. Отсюда исходит запрос в академическое сообщество на разработку подходящего инструментария для работы с моделями на миллионы переменных и гигабайты данных. В статье описан опыт моделирования одной довольно распространённой транспортно-экспедиционной задачи, излагаются математические и вычислительные идеи, применённые для её исследования. 
Табл. 3, библиогр. 21.

Литература:
  1. Gurobi optimizer reference manual. Beaverton: Gurobi Optimization, 2021. Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed Feb. 27, 2022).
     
  2. IBM ILOG CPLEX Optimizer. Armonk: IBM, 2022. Available at www.ibm. com/analytics/cplex-optimizer (accessed Feb. 27, 2022).
     
  3. Anderson E., Bai Z., Bischof C., Blackford S., Demmel J., Dongarra J., Du Croz J., Greenbaum A., Hammarling S., McKenney A., Sorensen D. LAPACK users’ guide. Philadelphia: SIAM, 1999. 404 p.
     
  4. SuiteSparse: A suite of sparse matrix software. College Station: Texas A&M Univ., 2022. Available at people.engr.tamu.edu/davis/suitesparse.html (accessed Feb. 27, 2022).
     
  5. Dantzig G. B., Wolfe Ph. The decomposition algorithm for linear programming // Econometrica. 1961. V. 9, No. 4. P. 767–778.
     
  6. AMPL homepage. Mountain View, CA: AMPL Optimization, 2022. Available at ampl.com (accessed Feb. 27, 2022).
     
  7. Fourer R., Gay D. M., Kernighan B. W. AMPL: A modeling language for mathematical programming. Boston: Cengage Learning, 2003. 517 p.
     
  8. GAMS — A user’s guide. Frechen: GAMS Software, 2022. Available at www.gams.com/35/docs/UG_MAIN.html (accessed Feb. 27, 2022).
     
  9. GLPK (GNU linear programming kit). Boston, MA: Free Software Found., 2012. Available at www.gnu.org/software/glpk/ (accessed Feb. 27, 2022).
     
  10. NEOS Server. Madison, WI: Univ. Wisconsin, 2022. Available at neos-server.org/neos/ (accessed Feb. 27, 2022).
     
  11. Kahan G. Walking through a columnar approach to linear programming of a business // Interfaces. 1982. V. 12, No. 3. P. 32–39.
     
  12. Nurminski E. A. Single-projection procedure for linear optimization // J. Glob. Optim. 2016. V. 66, No. 1. P. 95–110.
     
  13. Goldman A. J., Tucker A. W. Theory of linear programming, linear inequalities and related systems. V. 38. Princeton, NJ: Princeton Univ. Press, 1956. P. 53–97.
     
  14. Von Neumann J. On rings of operators. Reduction theory // Ann. Math. 1949. V. 50, No. 2. P. 401–485.
     
  15. Bauschke H. H., Borwein J. M. On the convergence of von Neumann’s alternating projection algorithm for two sets // Set-Valued Anal. 1993. No. 1. P. 185–212. 
     
  16. Escalante R., Raydan M. Alternating projection methods. Philadelphia: SIAM, 2011.
     
  17. Michelot C. A finite algorithm for finding the projection of a point onto the canonical simplex of $E^n$ // J. Optim. Theory Appl. 1986. V. 50, No. 1. P. 195–200.
     
  18. Малоземов В. Н., Тамасян Г. Ш. Два быстрых алгоритма проектирования точки на стандартный симплекс // Журн. вычисл. математики и мат. физики. 2016. Т. 56, вып. 5. С. 742–755.
     
  19. Нурминский Е. А. Проекция на внешне заданные полиэдры // Журн. вычисл. математики и мат. физики. 2008. Т. 48, вып. 3. С. 387–396.
     
  20. Nurminski E. A., Shamray N. B. Row-oriented decomposition in largescale linear optimization // Optimization and Applications. Proc. Int. Conf. OPTIMA 2021 (Petrovac, Montenegro, Sep. 27–Oct. 1, 2021). Heidelberg: Springer, 2021. P. 50–63. (Lect. Notes Comput. Sci.; V. 13078).
     
  21. Greenberg H. J., Lundgren J. R., Maybee J. S. Graph theoretic methods for the qualitative analysis of rectangular matrices // SIAM J. Algebraic Discrete Methods. 1981. V. 2, No. 3. P. 227–239.

Исследование выполнено при финансовой поддержке Министерства науки и высшего образования России (проект № 075–02–2022–880).

Нурминский Евгений Алексеевич
  1. Дальневосточный федеральный университет,
    пос. Аякс, 10, 690922 Владивосток, Россия

E-mail: nurminskiy.ea@dvfu.ru

Шамрай Наталья Борисовна
  1. Институт автоматики и процессов управления ДВО РАН,
    ул. Радио, 5, 690041 Владивосток, Россия

E-mail: shamray@dvo.ru

Статья поступила 2 мая 2022 г. 
После доработки — 2 мая 2022 г. 
Принята к публикации 5 мая 2022 г.

Abstract:

Large-scale economic modeling is becoming a reality for major businesses and it pushes their analytic and planning departments into very complicated areas of big data analytics and control. At the same time, it demands research communities in academia and else to develop adequate tools to operate models with millions of variables and gigabytes of data, where traditional off-the-shelf solutions fail. In this paper, we describe our experience with one rather common high-dimensional logistic problem and some of the mathematical and computational ideas we pursue to deal with it. 
Tab. 3, bibliogr. 21.

References:
  1. Gurobi Optimizer Reference Manual (Gurobi Optimization, Beaverton, 2021). Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed Feb. 27, 2022).
     
  2. IBM ILOG CPLEX Optimizer (IBM, Armonk, 2022). Available at www.ibm.com/analytics/cplex-optimizer (accessed Feb. 27, 2022).
     
  3. E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide (SIAM, Philadelphia, 1999).
     
  4. SuiteSparse: A Suite of Sparse Matrix Software (Texas A&M Univ., College Station, 2022). Available at people.engr.tamu.edu/davis/suitesparse.html (accessed Feb. 27, 2022).
     
  5. G. B. Dantzig and Ph. Wolfe, The decomposition algorithm for linear programming, Econometrica 9 (4), 767–778 (1961).
     
  6. AMPL Homepage (AMPL Optimization, Mountain View, CA, 2022). Available at ampl.com (accessed Feb. 27, 2022).
     
  7. R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming (Cengage Learning, Boston, 2003).
     
  8. GAMS — A User’s Guide (GAMS Software, Frechen, 2022). Available at www.gams.com/35/docs/UG_MAIN.html (accessed Feb. 27, 2022).
     
  9. GLPK (GNU Linear Programming Kit) (Free Software Found., Boston, MA, 2012). Available at www.gnu.org/software/glpk/ (accessed Feb. 27, 2022).
     
  10. NEOS Server (Univ. Wisconsin, Madison, WI, 2022). Available at neos-server.org/neos/ (accessed Feb. 27, 2022).
     
  11. G. Kahan, Walking through a columnar approach to linear programming of a business, Interfaces 12 (3), 32–39 (1982).
     
  12. E. A. Nurminski, Single-projection procedure for linear optimization, J. Glob. Optim. 66 (1), 95–110 (2016).
     
  13. A. J. Goldman and A. W. Tucker, Theory of Linear Programming, Linear Inequalities and Related Systems. Vol. 38 (Princeton Univ. Press, Princeton, NJ, 1956). P. 53–97.
     
  14. J. von Neumann, On rings of operators. Reduction theory, Ann. Math. 50 (2), 401–485 (1949).
     
  15. H. H. Bauschke and J. M. Borwein, On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Anal. 1, 185–212 (1993).
     
  16. R. Escalante and M. Raydan, Alternating Projection Methods (SIAM, Philadelphia, 2011).
     
  17. C. Michelot, A finite algorithm for finding the projection of a point onto the canonical simplex of $E^n$, J. Optim. Theory Appl. 50 (1), 195–200 (1986).
     
  18. V. N. Malozemov and G. Sh. Tamasyan, Two fast algorithms for projecting a point onto the canonical simplex, Zh. Vychisl. Mat. Mat. Fiz. 56 (5), 742–755 (2016) [Russian] [Comput. Math. Math. Phys. 56 (5), 730–743 (2016)]. 
     
  19. E. A. Nurminski, Projection onto polyhedra in outer representation, Zh. Vychisl. Mat. Mat. Fiz. 48 (3), 387–396 (2008) [Russian] [Comput. Math. Math. Phys. 48 (3), 367–375 (2008)].
     
  20. E. Nurminski and N. Shamray, Row-oriented decomposition in large-scale linear optimization, in Optimization and Applications (Proc. Int. Conf. OPTIMA 2021, Petrovac, Montenegro, Sep. 27–Oct. 1, 2021) (Springer, Heidelberg, 2021), pp. 50–63 (Lect. Notes Comput. Sci., Vol. 13078).
     
  21. H. J. Greenberg, J. R. Lundgren, and J. S. Maybee, Graph theoretic methods for the qualitative analysis of rectangular matrices, SIAM J. Algebraic Discrete Methods 2 (3), 227–239 (1981).