Латентная оптимизация

Латентная оптимизация — это парадигма оптимизации, разработанная компанией Lokad, нацеленная на решение сложных комбинаторных задач. Она также справляется со стохастическими задачами, возникающими в условиях неопределенности. Латентная оптимизация представляет собой прорыв для таких проблем, как планирование распределения ресурсов. В отличие от классических решателей, работающих в пространстве решений, латентная оптимизация действует в пространстве стратегий. Этот подход обеспечивает быструю переоптимизацию по мере изменения условий.

Обзор технологии

Латентная оптимизация, представленная в 2024 году, является вторым поколением технологий оптимизации общего назначения, разработанных компанией Lokad. Она решает более сложные комбинаторные задачи, чем те, что решаются посредством стохастического дискретного спуска, хотя и обладает несколько меньшей масштабируемостью.

Концептуально, специалисты по цепям поставок в Lokad разрабатывают конвейер обработки данных, включающий следующие этапы:

1. Подготовить исторические данные.
2. Сгенерировать вероятностные прогнозы.
3. Сформировать надежную стратегию принятия решений.
4. Переоптимизировать в последний момент при измененных условиях.

Исторические данные подготавливаются с использованием универсальных возможностей по обработке данных Envision; Envision — это предметно-ориентированный язык программирования Lokad. Затем вероятностные прогнозы создаются с помощью дифференцируемого программирования, парадигмы, идеально подходящей для вероятностного моделирования и рассматриваемой в Envision как первостепенный элемент.

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

Все четыре этапа — (1), (2), (3) и (4) — выполняются в Envision.

Ограничения традиционных решателей

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

Алгоритмы метода ветвей и границ (и все их варианты) опираются на разбиение допустимой области на более мелкие подзадачи (разветвление) и применение релаксаций (ограничивающих оценок) для отсечения больших участков пространства поиска. Такой подход плохо работает для задач цепей поставок, поскольку эти задачи остаются слишком открытыми. Хотя пространство решений строго ограничено, оно по-прежнему огромно. Простого выполнения ограничений недостаточно для получения хорошего решения, что подрывает основную идею разбиения.

Алгоритмы локального поиска (и все их варианты) основаны на итерации по одной или нескольким текущим решениям с анализом близких вариантов. К сожалению, этот метод также показывает слабые результаты, поскольку понятие «локальности» не имеет четкого определения в этих задачах. Учитывая, насколько строго ограничены эти сценарии, большинство локальных корректировок решения нарушают столь многие ограничения, что процесс поиска не может обеспечить улучшенное решение.

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

Под капотом

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

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

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

Пример: Планирование работы авиационного производства

Рассмотрим авиационного производителя и один из его производственных участков. На этом участке собирается критически важный компонент для самолёта. Общая цель — максимизировать пропускную способность участка с учетом имеющихся ресурсов (люди и промышленное оборудование).

Процесс сборки включает около 100 различных операций. Также имеется примерно 20 доступных слотов для выполнения этих операций, каждый из которых обладает своими характеристиками. Некоторые операции могут выполняться только в определённых слотах. Операции связаны сложным графом зависимостей, но в отличие от автомобильной сборочной линии, этот граф не представляет собой строгость последовательность; имеется значительная гибкость в окончательной последовательности выполнения задач.

Кроме того, некоторые операции требуют использования определённого оборудования, которого на участке имеется в ограниченном количестве. Многие операции также зависят от наличия необходимого запаса материалов; иногда поставки необходимых деталей задерживаются. Число сотрудников, одновременно работающих над операцией для ускорения её выполнения, варьируется от 1 до 5 человек.

Примерно 100 техников работают на участке, распределяясь по сменам численностью от 20 до 30 человек. Каждый техник имеет один из трёх уровней квалификации для каждой операции. Самый высокий уровень позволяет технику выполнять операцию и проверять работу других. Средний уровень дает технику возможность выполнять операцию и самостоятельно проверять свою работу. Самый низкий уровень позволяет технику выполнять операцию, но требует проверки со стороны коллеги с высшей квалификацией.

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

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

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