Параллельная реализация следящего алгоритма для решения нестационарных задач линейного программирования

Ирина Михайловна Соколинская, Леонид Борисович Соколинский

Аннотация


В статье описывается параллельный алгоритм решения нестационарных задач линейного программирования большой размерности, ориентированный на кластерные вычислительные системы. В основе алгоритма, получившего название «следящий», лежат фейеровские отображения. Алгоритм отслеживает изменения исходных данных и вносит корректировки в вычислительный процесс. При этом задача разбивается на большое количество подзадач, которые могут решаться независимо без обменов данными. Приводятся диаграммы деятельности UML, описывающие реализацию следящего алгоритма.

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


нестационарная задача линейного программирования, фейеровские отображения, следящий алгоритм, диаграммы деятельности UML, массовый параллелизм, кластерные вычислительные системы

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

PDF

Литература


Ерёмин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. 291 с.

Agmon S. The relaxation method for linear inequalities. Canad. J. Math. 1954. vol. 6, no. 3. pp. 382-392.

Motzkin T.S., Schoenberg J.J. The relaxation method for linear inequalities. Canad. J. Math. 1954. vol. 6, no. 3. pp. 393-404.

Ерёмин И.И., Попов Л.Д. Фейеровские процессы в теории и практике: обзор последних результатов // Известия высших учебных заведений. Математика. 2009. № 1. С. 44-65.

Дышаев М.М., Соколинская И.М. Представление торговых сигналов на основе адаптивной скользящей средней Кауфмана в виде системы линейных неравенств // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2013. Т. 2, № 4. С. 103-108.

Ананченко И.В., Мусаев А.А. Торговые роботы и управление в хаотических средах: обзор и критический анализ // Труды СПИИРАН. 2014. № 3 (34). С. 178-203.

Sokolinskaya I.M., Sokolinskii L.B. Parallel algorithm for solving linear programming problem under conditions of incomplete data // Automation and Remote Control. 2010. vol. 71, no. 7. pp. 1452-1460.

Rechkalov T.V., Zymbler M.L. Accelerating Medoids-based Clustering with the Intel Many Integrated Core Architecture // Proceedings of the 9th International Conference on Application of Information and Communication Technologies (AICT'2015), October 14–16, 2015, Rostov-on-Don, Russia. IEEE, 2015. pp. 413–417.

Zymbler M.L. Best-match Time Series Subsequence Search on the Intel Many Integrated Core Architecture // Proceedings of the 19th East-European Conference on Advances in Databases and Information Systems, ADBIS 2015 (Poitiers, France, September 8–11, 2015). Lecture Notes in Computer Science. vol. 9282. Springer, 2015. pp. 275–286.

Соколинская И.М., Соколинский Л.Б. Алгоритм решения нестационарных задач линейного программирования для кластерных вычислительных систем с многоядерными ускорителями // Параллельные вычислительные технологии (ПаВТ’2015): труды международной научной конференции. Челябинск: Издательский центр ЮУрГУ, 2015. С. 477-481.

Sokolinskaya I., Sokolinsky L. Solving unstable linear programming problems of high dimension on cluster computing systems // 1st Russian Conference on Supercomputing Days 2015, RuSCDays 2015; Moscow; Russian Federation; 28 September 2015 through 29 September 2015. CEUR Workshop Proceedings. vol. 1482, CEUR-WS.org 2015. pp. 420-427.

Еремин И.И. Фейеровские методы для задач выпуклой и линейной оптимизации. Челябинск: Изд-во ЮУрГУ, 2009. 200 с.

Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2011. no. 37(254), вып. 10. C. 12-21.




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