О проекционном методе линейного программирования
Автор: Леонид Борисович Соколинский, Александр Эдуардович Жулев, Ирина Михайловна Соколинская
Статья в выпуске: 1 т.15, 2026 года.
Бесплатный доступ
В статье рассматривается проблема разработки эффективных методов проекционного типа для решения задач линейного программирования (ЛП). Предложен новый гибридный проекционный алгоритм HAlEM (Hybrid Along Edges Movement), сочетающий идеи проекционного подхода и симплекс-метода. Алгоритм начинает работу из произвольной вершины многогранника допустимых решений и осуществляет движение вдоль его ребер к оптимальной вершине. Для вычисления направления движения используется оригинальный метод двух-факторной проекции, обеспечивающий высокую вычислительную точность для любых задач ЛП. Основным преимуществом HAlEM перед предшествующими разработками (AlFaMove, AlEM) является отказ от комбинаторного перебора всех возможных комбинаций гиперплоскостей за счет использования техники обновления матричного базиса, заимствованной из симплекс-метода. Это позволяет избежать экспоненциальной вычислительной сложности. В статье представлена параллельная версия алгоритма, основанная на модели параллельных вычислений BSF и схеме «мастер-рабочие», позволяющих получить эффективную реализацию для суперкомпьютерных систем кластерного типа. Проведены вычислительные эксперименты на эталонных задачах из репозитория Netlib-LP и на серии параметризованных задач. Результаты экспериментов демонстрируют, что HAlEM, в отличие от симплекс-метода, обладает более высоким ресурсом параллелизма, позволяя эффективно использовать до нескольких десятков процессорных узлов, и показывает хорошую масштабируемость с параллельной эффективностью не ниже 51%. При этом алгоритм обеспечивает высокую точность вычислений на уровне машинного нуля.
Линейное программирование, алгоритм HAlEM, проекционный метод, параллельная реализация, MPI, кластерная вычислительная система, исследование масштабируемости, Netlb-LP
Короткий адрес: https://sciup.org/147253967
IDR: 147253967 | УДК: 519.852, 514.172.45, 519.168 | DOI: 10.14529/cmse260101
On Projection Method of Linear Programming
The paper addresses the problem of developing efficient projection-type methods for linear programming (LP). A new hybrid projection algorithm called HAlEM (Hybrid Along Edges Movement) is proposed, combining ideas from the projection approach and the simplex method. The algorithm starts from an arbitrary vertex of the feasible solution polytope and moves along its edges toward the optimal vertex. An original two-factor projection method is used to compute the direction of movement, ensuring high computational accuracy for any LP problem. The main advantage of HAlEM over previous projection algorithms (AlFaMove, AlEM) is its avoidance of exhaustive combinatorial enumeration of all possible combinations of hyperplanes by employing a matrix basis update technique borrowed from the simplex method. This allows one to circumvent exponential computational complexity. The paper presents a parallel version of the algorithm based on the BSF parallel computing model and a master-worker scheme, enabling an efficient implementation for cluster-type supercomputer systems. Computational experiments were conducted on benchmark problems from the Netlib-LP repository and on a series of parameterized problems. The experimental results demonstrate that HAlEM, unlike the simplex method, possesses a higher degree of parallelism, allowing the efficient use of up to several dozen processor nodes, and exhibits good scalability with parallel efficiency not falling below 51%. Furthermore, the algorithm provides high computational accuracy at the level of machine epsilon.
