Сегодня все больше компаний пытается повысить эффективность производства при помощи современных технологий. Задачи оптимизации возникают во всех дисциплинах: они встречаются и в информатике, и в экономике, и в медицине, и во многих других областях. Чем больше спрос, тем больше различных алгоритмов оптимизации предлагает рынок.
Самым эффективным (и ресурсозатратным) вариантом будет использование квантового компьютера, ведь он способен одновременно просчитывать разные варианты и выдавать лучший из них. Сейчас такого компьютера, способного выполнять актуальные задачи бизнеса, еще не существует. Есть только прототипы. Когда появится такая мощная вычислительная машина, сказать пока сложно. IBM в своей дорожной карте называет срок в 10 лет, и это еще очень оптимистичные прогнозы.
Однако многие компании хотят получить выгоду уже здесь и сейчас, поэтому используют, например, алгоритмы, которые вдохновлены явлениями квантовой физики, но работают и на традиционных машинах. Для их реализации нужна программа-солвер.
Ведущие зарубежные игроки в сфере оптимизации, такие как
Основное преимущество квантовых машин и их эмуляторов состоит в параллельности поиска. Солвер может «охватить взглядом» сразу большую часть пространства, одновременно оценивая ситуацию в каждой её точке. Классические же подходы оценивают ситуацию в одной из точек пространства на каждой итерации. И спрос заказчиков на количество возможных переменных и скорость квантовых машин и эмуляторов далеко не всегда получается удовлетворить.
Чем больше переменных, тем монструозней выглядит математическая запись, и тем дольше будет искаться решение. К тому же QUBO не самая поворотливая форма записи, и переделывать в ней что-то очень сложно. Это приводит к тому, что компании, которые занимаются оптимизацией, обычно находят одну область, где у них уже получилось эффективно все настроить, и в ней и остаются.
Частично закрыть эту проблему способны логические алгоритмы. В их случае задачи сформулированы не в виде алгебраических формул, а в виде высказываний. Поэтому вместо знаков умножения и деления — операции И/ИЛИ и подобные. Во время анализа таких логических высказываний зачастую проще выделить возможные «структурные» противоречия между требованиями и сразу отсечь очень большие, неподходящие части пространства, где решения нет или оно заведомо не оптимально.
Такой подход позволяет эффективно решать задачи с очень большим числом переменных на классических компьютерах. Это делает его ближе к квантовым машинам по возможности охвата пространства поиска. Основные проблемы здесь возникают на этапе перевода с человеческого на логический язык и далее во внутреннее представление решателя. Процесс трансляции у больших задач может занимать больше времени, чем последующий поиск решения. Больше ограничений и длиннее запись — меньше пространство для поиска и быстрее решение.
Как выглядит процесс изнутри: описываются ограничения и выбирается некоторый критерий, по которому оценивается оптимальность, или, по-математически, целевая функция. Например, минимизация расходов. Транслятор переводит это в логические выражения для некоторого значения цели. После обработки солвер ставит вопрос: имеет ли эта задача решение при заданных значениях?
Если проверка выполнимости пройдена, то солвер пытается уменьшить значение целевой функции (то есть сэкономить ещё). И так происходит до тех пор, пока не будет найден вариант, соответствующий теоретическому минимуму целевой функции для задачи, или пока у солвера не закончится время.
В последнем случае решение может оказаться не оптимальным, но на практике удобнее остановиться именно на нём. Например, найти самый невыгодный маршрут с точностью 98%, потратив на вычисления минуту, вместо того, чтобы искать лучшее решение в течение часа.
Если сделать транслятор, который понимает широкий класс задач, то солвер получается универсальным. Он может оптимизировать как графикование производства, так и планирование доставок на районе, вне зависимости от дополнительных условий или переменных. Это значительно сэкономит бюджеты и ресурсы многих компаний. Поэтому так важно сейчас запустить свой солвер в России, работающий и с математическими, и с логическими алгоритмами, который мог бы заместить решения зарубежных компаний Gurobi и CPLEX, мировых лидеров индустрии.
