Speaker
Description
Солвер глобальной и дискретной оптимизации SCIP [1], scipopt.org, развивается с 2005 года и предназначен для решения задач математического программирования, в т.ч. с дискретными переменными, методом ветвей-и-границ-и-отсечений (branch-and-bound-and-cut). С конца 2022 года он свободно доступен в исходных кодах по лицензии Apache 2.0. Хотя по производительности SCIP уступает коммерческим солверам (Gurobi, COPT, CPLEX), он очень полезен в поисковых исследованиях поскольку применим для более широкого класса нелинейных задач, по сравнению с Gurobi и COPT. Типовой сценарий работы с солвером SCIP: подготовка формальной модели задачи и исходных данных для оправки их солверу, получение решения и анализ результатов. Как показала практика, одним из удобных вариантов является использование файлов в форматах стандарта AMPL, ampl.com: NL-файлов для исходной задачи и SOL-файлов для полученного решения. Для генерации NL-файлов и чтения результатов из SOL-файлов удобно применять свободно доступный пакет Pyomo, pyomo.org.
Производительность SCIP может быть существенно повышена за счет работы в параллельном режиме через библиотеку UG (ubiquity generator), ug.zib.de. Разработчики предлагают две параллельные реализации [2, 3]: многопоточный FiberSCIP, для многопроцессорных систем с общей памятью; ParaSCIP, для кластеров с коммуникацией по технологией MPI. К сожалению, эти параллельные солверы не имеют встроенной поддержки AMPL-форматов, что затрудняет их широкое применение.
В докладе описывается простой способ адаптации этих параллельных солверов к AMPL-форматам, где в роли «транслятора» форматов входных и выходных данных используется «обычный» солвер SCIP и несложный Bash-скрипт. В частности, это позволяет применять FiberSCIP и ParaSCIP непосредственно из Python-приложений на базе Pyomo или в сервисах оптимизационного моделирования на основе Everest, optmod.distcomp.org.
Работа выполнена в рамках государственного задания ИППИ РАН, утвержденного Минобрнауки России.
Ссылки
-
K. Bestuzheva, A. Gleixner, T. Koch, M.E. Pfetsch, Y. Shinano, S. Vigerske et al. The SCIP Optimization Suite 9.0 // Optimization Online, 2024, 36 pp. https://optimization-online.org/?p=25734
-
Yuji Shinano. ParaSCIP and FiberSCIP libraries to parallelize a customized SCIP solver. SCIP Workshop 2014, 30.09-2.10, 2014, Zuse Institute Berlin, https://www.scipopt.org/workshop2014/parascip_libraries.pdf
-
Y. Shinano et al. FiberSCIP - A Shared Memory Parallelization of SCIP // INFORMS Journal on Computing, 2018, 30(1), P. 11-30. https://doi.org/10.1287/ijoc.2017.0762
