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

A scalable algorithm for solving non-stationary linear programming problems

Authors

  • I.M. Sokolinskaya
  • L.B. Sokolinsky

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.

New computational technologies

Downloads

Published

2018-12-24

Issue

Vol. 19 (2018): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biographies

I.M. Sokolinskaya

South Ural State University
• Associate Professor

L.B. Sokolinsky

South Ural State University
• Vice-Rector for Informatization

References

  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).