Эффективное применение пакетов дискретной оптимизации в облачной инфраструктуре на основе эвристической декомпозиции исходной задачи в системе оптимизационного моделирования AMPL
Автор: Смирнов Сергей Андреевич, Волошинов Владимир Владимирович
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Методы оптимизации и теория управления
Статья в выпуске: 1 (28) т.7, 2016 года.
Бесплатный доступ
Пусть процесс поиска решения в некоторой задаче дискретной оптимизации пакетом, реализующим алгоритм ветвей и границ, занимает определенное время. Можно ли ускорить решение той же задачи если нам доступна вычислительная среда, где можно запустить несколько одновременно работающих «экземпляров» того же пакета оптимизации? В докладе рассматривается способ получить заметное ускорение для пакетов с открытым кодом в виртуальной многопроцессорной вычислительной среде. В основе подхода: (1) предварительная декомпозиция исходной задачи на несколько подзадач путем фиксации целочисленных (булевых) значений части дискретных переменных, выбираемых согласно некоторому эвристическому правилу, реализованному в форме программы на высокоуровневом языке оптимизационного моделирования AMPL; (2) одновременное решение полученных подзадач экземплярами того же пакета, с добавленной возможностью обмена найденными рекордными значениями целевой функции. Предлагаемый подход привлекает относительной простотой программной реализации и демонстрируется на примерах решения задачи коммивояжера и составления расписаний назначения работ исполнителям
Дискретная оптимизация, метод ветвей и границ, предварительная эвристическая декомпозиция
Короткий адрес: https://sciup.org/14336187
IDR: 14336187
Effective use of discrete optimization solvers in cloud infrastructure on the basis of heuristic decomposition of the initial problem by optimization modeling system AMPL
Let the process of finding a solution in some problem of discrete optimization by a package implementing the algorithm of branches and boundaries take a certain time. Is it possible to speed up the solution of the same problem if we have a computing environment where we can run several simultaneously running "instances" of the same optimization package? The report discusses a way to get a noticeable acceleration for open source packages in a virtual multiprocessor computing environment. The approach is based on the following: (1) preliminary decomposition of the original problem into several sub-tasks by fixing the integer (boolean) values of a part of the discrete variables selected according to some heuristic rule implemented in the form of a program in the high-level language of AMPL optimization modeling; (2) simultaneous solution of the subtasks obtained by the copies of the same package, with the added possibility of exchanging the found record values of the objective function. The proposed approach attracts relative simplicity of the software implementation and is demonstrated by examples of solving the traveling salesman problem and scheduling the assignment of work to the executors
Список литературы Эффективное применение пакетов дискретной оптимизации в облачной инфраструктуре на основе эвристической декомпозиции исходной задачи в системе оптимизационного моделирования AMPL
- Л. Д. Попов. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации//Автоматика и телемеханика, 2007, №5. С. 171-181.
- 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.
- Е. В. Алексеева, Построение математических моделей целочисленного линейного программирования. Примеры и задачи, Учеб. пособие, НГУ, Новосибирск, 2012, 132 с.
- 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.
- J. Kallrath, Algebraic Modeling Systems: Modeling and Solving Real World Optimization Problems, Applied Optimization, vol. 104, Springer Science & Business Media, 2012, 254 p.
- T. Koch, T. Ralphs, Y. Shinano. Could we use a million cores to solve an integer program? Mathematical Methods of Operations Research, V. 76. No. 1. 2012. P. 67-93.
