Skip to content
Назад к результатам поиска

Стохастическое смешанно-целочисленное программирование — Оптимизация в условиях неопределенности с дискретными и непрерывными решениями

Автор метода
Birge, J. R.; Louveaux, F.; Sen, S.
Год
1990s–2000s
Тип
Stochastic optimization model
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

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

Интуиция метода

Многие реальные задачи планирования требуют принятия решений «да/нет» или решений в целых числах — построить объект или нет, назначить целое число транспортных средств — однако будущее неопределенно. SMIP формализует это, рассматривая совокупность правдоподобных будущих сценариев и выбирая обязательства первой стадии (до раскрытия неопределенности), которые минимизируют ожидаемые затраты или максимизируют ожидаемую выгоду по всем сценариям. Целочисленные ограничения делают задачу комбинаторно сложной, но алгоритмы декомпозиции используют структуру сценариев, чтобы сделать большие экземпляры решаемыми.

История

Стохастическое программирование зародилось с Данцигом (1955) и Биллом (1955) как двухстадийное ЛП. Смешанно-целочисленное расширение получило заметное развитие в 1990-х годах с адаптациями L-образного метода для целочисленного отклика Лапортом и Луво (1993) и всесторонним изложением в учебнике Бирджа и Луво 1997 года. Алгоритм C3/D2 Сена и Хигла (2005) продвинул масштабируемые решатели SMIP, утвердив эту область как зрелую дисциплину в рамках исследования операций.

Когда применять

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

Ограничения и замечания

  • Вычислительная сложность растет комбинаторно с числом сценариев и целочисленных переменных; большие экземпляры могут быть неразрешимы без эффективной декомпозиции.
  • Требует явных распределений вероятностей или наборов сценариев — неправильно специфицированные модели неопределенности приводят к решениям, которые плохо работают вне выборки.
  • Двухстадийные формулировки могут чрезмерно упрощать многопериодные решения; многостадийный SMIP значительно сложнее.
  • Целочисленный отклик второй стадии разрушает выпуклость, используемую стандартными отсечениями Бендерса, требуя специализированных целочисленных L-образных отсечений.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Обрабатывает комбинаторные дискретные решения в условиях неопределенности в единой согласованной оптимизационной модели.
  • Производит хеджированные планы первой стадии, которые балансируют ожидаемую производительность по всем сценариям.
  • Метрики VSS и EVPI обеспечивают прозрачное обоснование ценности стохастического моделирования.
  • Алгоритмы декомпозиции (L-образный, прогрессивное хеджирование) масштабируются до больших наборов сценариев.
  • Широко поддерживается коммерческими решателями (CPLEX, Gurobi) и языками моделирования (AMPL, Pyomo).

Применение

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

Как это работает

Как это работает

1

Определите переменные решения: решения первой стадии x, принимаемые до раскрытия неопределенности (среди них целочисленные и/или бинарные), и переменные отклика второй стадии y(xi), принимаемые после материализации сценария xi. Укажите коэффициенты целевой функции, матрицы ограничений и распределение вероятностей или дискретный набор сценариев для неопределенных параметров.

2

Постройте конечный набор сценариев {xi_1, ..., xi_S} с соответствующими вероятностями {p_1, ..., p_S}, аппроксимирующий лежащее в основе распределение. Сценарии могут быть получены из исторических данных, экспертных оценок, выборки Латинского гиперкуба или методов согласования моментов. Качество сценария напрямую влияет на качество решения.

3

Сформулируйте детерминированный эквивалент: минимизировать c'x + sum_s p_s Q(x, xi_s) при соблюдении ограничений первой стадии и целочисленности. Q(x, xi_s) — это функция стоимости отклика второй стадии — оптимальная стоимость действий отклика при заданных x и сценарии xi_s. Совместная задача — это большая MIP, размер которой растет с числом сценариев.

Формула
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}
4

Решайте с помощью алгоритмов декомпозиции — L-образный метод (декомпозиция Бендерса) для выпуклых вторых стадий, метод ветвей и отсечений со сценарными подзадачами или прогрессивное хеджирование для сценарно-параллельной декомпозиции. Целочисленность на второй стадии требует дополнительных отсечений (целочисленные L-образные отсечения, lift-and-project). Современные решатели (CPLEX, Gurobi с обратными вызовами или специализированные библиотеки SMIP) реализуют эти процедуры.

5

Оцените решение с помощью Стоимости стохастического решения (VSS = EEV - RP) и Ожидаемой стоимости совершенной информации (EVPI = RP - WS), где RP — оптимальное значение задачи отклика, EEV — ожидаемая стоимость использования решения на основе среднего значения детерминированной задачи, а WS — стоимость ожидания и наблюдения. Эти метрики количественно определяют выгоду от явного моделирования неопределенности.

Частые ошибки

  • Использование слишком малого числа сценариев недостаточно представляет неопределенность, приводя к чрезмерно уверенным решениям; слишком большое число делает модель вычислительно невыполнимой.
  • Путаница ролей переменных первой и второй стадии приводит к формулировкам, которые не учитывают временную последовательность раскрытия информации.
  • Опора на решение, основанное на ожидаемой стоимости (игнорируя стохастичность), может быть значительно субоптимальной — всегда вычисляйте VSS, чтобы обосновать усилия по SMIP.
  • Пренебрежение целочисленностью на стадии отклика, когда она фактически присутствует, приводит к релаксации, решение которой может быть невыполнимым на практике.
  • Параметры решателя по умолчанию для MIP часто требуют настройки (приоритеты ветвления, стратегии отсечений) в рамках SMIP-фреймворков декомпозиции.

Часто задаваемые вопросы

Чем SMIP отличается от обычного смешанно-целочисленного программирования?

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

Сколько сценариев мне нужно?

Универсального правила нет. Иногда достаточно 10–50 сценариев для стабильных решений первой стадии; другим задачам требуются тысячи. Методы сокращения сценариев и тесты на стабильность (проверка того, что оптимальное решение не меняется при добавлении большего числа сценариев) помогают определить адекватность.

Что такое L-образный метод?

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

Когда следует использовать прогрессивное хеджирование вместо L-образного метода?

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

Может ли SMIP обрабатывать более двух стадий?

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

Похожие методы

Источники

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.

    ISBN: 9780387982175
    Скопировано.
  2. Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.

    Открыть ссылку DOI
    Скопировано.