Визуальное представление многомерных задач линейного программирования

Николай Александрович Ольховский, Леонид Борисович Соколинский

Аннотация


В статье строится n-мерная математическая модель визуального представления задачи линейного программирования. Эта модель позволит использовать аппарат искусственных нейронных сетей для решения многомерных задач линейной оптимизации, допустимая область которых является ограниченным непустым множеством. Для визуализации задачи линейного программирования вводится целевая гиперплоскость, ориентация которой определяется градиентом линейной целевой функции: градиент является нормалью к целевой гиперплоскости. В случае поиска максимума целевая гиперплоскость располагается таким образом, чтобы значение целевой функции во всех ее точках превосходило значение целевой функции во всех точках допустимой области, представляющей собой ограниченный выпуклый многогранник. Для произвольной точки целевой гиперплоскости определяется целевая проекция на многогранник: чем ближе точка целевой проекции к целевой гиперплоскости, тем больше значение целевой функции в этой точке. На основе целевой гиперплоскости строится конечное регулярное множество точек, называемое рецептивным полем. С помощью целевых проекций строится образ многогранника, включающий в себя точки рецептивного поля и расстояния до соответствующих точек поверхности многогранника. На основе предложенной модели строится параллельный алгоритм визуализации задачи линейного программирования. Дается аналитическая оценка его масштабируемости. Приводятся сведения о программной реализации и результаты масштабных вычислительных экспериментов, подтверждающие эффективность предложенных подходов.

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


линейное программирование; n-мерная визуализация; математическая модель; параллельный алгоритм; BSF-каркас

Полный текст:

PDF

Литература


Jagadish H.V., Gehrke J., Labrinidis A., et al. Big data and its technical challenges. Communications of the ACM. 2014. Vol. 57, no. 7. P. 86–94. DOI: 10.1145/2611567.

Hartung T. Making Big Sense From Big Data. Frontiers in Big Data. 2018. Vol. 1. P. 5. DOI: 10.3389/fdata.2018.00005.

Sokolinskaya I.M., Sokolinsky L.B. On solving linear programming problems in the era of big data. Parallel Computing Technologies (PCT’2017). Short articles and posters. Chelyabinsk: SUSU Publishing Center, 2017. P. 471–484. (in Russian).

Chung W. Applying large-scale linear programming in business analytics. 2015 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2015. P. 1860–1864. DOI: 10.1109/IEEM.2015.7385970.

Gondzio J., Gruca J.A., Hall J.A.J., et al. Solving large-scale optimization problems related to Bell’s Theorem. Journal of Computational and Applied Mathematics. 2014. Vol. 263. P. 392–404. DOI: 10.1016/j.cam.2013.12.003.

Sodhi M.S. LP modeling for asset-liability management: A survey of choices and simplifications. Operations Research. 2005. Vol. 53, no. 2. P. 181–196. DOI: 10.1287/opre.1040.0185.

Brogaard J., Hendershott T., Riordan R. High-Frequency Trading and Price Discovery. Review of Financial Studies. 2014. Vol. 27, no. 8. P. 2267–2306. DOI: 10.1093/rfs/hhu032.

Dyshaev M.M., Sokolinskaya I.M. Representation of trading signals based on the Kaufman’s Adaptive Moving Average in the form of a system of linear inequalities. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2014. Vol. 2, no. 4. P. 103–108. (in Russian) DOI: 10.14529/cmse130408.

Bixby R.E. Solving Real-World Linear Programs: A Decade and More of Progress. Operations Research. 2002. Vol. 50, no. 1. P. 3–15. DOI: 10.1287/opre.50.1.3.17780.

Dongarra J., Gottlieb S., Kramer W.T.C. Race to Exascale. Computing in Science and Engineering. 2019. Vol. 21, no. 1. P. 4–5. DOI: 10.1109/MCSE.2018.2882574.

Dantzig G.B. Linear programming and extensions. Princeton, N.J.: Princeton university press, 1998. 656 p.

Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms. Mathematical Programming. 1973. Vol. 5, no. 1. P. 255–266. DOI: 10.1007/BF01580132.

Tolla P. A Survey of Some Linear Programming Methods. Concepts of Combinatorial Optimization / ed. by V.T. Paschos. 2nd ed. Hoboken, NJ, USA: John Wiley, Sons, 2014. Chap. 7. P. 157–188. DOI: 10.1002/9781119005216.ch7.

Mamalis B., Pantziou G. Advances in the Parallelization of the Simplex Method. Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295 / ed. by C. Zaroliagis, G. Pantziou, S. Kontogiannis. Cham: Springer, 2015. P. 281–307. DOI: 10.1007/978-3-319-24024-4_17.

Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica. 1984. Vol. 4, no. 4. P. 373–395. DOI: 10.1007/BF02579150.

Yuan Y. Implementation tricks of interior-point methods for large-scale linear programs. Proc. SPIE, vol. 8285. International Conference on Graphic and Image Processing (ICGIP 2011). International Society for Optics, Photonics, 2011. DOI: 10.1117/12.913019.

Ershova A.V., Sokolinskaya I.M. On the convergence of a scalable algorithm for constructing a pseudoprojection on a convex closed set. Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software. 2011. No. 37(254). (in Russian).

Hafsteinsson H., Levkovitz R., Mitra G. Solving large scale linear programming problems using an interior point method on a massively parallel SIMD computer. Parallel Algorithms and Applications. 1994. Vol. 4, no. 3-4. P. 301–316. DOI: 10.1080/10637199408915470.

Karypis G., Gupta A., Kumar V. A parallel formulation of interior point algorithms. Proceedings of the 1994 ACM/IEEE conference on Supercomputing (Supercomputing’94). Los Alamitos, CA, USA: IEEE Computer Society Press, 1994. P. 204–213. DOI: 10.1109/SUPERC.1994.344280.

Prieto A., Prieto B., Ortigosa E.M., et al. Neural networks: An overview of early research, current frameworks and new challenges. Neurocomputing. 2016. Vol. 214. P. 242–268. DOI: 10.1016/j.neucom.2016.06.014.

Schmidhuber J. Deep learning in neural networks: An overview. Neural Networks. 2015. Vol. 61. P. 85–117. DOI: 10.1016/j.neunet.2014.09.003.

LeCun Y., Bengio Y., Hinton G. Deep learning. Nature. 2015. Vol. 521, no. 7553. P. 436–444. DOI: 10.1038/nature14539.

Lachhwani K. Application of Neural Network Models for Mathematical Programming Problems: A State of Art Review. Archives of Computational Methods in Engineering. 2020. Vol. 27. P. 171–182. DOI: 10.1007/s11831-018-09309-5.

Sokolinsky L.B. BSF: A parallel computation model for scalability estimation of iterative numerical algorithms on cluster computing systems. Journal of Parallel and Distributed Computing. 2021. Vol. 149. P. 193–206. DOI: 10.1016/j.jpdc.2020.12.009.

Ezhova N.A., Sokolinsky L.B. Parallel computation model BSF-MR. Control systems and information technologies. 2019. No. 3(77). P. 15–21. (in Russian).

Bird R.S. Lectures on Constructive Functional Programming. Constructive Methods in Computing Science. NATO ASI Series F: Computer and Systems Sciences, vol. 55 / ed. by M. Broy. Berlin, Heidelberg: Springer, 1988. P. 151–216.

Sokolinsky L.B. BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems. MethodsX. 2021. Vol. 8. Article 101437. DOI: 10.1016/j.mex.2021.101437.

Sokolinsky L.B. BSF-skeleton. 2019. URL: https://github.com/leonid-sokolinsky/BSF-skeleton (accessed: 24.01.2022).

Gropp W. MPI 3 and Beyond: Why MPI Is Successful and What Challenges It Faces. Recent Advances in the Message Passing Interface. EuroMPI 2012. Lecture Notes in Computer Science, vol. 7490 / ed. by J. Traff, S. Benkner, J. Dongarra. Berlin, Heidelberg: Springer, 2012. P. 1–9. DOI: 10.1007/978-3-642-33518-1_1.

Kale V. Shared-memory Parallel Programming with OpenMP. Parallel Computing Architectures and APIs. Boca Raton: Chapman, Hall/CRC, 2019. Chap. 14. P. 213–222. DOI: 10.1201/9781351029223-18/SHARED-MEMORY-PARALLEL-PROGRAMMING-OPENMP-VIVEKKALE.

Kostenetskiy P., Semenikhina P. SUSU Supercomputer Resources for Industry and fundamental Science. Proceedings - 2018 Global Smart Industry Conference, GloSIC 2018. IEEE, 2018. Article 8570068. P. 1–7. DOI: 10.1109/GloSIC.2018.8570068.

Sokolinsky L.B., Sokolinskaya I.M. On generation of random linear programming problems on cluster computing systems. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 1. P. 38–52. (in Russian).

Sokolinsky L.B. Certificate of state registration of computer program no. 2021619526 Russian Federation. Generator of random linear programming problems FRaGenLP : no. 2021618165 : application 28.05.2021 : publ. 10.06.2021. (in Russian).




DOI: http://dx.doi.org/10.14529/cmse220103