О проекционном методе линейного программирования

Леонид Борисович Соколинский
Южно-Уральский государственный университет, Челябинск

Александр Эдуардович Жулев
Южно-Уральский государственный университет, Челябинск

Ирина Михайловна Соколинская
Южно-Уральский государственный университет, Челябинск


Аннотация


В статье рассматривается проблема разработки эффективных методов проекционного типа для решения задач линейного программирования (ЛП). Предложен новый гибридный проекционный алгоритм HAlEM (Hybrid Along Edges Movement), сочетающий идеи проекционного подхода и симплекс-метода. Алгоритм начинает работу из произвольной вершины многогранника допустимых решений и осуществляет движение вдоль его ребер к оптимальной вершине. Для вычисления направления движения используется оригинальный метод двух-факторной проекции, обеспечивающий высокую вычислительную точность для любых задач ЛП. Основным преимуществом HAlEM перед предшествующими разработками (AlFaMove, AlEM) является отказ от комбинаторного перебора всех возможных комбинаций гиперплоскостей за счет использования техники обновления матричного базиса, заимствованной из симплекс-метода. Это позволяет избежать экспоненциальной вычислительной сложности. В статье представлена параллельная версия алгоритма, основанная на модели параллельных вычислений BSF и схеме «мастер-рабочие», позволяющих получить эффективную реализацию для суперкомпьютерных систем кластерного типа. Проведены вычислительные эксперименты на эталонных задачах из репозитория Netlib-LP и на серии параметризованных задач. Результаты экспериментов демонстрируют, что HAlEM, в отличие от симплекс-метода, обладает более высоким ресурсом параллелизма, позволяя эффективно использовать до нескольких десятков процессорных узлов, и показывает хорошую масштабируемость с параллельной эффективностью не ниже 51%. При этом алгоритм обеспечивает высокую точность вычислений на уровне машинного нуля.

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


линейное программирование; алгоритм HAlEM; проекционный метод; параллельная реализация; MPI; кластерная вычислительная система; исследование масштабируемости; Netlb-LP

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

PDF

Литература


Pan P.-Q. Linear Programming Computation. Berlin, Heidelberg: Springer, 2014. 747 p. DOI: 10.1007/978-3-642-40754-3.

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.

Rasmussen S. Production Economics. The Basic Theory of Production Optimisation. 2nd ed. Berlin, Heidelberg: Springer, 2013. XII, 292 p. Springer Texts in Business and Economics. DOI: 10.1007/978-3-642-30200-8.

Xu Y. Solving Large Scale Optimization Problems in the Transportation Industry and Beyond Through Column Generation. Optimization in Large Scale Problems. Springer Optimization and Its Applications, vol. 152. Cham: Springer, 2019. P. 269–292. DOI: 10.1007/978-3-030-28565-4_23.

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.

Dantzig G.B., Thapa M.N. Linear Programming 2: Theory and Extensions. Springer Series in Operations Research and Financial Engineering. New York, NY, USA: Springer, 2003. XXVI, 448 p. DOI: 10.1007/b97283.

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.

Im H., Wolkowicz H. Revisiting degeneracy, strict feasibility, stability, in linear programming. European Journal of Operational Research. 2023. Vol. 310, no. 2. P. 495–510. DOI: 10.1016/j.ejor.2023.03.021.

Gass S.I., Vinjamuri S. Cycling in linear programming problems. Computers and Operations Research. 2004. Vol. 31, no. 2. P. 303–311. DOI: 10.1016/S0305-0548(02)00226-5.

Hall J., McKinnon K. The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. Mathematical Programming, Series B. 2004. Vol. 100, no. 1. P. 133–150. DOI: 10.1007/s10107-003-0488-1.

Sokolinsky L.B., Sokolinskaya I.M. Apex Method: A New Scalable Iterative Method for Linear Programming. Mathematics. 2023. Vol. 11, no. 7. P. 1–28. DOI: 10.3390/MATH11071654.

Olkhovsky N.A., Sokolinsky L.B. Surface Movement Method for Linear Programming. Lobachevskii Journal of Mathematics. 2024. Vol. 45, no. 10. P. 5061–5079. DOI: 10.1134/S1995080224605745.

Olkhovsky N.A., Sokolinsky L.B. AlFaMove: Scalable Implementation of Surface Movement Method for Cluster Computing Systems. Supercomputing Frontiers and Innovations. 2024. Vol. 11, no. 3. P. 4–26. DOI: 10.14529/jsfi240301.

Zhulev A.E., Sokolinsky L.B. Finding optimal vertex on polytope of feasible solutions to linear programming problem. Numerical Methods and Programming. 2026. Vol. 27, no. 1. P. 1–18. (in Russian) DOI: 10.26089/NumMet.v27r101.

Murty K.G. Computational and Algorithmic Linear Algebra and n-Dimensional Geometry. Singapore: World Scientific Publishing Company, 2014. 480 p. DOI: 10.1142/8261.

Strang G. Linear Algebra and Its Applications. 2nd. Academic Press, 1980. 425 p.

Schrijver A. Theory of Linear and Integer Programming. Chichester, New York, Brisbane, Toronto, Singapore: Wiley, Sons, 1998. 484 p.

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.

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

Dolganina N., Ivanova E., Bilenko R., Rekachinsky A. HPC Resources of South Ural State University. Parallel Computational Technologies. PCT 2022. Communications in Computer and Information Science, vol. 1618 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2022. P. 43–55. DOI: 10.1007/978-3-031-11623-0_4.

Gay D.M. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin. 1985. Vol. 13. P. 10–12.

Murtagh B.A. Advanced linear programming: computation and practice. New York, London: McGraw-Hill, 1981. xii, 202 p.

Boisvert R.F., Pozo R., Remington K.A. The Matrix Market Exchange Formats: Initial Design: tech. rep. / NISTIR 5935. National Institute of Standards; Technology. Gaithersburg, MD, 1996. P. 14. URL: https://nvlpubs.nist.gov/nistpubs/Legacy/IR/nistir5935.pdf.

Koch T. The final NETLIB-LP results. Operations Research Letters. 2004. Vol. 32, no. 2. P. 138–142. DOI: 10.1016/S0167-6377(03)00094-4.

Quarteroni A., Sacco R., Saleri F. Numerical Mathematics. Vol. 37. 2nd ed. Berlin, Heidelberg: Springer, 2007. XVIII, 657 p. Texts in Applied Mathematics. DOI: 10.1007/b98885.

Ziegler G.M. Lectures on Polytopes. Vol. 152. New York, NY: Springer New York, 1995. XI, 370 p. Graduate Texts in Mathematics. DOI: 10.1007/978-1-4613-8431-1.

Sokolinsky L.B., Sokolinskaya I.M. FRaGenLP: A Generator of Random Linear Programming Problems for Cluster Computing Systems. Parallel Computational Technologies. PCT 2021. Communications in Computer and Information Science, vol. 1437 / ed. by L. Sokolinsky, M. Zymbler. Cham: Springer, 2021. P. 164–177. DOI: 10.1007/978-3-030-81691-9_12.




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