Стохастический дискретный спуск

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

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

Стохастическая оптимизация в Действии

Вероятностные прогнозы и последовательное принятие решений

Принятие решений в условиях неопределенности в цепи поставок

Стохастическая оптимизация решений цепей поставок

Будущее формирует прошлое в цепи поставок

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

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

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

1. Подготовка исторических данных.
2. Генерация вероятностных прогнозов.
3. Принятие надежных решений.

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

В конечном итоге шаги (1), (2) и (3) все выполняются в Envision.

Традиционные солверы и их ограничения

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

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

2. Большинство солверов не достаточно масштабируются. Проблемы цепей поставок могут стать чрезвычайно большими: один миллион SKU может превратиться в десятки миллионов переменных после моделирования для оптимизации. Разделение цепи поставок только для адаптации солвера нецелесообразно. Солвер должен нативно обрабатывать десятки миллионов переменных.

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

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

Под капотом

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

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

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

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

Примеры

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

Пополнение модного магазина

Представьте себе розничную сеть, пополняющую магазины с определенными целями ассортимента. Например, обеспечение наличия всех размеров для одежды часто более критично, чем предложение каждого цвета, особенно если некоторые цвета очень похожи. Если клиент не может найти подходящий размер, он уходит. Напротив, запас только “популярных” или нейтральных цветов делает магазин менее привлекательным с визуальной точки зрения, уменьшая его общую привлекательность. Поэтому “яркие” предметы должны быть включены, даже если их объем продаж может быть ниже, и их общее присутствие в магазине должно оставаться тщательно сбалансированным.

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

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

Ремонт авиадвигателей

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

Стохастическая оптимизация - конкретно, стохастический дискретный спуск - обеспечивает надежное приоритетное распределение инвестиций в детали, помогая поставщику MRO (техническое обслуживание, ремонт и модернизация) минимизировать время ремонта авиадвигателей. Для каждого приобретаемого предмета основной вопрос заключается в следующем: “Учитывая этот бюджет, сколько дней задержки в ремонте я могу избежать?” Таким образом, приобретение деталей стратегически приоритизируется для сокращения времени простоя - что критично, поскольку MRO получает оплату за предоставление работоспособных двигателей, и любая задержка является прямым убытком как для MRO, так и для авиакомпании. Простой жадный подход здесь не срабатывает, потому что зависимости между деталями могут вызвать каскадные задержки. Напротив, если MRO решает не хранить определенные детали, это может не повлиять на общий график, если эти детали могут быть получены параллельно в ожидании компонентов с более длительным сроком поставки. Стохастический дискретный спуск учитывает эти взаимосвязи и возможности параллельного снабжения.

Ограниченное многократное снабжение

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

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