A scalable algorithm for solving non-stationary linear programming problems

Authors

DOI:

https://doi.org/10.26089/NumMet.v19r448

Keywords:

non-stationary high-dimension linear programming problem, NSLP algorithm, BSF parallel computation model, scalability estimation, cluster computing systems

Abstract

This paper is devoted to the scalability study of an NSLP algorithm for solving non-stationary high-dimension linear programming problems on cluster computing systems. The analysis is based on the BSF model of parallel computations. The BSF model is a new parallel computation model designed on the basis of BSP and SPMD models. The brief descriptions of the NSLP algorithm and the BSF model are given. The NSLP algorithm implementation in the form of a BSF program is considered. On the basis of the BSF cost metric, the upper bound of the NSLP algorithm scalability is derived and its parallel efficiency is estimated. The NSLP algorithm implementation using BSF skeleton is described. The scalability estimates obtained analytically and experimentally are compared.

Author Biographies

I.M. Sokolinskaya

South Ural State University
• Associate Professor

L.B. Sokolinsky

South Ural State University
• Vice-Rector for Informatization

References

  1. Chung W. Applying large-scale linear programming in business analytics // Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). New York: IEEE Press, 2015. 1860-1864.
  2. Tipi H. Solving super-size problems with optimization // Presentation at the meeting of the 2010 INFORMS Conference on O.R. Practice. Orlando, Florida. April 2010. // http://nymetro.chapter.informs.org/prac_cor_pubs/06-10
  3. Gondzio J. et al. Solving large-scale optimization problems related to Bell’s theorem // Journal of Computational and Applied Mathematics. 2014. 263. 392-404.
  4. Sodhi M.S. LP modeling for asset-liability management: a survey of choices and simplifications // Operations Research. 2005. 53, N 2. 181-196.
  5. Brogaard J., Hendershott T., Riordan R. High-frequency trading and price discovery // Review of Financial Studies. 2014. 27, N 8. 2267-2306.
  6. Budish E., Cramton P., Shim J. The high-frequency trading arms race: frequent batch auctions as a market design response // The Quarterly Journal of Economics. 2015. 130, N 4. 1547-1621.
  7. Goldstein M.A., Kwan A., Philip R. High-frequency trading strategies. //
  8. Hendershott T., Jones C.M., Menkveld A.J. Does algorithmic trading improve liquidity? // The Journal of Finance. 2011. 66, N 1. 1-33.
  9. Dantzig G.B. Linear programming and extensions. Princeton: Princeton University Press, 1998.
  10. Klee V., Minty G.J. How good is the simplex algorithm? // Inequalities. Vol. 3. New-York: Academic Press, 1972. 159-175.
  11. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. 4, N 4. 373-395.
  12. Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных // Параллельные вычислительные технологии - XI международная конференция, ПаВТ-2017, г. Казань, 3-7 апреля 2017 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. 471-484. http://omega.sp.susu.ru/pavt2017/short/014.pdf.
  13. Agmon S. The relaxation method for linear inequalities // Canadian Journal of Mathematics. 1954. 6. 382-392.
  14. Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities // Canadian Journal of Mathematics. 1954. 6. 393-404.
  15. Еремин И.И. Фейеровские методы для задач выпуклой и линейной оптимизации. Челябинск: Изд. центр ЮУрГУ, 2009.
  16. González-Gutiérrez E., Rebollar L.H., Todorov M.I. Relaxation methods for solving linear inequality systems: converging results // TOP. 2012. 20, N 2. 426-436.
  17. Соколинская И.М., Соколинский Л.Б. Модифицированный следящий алгоритм для решения нестационарных задач линейного программирования на кластерных вычислительных системах с многоядерными ускорителями // Суперкомпьютерные дни в России: труды международной конференции (26-27 сентября 2016 г., г. Москва). М.: Изд-во МГУ, 2016. 294-306. http://2016.russianscdays.org/files/pdf16/294.pdf.
  18. Sahni S., Vairaktarakis G. The master-slave paradigm in parallel computer and industrial settings // Journal of Global Optimization. 1996. 9, N 3-4. 357-377.
  19. Silva L.M., Buyya R. Parallel programming models and paradigms // High Performance Cluster Computing: Architectures and Systems. Vol. 2. Upper Saddle River: Prentice Hall, 1999. 4-27.
  20. Leung J.Y.-T., Zhao H. Scheduling problems in master-slave model // Annals of Operations Research. 2008. 159, N 1. 215-231.
  21. Ежова Н.А., Соколинский Л.Б. BSF: модель параллельных вычислений для многопроцессорных систем с распределенной памятью // Параллельные вычислительные технологии - XII международная конференция, ПаВТ-2018, г. Ростов-на-Дону, 2-6 апреля 2018 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2018. 253-265. http://omega.sp.susu.ru/pavt2018/short/001.pdf.
  22. Darema F., George D.A., Norton V.A., Pfister G.F. A single-program-multiple-data computational model for EPEX-FORTRAN // Parallel Computing. 1988. 7, N 1. 11-24.
  23. Kostenetskiy P.S., Safonov A.Y. SUSU Supercomputer resources // Proceedings of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). CEUR Workshop Proceedings. 2016. 1576. 561-573.

Published

2018-12-24

How to Cite

Соколинская И.М., Соколинский Л.Б. A Scalable Algorithm for Solving Non-Stationary Linear Programming Problems // Numerical methods and programming. 2018. 19. 540-550. doi 10.26089/NumMet.v19r448

Issue

Section

Section 1. Numerical methods and applications