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

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

Автор метода
Ben-Tal & Nemirovski; Bertsimas & Sim
Год
1998–2004
Тип
Deterministic robust reformulation of MIP under uncertainty
Семейство
Simulation / optimization

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

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

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

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

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

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

Классические смешанно-целочисленные программы предполагают, что все данные известны точно, но на практике затраты, спрос и время обработки колеблются. РСЦП ставит вопрос: какие целочисленные и непрерывные решения являются наилучшими, если неопределенные параметры принимают свои наихудшие правдоподобные значения в пределах заданного диапазона? Встраивая неопределенность непосредственно в модель оптимизации, РСЦП создает планы, которые застрахованы от вариаций данных без обращения к множественным вероятностным сценариям. Подход Берцимса-Сима с бюджетом неопределенности позволяет практикам выбирать между полной робастностью и эффективностью в среднем случае, делая компромисс между защитой и стоимостью явным.

История

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

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

Использовать РСЦП, когда решения включают целочисленные или бинарные выборы (размещение объектов, определение размера партии, проектирование сети, планирование) и некоторые входные параметры неопределенны, но распределения вероятностей недоступны или ненадежны. Это подходит, когда нарушения ограничений недопустимы (жесткие требования допустимости) и консервативная, но детерминированная гарантия предпочтительнее оптимизации по ожидаемому значению. НЕ использовать, когда распределения неопределенности хорошо охарактеризованы и допустимы аппроксимация среднего по выборке или стохастическое смешанно-целочисленное программирование; когда все переменные решения непрерывны (использовать вместо этого робастное линейное программирование); или когда множество неопределенности настолько велико, что модель становится нерешаемой без стратегий декомпозиции.

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

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

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

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

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

Применение

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

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

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

1

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

2

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

3

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

4

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

5

Оценить робастное решение путем: (a) вычисления его значения целевой функции при номинальных и наихудших параметрах, (b) сравнения с решением стохастического программирования с использованием сценариев Монте-Карло и (c) сообщения о цене робастности — дополнительной стоимости, уплаченной за защиту от неопределенности.

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

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

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

Чем РСЦП отличается от стохастического смешанно-целочисленного программирования?

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

Что такое 'цена робастности' и насколько она велика обычно?

Цена робастности — это процентное увеличение значения целевой функции по сравнению с номинальным (без неопределенности) оптимумом. Берцимс и Сим показывают, что она растет примерно линейно с Gamma, но остается скромной для типичных значений бюджета, часто 5–15% в практических приложениях.

Может ли РСЦП обрабатывать неопределенные правые части ограничений так же, как и неопределенные коэффициенты затрат?

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

Решаемо ли РСЦП с помощью стандартных решателей смешанно-целочисленного программирования?

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

Когда следует предпочесть коробочное множество неопределенности множеству с бюджетом неопределенности?

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

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

Источники

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

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

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