Стохастическое целочисленное программирование — оптимизация дискретных решений в условиях неопределенности
- Автор метода
- Dantzig, G. B.; Beale, E. M. L.
- Год
- 1955
- Тип
- Optimization under uncertainty with discrete decisions
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Стохастическое целочисленное программирование (СЦП) — это оптимизационная парадигма, которая сочетает целочисленные (дискретные) переменные решения с явным вероятностным моделированием неопределенности.
Оно направлено на поиск наилучшего «здесь-и-сейчас» решения, которое минимизирует ожидаемые затраты (или максимизирует ожидаемую выгоду) по распределению будущих сценариев, учитывая тот факт, что некоторые решения должны быть приняты до разрешения неопределенности.
Интуиция метода
Многие реальные решения являются как дискретными (строить объект или нет; назначать работника или нет), так и неопределенными (спрос, затраты и ограничения неизвестны в момент принятия решения). СЦП одновременно решает обе эти задачи. Оно моделирует неопределенное будущее как набор сценариев с ассоциированными вероятностями, а затем находит целочисленное решение, которое показывает наилучшие результаты в среднем — или которое страхует от наихудших исходов. В отличие от стохастического линейного программирования, дискретная структура делает задачу комбинаторно более сложной, но полученные решения непосредственно применимы без округления или аппроксимации.
История
Стохастическое программирование берет свое начало от Данцига (Dantzig, 1955) и Била (Beale, 1955), которые независимо предложили двухэтапные модели корректирующих действий для линейных программ в условиях неопределенности. Целочисленное расширение появилось по мере развития целочисленного программирования в 1960-х–1980-х годах. Учебник Бирджа и Луво (Birge and Louveaux, 1997) систематизировал эту область, а Клейвегт и др. (Kleywegt et al., 2002) установили метод аппроксимации выборочного среднего (Sample Average Approximation, SAA) как стандартный вычислительный подход для крупномасштабной стохастической дискретной оптимизации.
Когда применять
Используйте стохастическое целочисленное программирование, когда решения по своей природе дискретны (бинарный выбор, распределение целых единиц, назначения маршрутов), а ключевые параметры неопределенны в момент принятия решения. Оно хорошо подходит для планирования мощностей, проектирования сетей поставок, составления расписаний в условиях неопределенности спроса, диспетчеризации энергии и распределения ресурсов со случайной доходностью. НЕ используйте его, когда все переменные непрерывны (достаточно стохастического линейного программирования), когда неопределенность незначительна или полностью наблюдаема до принятия решения, когда масштаб задачи делает перечисление сценариев вычислительно неразрешимым без инфраструктуры декомпозиции, или когда актуален только один детерминированный сценарий.
Ограничения и замечания
- Вычислительная сложность быстро растет с увеличением числа сценариев и целочисленных переменных; большие экземпляры являются NP-трудными.
- Генерация сценариев требует достоверных распределений вероятностей, которые может быть трудно получить или оценить из ограниченных данных.
- Многоэтапные расширения (более двух этапов) сталкиваются с экспоненциальным ростом деревьев сценариев и редко разрешимы за пределами трех этапов.
- Требуются навыки моделирования для правильного определения осуществимости корректирующих действий, ограничений ненаблюдаемости и структур штрафов.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Явно моделирует неопределенность, а не использует точечные оценки, что приводит к решениям, устойчивым к реализованным сценариям.
- Обрабатывает дискретные и бинарные решения изначально, поэтому решения непосредственно применимы без последующего округления.
- Двухэтапная структура четко разделяет стратегические решения первого этапа от операционных корректирующих действий второго этапа.
- Поддерживает богатые структуры корректирующих действий, включая закупку ресурсов, штрафные издержки и корректирующее планирование.
- Статистические границы качества (через SAA) позволяют практикам подтверждать квазиоптимальность с количественно определенной уверенностью.
Применение
- Проектирование сети поставок в условиях стохастического спроса и сроков выполнения заказов
- Планирование расширения производства электроэнергии с неопределенным выходом возобновляемых источников
- Планирование расписания операционных в больницах с переменной продолжительностью процедур
- Планирование расписания экипажей авиакомпаний со стохастическими задержками рейсов
- Предварительное размещение гуманитарной помощи до стихийных бедствий
- Оптимизация финансового портфеля с дискретным выбором активов и доходностью на основе сценариев
Как это работает
Как это работает
Сформулируйте задачу первого этапа: выберите целочисленные (или смешанные целочисленные) переменные решения x до того, как будет раскрыта неопределенность. Определите целевую функцию, которая включает как немедленные затраты, так и ожидаемые затраты на корректирующие действия по всем сценариям. Здесь указываются ограничения, связывающие x с условиями осуществимости.
Формула
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]Представьте неопределенность через конечное множество сценариев. Каждый сценарий присваивает конкретные значения случайным параметрам (уровни спроса, затраты, доступность ресурсов). Сценарии могут быть сгенерированы путем исторической выборки, методом Монте-Карло из подобранных распределений или экспертно определенными репрезентативными случаями. Каждый сценарий имеет весовую вероятность, сумма которых равна единице.
В стандартной двухэтапной формулировке, после того как x зафиксировано и сценарий xi реализован, задача корректирующих действий (второго этапа) определяет корректирующие действия y. Задача корректирующих действий часто является линейной или целочисленной программой. Полная модель минимизирует c^T x плюс ожидаемые затраты на корректирующие действия E[Q(x, xi)].
Формула
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xРешите подзадачи сценариев для оценки затрат на корректирующие действия для каждого сценария при заданном x. Методы включают метод ветвей и границ, декомпозицию Бендерса, лагранжеву релаксацию и метод аппроксимации выборочного среднего (SAA). Для больших деревьев сценариев алгоритмы декомпозиции используют блочную структуру по сценариям.
Агрегируйте результаты подзадач для оценки ожидаемых затрат на корректирующие действия. В SAA это среднее значение по S выбранным сценариям. Полученная аппроксимация сходится к истинному ожиданию по мере увеличения S. Статистические границы качества решения могут быть рассчитаны на основе выборочной дисперсии.
Формула
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)Проверьте оптимальность или квазиоптимальность с помощью разрывов оптимальности, критериев сходимости или статистических доверительных интервалов из SAA. Если разрыв неприемлем, уточните набор сценариев, увеличьте размер выборки или ужесточите релаксации. Сообщите решение первого этапа x* и его ожидаемые общие затраты.
Частые ошибки
- Использование слишком малого количества сценариев приводит к чрезмерно уверенным решениям; использование слишком большого количества делает задачу вычислительно неразрешимой — баланс достигается с помощью диагностик сходимости SAA.
- Игнорирование целочисленности на втором этапе, когда она фактически требуется, приводит к оптимистичным оценкам затрат и неосуществимым корректирующим действиям.
- Предположение о независимости сценариев, когда параметры коррелированы (например, коррелированный спрос и цена), вносит систематическую ошибку в оценку ожидаемых затрат.
- Забывание ограничений ненаблюдаемости в многоэтапных задачах позволяет модели использовать будущую информацию, которая не была бы доступна на практике.
Часто задаваемые вопросы
Чем стохастическое целочисленное программирование отличается от робастной оптимизации?
СЦП минимизирует ожидаемые затраты по взвешенному по вероятности набору сценариев, допуская, что некоторые сценарии могут привести к высоким затратам, если они маловероятны. Робастная оптимизация минимизирует затраты в наихудшем случае по набору неопределенности, не делая вероятностных предположений. СЦП требует распределения вероятностей; робастная оптимизация требует только набора неопределенности. СЦП обычно менее консервативно, но более требовательно к данным.
Сколько сценариев необходимо на практике?
Это зависит от размерности задачи и требуемой точности. Подход аппроксимации выборочного среднего (SAA) предоставляет статистические доверительные интервалы для разрыва оптимальности. Типичные прикладные исследования используют от десятков до тысяч сценариев; диагностика сходимости (дисперсия оценки границы) направляет выбор. Для структурированных задач методы сокращения сценариев (например, Heitsch-Romisch) могут существенно сократить количество сценариев.
Может ли стохастическое целочисленное программирование обрабатывать более двух этапов?
Да, но многоэтапное СЦП значительно сложнее. Дерево сценариев экспоненциально растет с числом этапов, и ограничения ненаблюдаемости должны применяться в каждом узле. На практике трехэтапные модели являются нормой для разрешимых приложений; за их пределами обычно требуются аппроксимации, такие как скользящий горизонт или сокращение дерева сценариев.
Какое программное обеспечение может решать модели стохастического целочисленного программирования?
Общие решатели включают CPLEX и Gurobi (через алгебраические языки моделирования, такие как AMPL, JuMP в Julia или PuLP/Pyomo в Python), которые поддерживают декомпозицию сценариев. Специализированные фреймворки стохастического программирования включают PySP (Python), решатели формата SMPS и пакет Julia StochasticPrograms.jl, который реализует SAA и прогрессивное хеджирование.
Является ли стохастическое целочисленное программирование тем же самым, что и стохастическое смешанное целочисленное программирование?
Стохастическое целочисленное программирование — это более широкий класс; стохастическое смешанное целочисленное программирование (ССЦП) относится конкретно к моделям, где некоторые переменные являются непрерывными, а другие — целочисленными на одном или обоих этапах. ССЦП является наиболее общей и наиболее часто встречающейся формой на практике.
Похожие методы
Источники
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 978-1-4614-0237-4Скопировано.Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
Открыть ссылку DOIСкопировано.