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

Робастное целочисленное программирование — Оптимизация в условиях неопределенности с ограничениями целочисленности

Автор метода
Bertsimas, D. and Sim, M.
Год
2003
Тип
Deterministic robust optimization with integer variables
Семейство
Simulation / optimization

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

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

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

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

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

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

Многие реальные решения — производственные расписания, проектирование сетей, распределение ресурсов — включают целые числа (нельзя произвести пол-единицы или построить пол-объекта) и неопределенные данные (колебания затрат, спроса, времени в пути). Классическое целочисленное программирование игнорирует неопределенность и может привести к решениям, которые плохо работают, когда входные данные отличаются от оценок. Робастное целочисленное программирование явно моделирует эту неопределенность через множество неопределенности и находит целочисленное решение, которое наилучшим образом работает в наихудшем случае. Подход Bertsimas-Sim использует параметр бюджета неопределенности для контроля консерватизма: при нулевом бюджете задача сводится к детерминированному целочисленному программированию; по мере роста бюджета решения становятся все более защищенными от возмущений данных, ценой ухудшения значения целевой функции.

История

Систематическое исследование робастной дискретной оптимизации было продвинуто Bertsimas и Sim в их статье 2003 года, представляющей модель бюджета неопределенности для дискретных задач, основанную на более ранних работах по робастному ЛП Ben-Tal и Nemirovski (1998) и El Ghaoui и Lebret (1997). Bertsimas и Sim показали, что робастные двойственные аналоги целочисленных программ при неопределенности бюджета остаются разрешимыми MIP, что стимулировало широкое применение в логистике, проектировании сетей и планировании. Монография 2009 года Ben-Tal, El Ghaoui и Nemirovski обобщила теоретические основы робастной оптимизации в непрерывных и дискретных условиях.

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

Использовать робастное целочисленное программирование, когда решения включают дискретные выборы (бинарное назначение, проектирование сети, планирование, определение размера партии) и входные данные неопределенны, но ограничены в известном множестве. Оно предпочтительнее стохастического целочисленного программирования, когда распределение вероятностей неопределенности неизвестно или ненадежно и требуется гарантия наихудшего случая. НЕ использовать RIP, когда неопределенность чисто стохастическая с хорошо оцененными распределениями (использовать стохастическое программирование), когда задача чисто непрерывная (использовать робастное линейное программирование), когда множество неопределенности слишком консервативно и цена робастности неприемлема, или когда размер задачи делает даже номинальное целочисленное программирование неразрешимым.

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

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

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

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

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

Применение

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

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

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

1

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

Формула
\min_{x \in \mathcal{X}} \max_{\xi \in \mathcal{U}} c(\xi)^\top x \quad \text{s.t.} \quad A(\xi)x \leq b,\; x \in \mathbb{Z}^n
2

Определить множество неопределенности U, которое охватывает правдоподобный диапазон вариации параметров. Распространенные варианты включают коробочные множества (независимые интервальные границы для каждого параметра), эллипсоидальные множества (коррелированная неопределенность) и множество бюджета неопределенности Bertsimas-Sim, где одновременно отклоняются не более Gamma параметров от их номинальных значений. Бюджет Gamma является ключевым рычагом консерватизма.

Формула
\mathcal{U} = \{\xi : \|\xi - \hat{\xi}\|_\infty \leq \Gamma\} \quad (\text{budget-of-uncertainty, Bertsimas-Sim})
3

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

4

Решить переформулированную робастную целочисленную программу с помощью стандартного решателя MIP (CPLEX, Gurobi, SCIP) или специализированного метода ветвей и границ с процедурами робастного оценивания. Для больших задач могут применяться методы декомпозиции, такие как декомпозиция Бендерса или генерация столбцов и ограничений, для разделения основной целочисленной задачи и состязательной подзадачи.

5

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

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

  • Установка бюджета неопределенности Gamma слишком высокой приводит к чрезвычайно консервативным, практически бесполезным решениям; рекомендуется калибровать Gamma по частоте исторических отклонений.
  • Пренебрежение проверкой того, что переформулировка робастного двойственного аналога действительна для выбранного множества неопределенности — некоторые переформулировки применимы только к определенным типам множеств (например, бюджетным, но не эллипсоидальным).
  • Путаница робастного целочисленного программирования со стохастическим целочисленным программированием: RIP не оптимизирует ожидаемую производительность и не требует дерева сценариев или распределения вероятностей.
  • Игнорирование анализа цены робастности — практикующие специалисты всегда должны сравнивать робастные и номинальные значения целевой функции, чтобы судить, стоит ли защита затрат.
  • Применение RIP к задачам, где неопределенность нелинейно влияет на правую часть, без проверки того, что результирующая подзадача остается разрешимой.

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

Чем робастное целочисленное программирование отличается от стохастического целочисленного программирования?

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

Что такое бюджет неопределенности и как его выбрать?

Бюджет Gamma ограничивает количество одновременно отклоняющихся от номинальных значений неопределенных параметров. Когда Gamma равно нулю, модель сводится к детерминированному ЦП. По мере увеличения Gamma решения становятся более робастными, но и более дорогими. Практическое правило — установить Gamma, используя исторические данные: если в временном окне обычно отклоняется не более k параметров, установите Gamma равным k. Альтернативно, Bertsimas и Sim предоставляют вероятностные границы нарушения ограничений для заданного Gamma.

Остается ли робастный двойственный аналог целочисленной программы целочисленной программой?

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

Когда робастное целочисленное программирование вычислительно разрешимо?

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

Может ли робастное целочисленное программирование обрабатывать множественные цели?

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

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

Источники

  1. Bertsimas, D., Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1-3), 49-71.

    Открыть ссылку DOI
    Скопировано.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Скопировано.