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

Масштабируемый алгоритм для решения нестационарных задач линейного программирования

Авторы

  • И.М. Соколинская
  • Л.Б. Соколинский

Ключевые слова:

нестационарная задача линейного программирования сверхбольшой размерности
алгоритм NSLP
модель параллельных вычислений BSF
оценка масштабируемости
кластерные вычислительные системы

Аннотация

Статья посвящена исследованию алгоритма NSLP для решения нестационарных задач линейного программирования сверхбольшой размерности, ориентированного на кластерные вычислительные системы. В основе анализа лежит модель параллельных вычислений BSF, основанная на моделях BSP и SPMD. Даются краткие описания алгоритма NSLP и модели BSF. Рассматривается реализация алгоритма NSLP в виде BSF-программы. На базе стоимостной метрики модели BSF выводится верхняя граница масштабируемости алгоритма NSLP и оценивается эффективность его параллелизации. Описывается реализация алгоритма NSLP на основе программного каркаса BSF на языке Си и приводятся результаты экспериментов, исследующих масштабируемость указанной реализации на модельной задаче линейного программирования. Делается сравнение результатов, полученных аналитическим и экспериментальным путем.

Новые вычислительные технологии

Загрузки

Опубликован

2018-12-24

Выпуск

Том 19 (2018): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

И.М. Соколинская

Южно-Уральский государственный университет
просп. Ленина, 76, 454080, Челябинск
• доцент

Л.Б. Соколинский

Южно-Уральский государственный университет
просп. Ленина, 76, 454080, Челябинск
• проректор по информатизации

Библиографические ссылки

  1. W. Chung, “Applying Large-Scale Linear Programming in Business Analytics,” in Proc. IEEE Int. Conf. on Industrial Engineering and Engineering Management Singapore, December 6-9, 2015 (IEEE Press, New York, 2016), pp. 1860-1864.
  2. H. Tipi, 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%20Horia%20Tipi%20SolvingLargeScaleXpress.pdf . Cited December 10, 2018.
  3. J. Gondzio, J. A. Gruca, J. A. J. Hall, et al., “Solving Large-Scale Optimization Problems Related to Bell’s Theorem,” J. Comput. Appl. Math. 263, 392-404 (2014).
  4. M. S. Sodhi, “LP Modeling for Asset-Liability Management: A Survey of Choices and Simplifications,” Oper. Res. 53 (2), 181-196 (2005).
  5. J. Brogaard, T. Hendershott, and R. Riordan, “High-Frequency Trading and Price Discovery,” Rev. Financ. Stud. 27 (8), 2267-2306 (2014).
  6. E. Budish, P. Cramton, and J. Shim, “The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response,” Quart. J. Econ. 130 (4), 1547-1621 (2015).
  7. M. A. Goldstein, A. Kwan, and R. Philip, “High-Frequency Trading Strategies,”
    https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2973019 . Cited December 10, 2018.
  8. T. Hendershott, C. M. Jones, and A. J. Menkveld, “Does Algorithmic Trading Improve Liquidity?,” J. Finance 66 (1), 1-33 (2011).
  9. G. B. Dantzig, Linear Programming and Extensions (Princeton Univ. Press, Princeton, 1998).
  10. V. Klee and G. J. Minty, “How Good is the Simplex Algorithm?,” in Inequalities (Academic, New York, 1972), Vol. 3, pp. 159-175.
  11. N. Karmarkar, “A New Polynomial-Time Algorithm for Linear Programming,” Combinatorica 4 (4), 373-395 (1984).
  12. I. M. Sokolinskaya and L. B. Sokolinsky, “On the Solution of Linear Programming Problem in the Era of Big Data,” in Proc. Int. Conf. on Parallel Computational Technologies, Kazan, Russia, April 3-7, 2017 (South Ural State Univ., Chelyabinsk, 2017), pp. 471-484.
  13. S. Agmon, “The Relaxation Method for Linear Inequalities,” Canad. J. Math. 6, 382-392 (1954).
  14. T. S. Motzkin and I. J. Schoenberg, “The Relaxation Method for Linear Inequalities,” Canad. J. Math. 6, 393-404 (1954).
  15. I. I. Eremin, Fejer Methods for Problems of Convex and Linear Optimization (South Ural State Univ., Chelyabinsk, 2009) [in Russian].
  16. E. González-Gutiérrez, L. H. Rebollar, and M. I. Todorov, “Relaxation Methods for Solving Linear Inequality Systems: Converging Results,” TOP 20 (2), 426-436 (2012).
  17. I. M. Sokolinskaya and L. B. Sokolinsky, “Revised Pursuit Algorithm for Solving Unstable Linear Programming Problems on Modern Computing Clusters with Manycore Accelerators,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 26-27, 2016 (Mosk. Gos. Univ., Moscow, 2016), pp. 294-306.
  18. S. Sahni and G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings,” J. Glob. Optim. 9 (3-4), 357-377 (1996).
  19. L. M. Silva and R. Buyya, “Parallel Programming Models and Paradigms,” in High Performance Cluster Computing: Architectures and Systems (Prentice Hall, Upper Saddle River, 1999), Vol. 2, pp. 4-27.
  20. J. Y.-T. Leung and H. Zhao, “Scheduling Problems in Master-Slave Model,” Ann. Oper. Res. 159 (1), 215-231 (2008).
  21. N. A. Ezhova and L. B. Sokolinsky, “BSF: A model of Parallel Computation for Multiprocessor Systems with Distributed Memory,” in Proc. Int. Conf. on Parallel Computational Technologies, Rostov-on-Don, Russia, April 2-6, 2018 (South Ural State Univ., Chelyabinsk, 2018), pp. 253-265.
    http://omega.sp.susu.ru/pavt2018/short/001.pdf.
  22. F. Darema, D. A. George, V. A. Norton, and G. F. Pfister, “A Single-Program-Multiple-Data Computational Model for EPEX/FORTRAN,” Parallel Comput. 7 (1), 11-24 (1988).
  23. P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computing Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. 1576, 561-573 (2016).