Тестирование алгоритмов для целочисленных квазиблочных задач оптимизации

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

Литература

[1] Щербина О.А. Локальные алгоритмы для блочно-древовидных задач дискретного программирования // Журн. вычисл. математики и матем. физики. 1985. № 8 (25). C. 1143–1154.

[2] Лемтюжникова Д.В., Свириденко А.В., Щербина О.А. Алгоритм выделения блочно-древовидной структуры в разреженных задачах дискретной оптимизации // Таврический вестник информатики и математики. 2012. № 1. C. 44–55.

[3] Авербах И.Л., Цурков В.И. Оптимизация в блочных задачах с целочисленными переменными. М.: Наука, 1995. 225 с.

[4] Lubin M., Martin K., Petra C.G., Sandikci B. On parallelizing dual decomposition in stochastic integer programming // Operations Research Letters. 2013. Vol. 41. Iss. 3. P. 252–258. DOI: 10.1016/j.orl.2013.02.003

[5] Laesanklang W., Landa-Silva D., Castillo-Salazar J.A. Mixed integer programming with decomposition to solve a workforce scheduling and routing problem // Int. Conf. on Operations Research and Enterprise Systems (ICORES 2015). 2015. P. 283–293.

[6] Heinz S., Beck J.C. Reconsidering mixed integer programming and MIP-based hybrids for scheduling // Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012). 2012. P. 211–227.

[7] Cire A., Coban E., Hooker J.N. Mixed integer programming vs. logic-based benders decomposition for planning and scheduling // Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2013). 2013. P. 325–331.

[8] Park J., Karumanchi S., Iagnemma K. Homotopy-based divide-and-conquer strategy for optimal trajectory planning via mixed-integer programming // IEEE Transactions on Robotics. 2015. Vol. 31. No. 5. P. 1101–1115.

[9] Gade D., Kucukyavuz S., Sen S. Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs // Mathematical Programming. 2014. Vol. 144. Iss. 1-2. P. 39–64. DOI: 10.1007/s10107-012-0615-y

[10] Ntaimo L. Fenchel decomposition for stochastic mixed-integer programming // Journal of Global Optimization January. 2013. Vol. 55. Iss. 1. P. 141–163. DOI: 10.1007/s10898-011-9817-8

[11] Chu Y., You F. Integration of production scheduling and dynamic optimization for multi-product CSTRs: Generalized Benders decomposition coupled with global mixed-integer fractional programming // Computers & Chemical Engineering. 2013. Vol. 58. P. 315–333. DOI: 10.1016/j.compchemeng.2013.08.003

[12] An effective problem decomposition method for scheduling of diffusion processes based on mixed integer linear programming / C. Jung, D. Pabst, M. Ham, M. Stehli, M. Rothe // IEEE Tran-sactions on Semiconductor Manufacturing. 2014. Vol. 27. No. 3. P. 357–363.

[13] Luedtke J. A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support // Mathematical Programming. 2014. Vol. 146. Iss. 1-2. P. 219–244. DOI: 10.1007/s10107-013-0684-6

[14] Integration of progressive hedging and dual decomposition in stochastic integer programs / G. Guo, G. Hackebeil, S.M. Ryan, J.P. Watson, D.L. Woodruff // Operations Research Letters. 2015. Vol. 43. Iss. 3. P. 311–316. DOI: 10.1016/j.orl.2015.03.008

[15] Mitra S., Garcia-Herreros P., Grossmann I.E. A novel cross-decomposition multi-cut scheme for two-stage stochastic programming // Computer Aided Chemical Engineering. 2014. Vol. 33. P. 241–246. DOI: 10.1016/B978-0-444-63456-6.50041-7

[16] Миронов А.А., Федорчук В.В., Цурков В.И. Минимакс в моделях транспортного типа с интегральными ограничениями. I // Известия РАН. Теория и системы управления. 2003. № 4. C. 69–81.

[17] Миронов А.А., Федорчук В.В., Цурков В.И. Минимакс в моделях транспортного типа с интегральными ограничениями. II // Известия РАН. Теория и системы управления. 2005. № 5. С. 66–86.

[18] Миронов А.А., Цурков В.И. Наследственно минимаксные матрицы в моделях транспортного типа // Известия РАН. Теория и системы управления. 1998. № 6. С. 104–121.

[19] Миронов А.А., Цурков В.И. Транспортные и сетевые задачи с минимаксным критерием // Журн. вычисл. математики и матем. физики. 1995. Т. 35. № 1. С. 24–45.

[20] Соколов А.А., Тизик А.П., Цурков В.И. Итеративный метод для транспортной задачи с дополнительными пунктами производства и потребления и квадратичным штрафом // Известия РАН. Теория и системы управления. 2013. № 4. С. 88–98.

[21] Mironov A.A., Tsurkov V.I. Network models with fixed parameters at the communication nodes // Journal of Computer and Systems Sciences International. 1995. Vol. 33. No. 3. P. 107.

[22] Symphony // Coin-or: веб-сайт. URL: https://projects.coin-or.org/SYMPHONY (дата обращения: 27.03.2017).

[23] Щербина О.А. Локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации. Дис. … д-pa физ.-мат. наук. М., 2011. 361 с.

[24] Gorry G.A., Shapiro J.F., Wolsey L.A. Relaxation methods for pure and mixed integer programming problems // Management Science. 1972. Vol. 18. No. 5. P. 229–239.

[25] Local elimination solver // GitHub.com: веб-сайт. URL: https://github.com/robionica/les (дата обращения: 27.03.2017).

[26] Концепция многозадачной ГРИД-системы с гибким распределением свободных вычислительных ресурсов суперкомпьютеров / А.П. Афанасьев, И.В. Бычков, О.С. Заикин и др. // Известия РАН. Теория и системы управления. 2017. № 4. С. 133–139.

[27] Everest: A cloud platform. URL: http://everest.distcomp.org (дата обращения: 27.03.2017).

[28] Koutsopoulos I., Papaioannou T.G., Hatzi V. Modeling and optimization of the smart grid ecosystem // Foundations and Trends in Networking. 2016. Vol. 10. No. 2–3. P. 115–316. DOI: 10.1561/1300000042 URL: http://www.nowpublishers.com/article/Details/NET-042

[29] Salah A., Hart E. A modified grid diversity operator for discrete optimization and its application to wind farm layout optimization problems // Companion Material Proceedings Genetic and Evolutionary Computation Conference. 2016. P. 977–982.

[30] A mathematical programming language // AMPL: веб-сайт. URL: https://www.ampl.com (дата обращения: 27.03.2017).

[31] Achterberg T. SCIP: Solving constraint integer programs // Mathematical Programming Computation. 2009. Vol. 1. Iss. 1. P. 1–41. DOI: 10.1007/s12532-008-0001-1

[32] Волошинов В.В., Смирнов С.А., Неверов В.С. Интеграция программных средств оптимизационного моделирования в неоднородной вычислительной среде на основе системы AMPLX. URL: http://distcomp.ru/~vladimirv/docs/nscf2015-amplx-VoloshinovVVSmirnovSANeverovVS.pdf (дата обращения: 27.03.2017).

[33] AMPLX // GitLab: веб-сайт. URL: https://gitlab.com/ssmir/amplx (дата обращения: 27.03.2017).