Как решать задачи оптимизации без зарубежных солверов

Зачем нужны солверы, как обойтись без Gurobi и IBM и почему не стоит обращаться к университетам

Автор: Антон Ларин, Сооснователь и CEO SigmaDevs и автор тг-канала "Есть мысли"

В марте 2022 ключевые зарубежные поставщики объявили об уходе с российского рынка. Среди них оказались американские программы-солверы. Из-за этого бизнес оказался в непростой ситуации выбора: пользоваться опенсорсными решениями или вообще отказаться от солверов. Разберемся, что это такое и как лучше поступать в сложившихся обстоятельствах.

Солвер – это программно-аппаратный комплекс, с помощью которого можно решать сложные математические задачи по оптимизации. В соответствии с набором условий солверы перебирают варианты решения и выбирают наилучшее. Их используют в различных отраслях:

Польза таких комплексов заключается в том, что с ними задачи решаются быстрее, а показатели компании увеличиваются за счет оптимальных решений. Чтобы понять, насколько быстрее, приведу пример: некоторые задачи математической оптимизации, которые сегодня можно решить за одну секунду, в 1991 году потребовали бы 55 лет для решения.

Ещё одно преимущество солверов состоит в том, что с их помощью можно сгенерировать множество сценариев по типу “что-если”, оценить и сравнить потенциальное влияние на бизнес-процессы, а также определить наилучший. Например, Национальная футбольная лига (НФЛ) использует математическую оптимизацию для автоматического создания и анализа более 50 000 возможных сценариев составления расписания. Помогает им в этом солвер, который быстро создает огромную выборку расписаний-кандидатов для выбора.

В зависимости от задач, которые способны решать солверы, их можно разделить на два типа. Первый – промышленные или универсальные солверы, которым посильны задачи различной направленности. Самые известные из них – это Gurobi и IBM.

Ещё есть специализированные солверы, которые дешевле промышленных, но могут работать в рамках своей специфики с ограниченным набором данных. В России примером такого солвера является Яндекс.Маршрутизация.

Помимо этих решений существуют общедоступные Open Source-солверы: COIN-OR, SCIP, GLPK и другие. Недостаток опенсорсных солверов заключается в том, что они работают в несколько раз медленнее, чем их коммерчерские аналоги, и решают меньшее количество моделей. Например, опенсорсный решатель сможет решить 48 из 87 моделей, а коммерческий – 86.

Иными словами, в открытых солверах сложнее замоделировать и решить задачу, нужен математик, который сформулирует задачу нужным образом. Ну, и конечно же, подобные решения не лишены ошибок, на исправление которых нет постоянной техподдержки. Это тоже стоит учитывать при выборе опенсорсного солвера.

Когда с российского рынка ушли известные зарубежные солверы, это означало только одно – возросшую необходимость компаний переходить на отечественные аналоги. Основная проблема заключается в том, что сейчас в России пока еще нет солвера, который мог бы сравниться с гигантами вроде IBM или Gurobi. Разработать подобные решения с нуля – задача, которую можно выполнить только за несколько лет, но никак не месяцев. Известно, что попытки создать российский аналог предпринимаются – например, на одной из кафедр МФТИ уже разрабатывают кастомное решение для оптимизационных задач ВТБ.

Компании, ранее использовавшие зарубежные промышленные солверы, сейчас вынуждены переходить на бесплатные аналоги. Но, как говорилось выше, это не является наилучшим выходом из ситуации.

Сейчас порог входа на решение математических задач стал выше. Раньше компания могла обратиться с задачей к студенту, который бы написал модель и она бы решилась на коммерческом солвере. Сейчас такой вариант не сработает — доступные решения требуют не только университетского уровня знаний по математике, но еще и специфического опыта. В связи с этим у бизнеса появляется запрос на услуги профильных команд, которые специализируются на математике.

Особенность таких команд в том, что они уже имеют нужную экспертизу в решении похожих задач, а заодно математические формулировки, которые доказали свою эффективность в разных проектах. Задача же команды будет заключаться в том, чтобы правильно сформулировать задачу и применить имеющийся опыт так, чтобы даже опенсорсные солверы с ней справились. Поэтому если у компании есть необходимость в решении оптимизационных задач, то в текущих условиях лучше обращаться не к университетам, но к командам математиков, которые давно работают на рынке и специализируются в решении таких задач. Это поможет сохранить бюджет и получить максимальный эффект от оптимизации.

Если у вас есть задача, для решения которой необходима математическая оптимизация, вы можете проконсультироваться по проекту здесь.