Робастное линейное программирование — Оптимизация в условиях неопределенности
- Автор метода
- Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
- Год
- 1999–2004
- Тип
- Uncertainty-robust linear optimization
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Робастное линейное программирование (RLP) расширяет классическое линейное программирование для обработки неопределенности в данных задачи — коэффициентах затрат, коэффициентах ограничений или правых частях — требуя, чтобы решения оставались допустимыми и близкими к оптимальным при всех реализациях неопределенных параметров в пределах заданного множества неопределенности.
Оно заменяет вероятностные предположения гарантиями наихудшего случая, что делает его практичным, когда знания о распределении ограничены.
Интуиция метода
Обычное линейное программирование находит лучшее решение, предполагая, что все данные известны точно. На практике коэффициенты оцениваются, прогнозируются или измеряются с ошибкой. RLP ставит вопрос: какое лучшее решение остается допустимым независимо от того, как неопределенные параметры изменяются в допустимом диапазоне? Аналитик указывает множество неопределенности — ящик, эллипсоид или полиэдральную область — и решатель находит план, который оптимален для наихудшего случая внутри этого множества. Формулировка Берцимса и Сима «бюджет неопределенности» позволяет аналитику настраивать консерватизм: параметр Гамма контролирует, сколько коэффициентов могут одновременно отклоняться, интерполируя между номинальной ЛП и полностью консервативным наихудшим случаем.
История
Робастная оптимизация была прочно теоретически обоснована Бен-Талом и Немировски (1999), которые показали, что неопределенные линейные программы с эллипсоидальными множествами неопределенности приводят к трактуемым программам второго порядка. Берцимс и Сим (2004) ввели концепцию «бюджета неопределенности», которая сохраняет переформулировку как линейную программу и делает робастность настраиваемой с помощью одного параметра, что значительно расширило практическое применение в исследовании операций и инженерии.
Когда применять
Используйте RLP, когда неопределенность данных реальна, но распределения вероятностей неизвестны или ненадежны, например, при планировании цепочек поставок с неопределенным спросом, диспетчеризации энергии с ошибками прогнозирования или формировании финансового портфеля при неоднозначных доходностях активов. Он подходит, когда допустимость ограничений при всех сценариях является не подлежащей обсуждению. Избегайте RLP, когда неопределенность незначительна по сравнению с масштабом целевой функции, когда распределения вероятностей хорошо охарактеризованы (предпочтительнее стохастическое программирование), когда число неопределенных параметров настолько велико, что робастный аналог становится неразрешимым, или когда сценарий наихудшего случая нереалистично пессимистичен для данного приложения.
Ограничения и замечания
- Ориентация на наихудший случай может привести к чрезмерно консервативным решениям, когда крайние сценарии крайне маловероятны.
- Эллипсоидальные множества неопределенности дают трактуемые программы второго порядка, но уже не чистые ЛП, что увеличивает требования к решателю.
- Требует от аналитика указания множества неопределенности, что само по себе является модельным выбором, существенно влияющим на результаты.
- Не предоставляет напрямую утверждений о вероятности нарушения; стохастическое программирование лучше, если важны вероятности в хвосте распределения.
- Сводится к номинальной ЛП при Гамма = 0, не предоставляя защиты от неопределенности.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Предоставляет строгие гарантии допустимости в наихудшем случае без необходимости предположений о распределении.
- Формулировка бюджета Берцимса-Сима дает трактуемый аналог ЛП, решаемый стандартными решателями.
- Бюджет робастности Гамма дает аналитику интуитивно понятный регулятор для компромисса между качеством решения и консерватизмом.
- Вычислительно эффективен — робастные аналоги для бюджетных множеств имеют схожую сложность с исходной ЛП.
- Особенно хорошо подходит для задач, где нарушение ограничений дорого или небезопасно.
Применение
- Проектирование сети цепочки поставок с неопределенными транспортными расходами и спросом
- Диспетчеризация электроэнергетических систем при неопределенности прогнозов возобновляемой энергии
- Оптимизация портфеля при неоднозначных диапазонах доходности активов
- Планирование лучевой терапии при неопределенности движения пациента
- Составление расписания экипажей авиакомпаний при неопределенности задержек рейсов
- Распределение водных ресурсов при неопределенности осадков и испарения
Как это работает
Как это работает
Сформулируйте номинальную задачу линейного программирования: минимизировать линейную целевую функцию c^T x при линейных неравенствах Ax <= b и неотрицательности. Определите, какие коэффициенты — обычно элементы матрицы ограничений a_ij — являются неопределенными. Этот шаг аналогичен стандартному моделированию ЛП, но помечает каждый неопределенный параметр.
Формула
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0Постройте множество неопределенности U, которое охватывает диапазон допустимых значений параметров без необходимости в распределении вероятностей. Распространенные варианты — множества-ящики (каждый параметр изменяется независимо в пределах [a_bar - a_hat, a_bar + a_hat]), эллипсоидальные множества (Ben-Tal и Nemirovski, 1999) и бюджетные множества (Bertsimas и Sim, 2004). Параметр бюджета Гамма ограничивает, сколько параметров могут одновременно принимать свои наихудшие значения.
Формула
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}Замените каждое неопределенное ограничение его робастным аналогом: требуйте допустимости для каждой реализации в U. Это преобразует исходную задачу в полубесконечную программу — бесконечное число ограничений, по одному на элемент U.
Формула
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall iВыведите трактуемый детерминированный эквивалент. Для бюджетных множеств неопределенности робастный аналог переформулируется как стандартная ЛП или смешанная целочисленная ЛП схожего размера, решаемая обычными решателями. Ключевая переформулировка вводит вспомогательные переменные, которые линеаризуют внутреннюю максимизацию по множеству неопределенности.
Формула
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_iРешите переформулированную ЛП с помощью стандартного решателя (симплекс или метод внутренней точки). Оцените решение: проверьте нарушение ограничений в наихудшем случае по множеству неопределенности, сообщите цену робастности (увеличение целевой функции относительно номинальной ЛП) и выполните анализ чувствительности к бюджету робастности Гамма.
Частые ошибки
- Установка Гамма слишком высокой делает каждое ограничение одновременно наихудшим, что приводит к чрезмерно консервативному и дорогому решению.
- Неправильное указание множества неопределенности (например, игнорирование корреляционной структуры) может привести как к чрезмерной, так и к недостаточной защите.
- Путаница робастной ЛП со стохастической ЛП: RLP максимизирует производительность в наихудшем случае, а не ожидаемую производительность.
- Игнорирование отчета о цене робастности — всегда сравнивайте робастную целевую функцию с номинальной ЛП, чтобы количественно оценить стоимость консерватизма.
- Применение RLP к задачам с целочисленными переменными без перехода к робастной смешанной целочисленной формулировке, которая требует иных переформулировок.
Часто задаваемые вопросы
Чем робастное ЛП отличается от стохастического ЛП?
Стохастическое ЛП оптимизирует ожидаемую производительность при заданном распределении вероятностей по сценариям, требуя знаний о распределении. Робастное ЛП оптимизирует производительность в наихудшем случае по множеству неопределенности, требуя только границы — без распределения вероятностей. Робастное ЛП предпочтительнее, когда распределения ненадежны; стохастическое ЛП предпочтительнее, когда они хорошо оценены.
Что такое цена робастности?
Цена робастности — это увеличение значения целевой функции (стоимости) робастного решения по сравнению с номинальным решением ЛП. Берцимс и Сим (2004) доказали, что эта цена растет только как квадратный корень из числа неопределенных параметров для бюджетных множеств, делая робастность на удивление доступной.
Что такое бюджет робастности Гамма?
Гамма — это параметр в модели Берцимса-Сима, который контролирует, сколько неопределенных коэффициентов могут одновременно принимать свои наихудшие значения. Гамма = 0 соответствует номинальной ЛП; Гамма = n защищает от одновременного отклонения всех n параметров. Аналитики обычно выбирают Гамма на основе допустимых границ вероятности нарушения.
Требует ли робастное ЛП специального решателя?
Нет. Для множеств неопределенности типа «ящик» и «бюджет» робастный аналог сам является линейной программой, решаемой любым стандартным решателем ЛП (CPLEX, Gurobi, HiGHS и т. д.). Эллипсоидальные множества требуют решателя программ второго порядка, который также широко поддерживается.
Когда следует использовать робастное смешанное целочисленное программирование?
Если переменные решения должны быть целочисленными (например, бинарные решения «да/нет», размеры партий), робастный аналог будет содержать целочисленные переменные и станет робастной смешанной целочисленной программой. Подход с множеством неопределенности тот же, но переформулировка и требования к решателю соответственно меняются.
Похожие методы
Источники
Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
Открыть ссылку DOIСкопировано.Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.
Открыть ссылку DOIСкопировано.