Оценка производительности крупноблочного алгоритма метода ветвей и границ в вычислительной среде Everest
Автор: Волошинов Владимир Владимирович, Смирнов Сергей Андреевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 1 (32) т.8, 2017 года.
Бесплатный доступ
В работе исследовался т.н. крупноблочный подход к реализации параллельной работы метода ветвей и границ (МВГ). Исходная задача частично-целочисленного программирования разбивается на несколько подзадач посредством фиксации значений у части целочисленных переменных. Подзадачи решаются параллельно пулом МВГ-решателей. Если в ходе решения подзадач появляется допустимое решение, с наилучшим на данный момент значением целевой функции, то это число рассылается другим решателям. Такой обмен рекордными значениями критерия позволяет взаимно ускорить решение подзадач за счет сокращения перебора вершин дерева ветвлений алгоритма МВГ. Запуск подзадач и обмен данными обеспечивается средствами платформы Everest. В результате тестирования разработанной распределенный системы на случайным образом сгенерированных задачах линейного программирования с частично-булевыми переменными было обнаружено заметное ускорение
ID: 14336105 Короткий адрес: https://sciup.org/14336105
Список литературы Оценка производительности крупноблочного алгоритма метода ветвей и границ в вычислительной среде Everest
- Л. Д. Попов. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации//Автомат. и телемех., 2007, №5. С. 171-181, URL: http://www.mathnet.ru/php/getFT.phtml?jrnid=at&paperid=993&what=fullt&option_lang=rus
- E. P. Mancini, S. Marcarelli, I. Vasilyev, U. Villano. "A grid-aware MIP solver: Implementation and case studies", Future Generation Computer Systems, V. 24. No. 2. 2008. P. 133-141.
- M. R. Bussieck, M. C. Ferris, A. Meeraus. "Grid-enabled optimization with GAMS", INFORMS Journal on Computing, V. 21. No. 3. 2009. P. 349-362.
- С. А. Смирнов, В. В. Волошинов. Эффективное применение пакетов дискретной оптимизации в облачной инфраструктуре на основе эвристической декомпозиции исходной задачи в системе оптимизационного моделирования AMPL//Программные системы: теория и приложения, Т. 7, № 1. 2016. С. 29-46, URL: http://psta.psiras.ru/read/psta2016_1_29-46.pdf
- С. А. Смирнов, В. В. Волошинов. Предварительная декомпозиция задач дискретной оптимизации для ускорения алгоритма ветвей и границ в распределенной вычислительной среде//Компьютерные исследования и моделирование, Т. 7, № 3. 2015. С. 719-725, URL: http://crm.ics.org.ru/uploads/crmissues/crm_2015_3/15746.pdf
- O. Sukhoroslov, S. Volkov, A. Afanasiev. "A Web-Based Platform for Publication and Distributed Execution of Computing Applications", Proc. 14th International Symposium on Parallel and Distributed Computing, ISPDC 2015 (Limassol, Cyprus, 29 June-01 July. 2015), IEEE, 2015. P. 175-184.
- G. Gamrath, T. Fischer, T. Gally, A. M. Gleixner, G. Hendel, T. Koch, S. J. Maher, M. Miltenberger, et al. The SCIP Optimization Suite 3.2, ZIB Report, 2016, 15-60.
- H. Mittelmann. Mixed Integer Linear Programming Benchmark, 2016, URL: http://plato.asu.edu/ftp/milpc.html
- R. Fourer, D. M. Gay, B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming, second edition, Duxbury Press/Brooks/Cole Publishing Company, 2002, 538 p.
- Е. В. Алексеева, Построение математических моделей целочисленного линейного программирования. Примеры и задачи, Учеб. пособие, НГУ, Новосибирск, 2012, 132 с.
