Введение

Масштабные задачи целочисленного программирования (IP) и смешанных целочисленных программ (MIP) возникают естественным образом во многих отраслях, включая логистику, производство, управление энергией, телекоммуникации и финансы. В этих задачах переменные решения должны принимать целые значения — например, количество грузовиков для отправки, расположение складов или состояние генераторов энергии. В то время как целочисленное программирование обеспечивает мощную модельную структуру, решение этих проблем напрямую часто становится вычислительно неосуществимым, поскольку число переменных и ограничений растет. Стандартные алгоритмы разложения ветвей или ветвей и вырезок могут задерживаться или требовать чрезмерной памяти и времени. , впервые введенный Жаком Ф. Бендером в 1962 году, является классической техникой, которая решает такую сложность, разделяя первоначальную проблему на более мелкую основную проблему , содержащую целочисленные переменные и одну или несколько непрерывных подзадачи.

Что такое декомпозиция Бендеров?

Разложение Бендеров — это метод генерации строк, предназначенный для решения задач оптимизации со структурой, которая может быть разделена на две стадии: первая стадия включает в себя «компликацию» переменных (часто целых или двоичных), а вторая стадия включает в себя переменные, которые, когда переменные первой стадии фиксированы, дают непрерывную линейную или выпуклую подзадачу. Основная идея состоит в том, чтобы проецировать проблему на пространство усложняющих переменных, заменяя внутреннюю подзадачу набором линейных ограничений — известных как , разрезы Бендеров — которые генерируются постепенно. Этот подход особенно эффективен, когда подзадача легче решить, чем оригинальная монолитная формулировка. Для всеобъемлющего математического введения см. статью Википедия о разложении Бендеров .

Исторически сложилось так, что разложение Бендеров было разработано для смешанного целочисленного линейного программирования (MILP). Со временем оно было распространено на нелинейные, стохастические и надежные задачи оптимизации. В стохастическом программировании, например, основная задача захватывает решения первой стадии, в то время как каждый сценарий формирует подзадачу; Бендеры режет затем связывают сценарии. Метод остается основным продуктом в исследованиях операций и реализуется в коммерческих решателях, таких как CPLEX и Gurobi, а также инструменты с открытым исходным кодом, такие как Pyomo и GAMS.

Основные этапы разложения бендеров

Применение разложения Бендеров к задаче целочисленного программирования следует четко определенной итеративной процедуре.Предполагается, что исходная задача имеет структуру:

  • Главная задача (MP): Содержит целые переменные x ∈ Zn и вспомогательную переменную θ, которая представляет ожидаемую стоимость или значение из подзадачи. Первоначально MP может не иметь сокращений Бендеров или только нескольких ограничений осуществимости.
  • Проблема (SP): Для фиксированного назначения xk из МР, SP решает непрерывную линейную программу (или выпуклую программу) по оставшимся непрерывным переменным y. SP даёт оптимальное объективное значение Qk и двойные множители, которые определяют разрез.

Итеративный алгоритм протекает следующим образом:

  1. Начните: Установите счетчик итерации k = 1. Выберите начальную возможную x1 (часто от решения МР без сокращений, если это возможно).
  2. Решите подзадачу: Исправьте x = xk и решите SP до оптимальности., если SP неосуществим, сгенерируйте ток осуществимость разрезаxkk и добавьте его в MP. Если SP осуществим и ограничен, получите двойное решениеоптимальность разреза ≥αβTx
  3. Добавить разрез к основной задаче: Добавить вновь сгенерированный разрез к MP.
  4. Решите основную задачу: Решите MP (который теперь включает все разрезы, сгенерированные до сих пор) для получения нового кандидата xk+1 и обновленной нижней границы (оптимальная цель MP). Верхняя граница может быть получена из значения решения SP.
  5. Проверить конвергенцию: Если верхняя и нижняя границы достаточно близки (в пределах допуска), остановитесь. В противном случае, прирасти k и вернитесь к шагу 2.

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

Математическая формула и простой пример

Чтобы заложить основу дискуссии, рассмотрим классическую проблему местоположения объекта. Решения первой стадии двоичные: открытые или не открытые объекты. Решения второй стадии назначают клиентам открытые объекты для минимизации транспортных расходов. Монолитный MILP может быть разложен на главную проблему, которая решает, какие объекты открывать, и подзадачу, которая вычисляет оптимальное назначение для этого фиксированного набора. Подзадача представляет собой непрерывную линейную программу транспортировки. Двойная из этой подзадачи обеспечивает коэффициенты для сокращений Бендеров, которые постепенно формируют приблизительную стоимость главной проблемы. Для подробного руководства с небольшим численным примером руководство по разложению Бендеров NEOS предлагает отличный проход.

В более общем плане, предположим, что первоначальная проблема заключается в следующем:

min cTx + f(y)
s.t. A x + B y ≥ b
x ∈ {0,1}n, y ≥ 0

После фиксации x подзадача над y является линейной программой (LP). Её двойная выдает луч крайних точек. Разрез оптимальности выводится из двойной крайней точки, в то время как экстремальные лучи производят разрезы осуществимости. Основной проблемой становится:

min cTx + θ
s.t. (выполняемые сокращения), (оптимальные сокращения)
x ∈ {0,1}n, θ free

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

Преимущества разложения бендеров

Разложение бендеров приносит несколько конкретных преимуществ практикующим:

  • Сниженная вычислительная сложность: Выделяя целочисленные переменные, комбинаторный взрыв ограничивается меньшей главной задачей. Непрерывная подзадача, которая может включать в себя десятки тысяч переменных, быстро решается с помощью линейного программирования.
  • Масштабируемость: Проблемы с миллионами непрерывных переменных и всего несколькими сотнями целых переменных становятся тягостными. Эта структура распространена в сетевом дизайне, оптимизации цепочки поставок и расширении емкости.
  • Гибкость: Метод может обрабатывать стохастические расширения (подзадачи на основе сценариев) и надежную оптимизацию (выпуклые или даже невыпуклые подзадачи, если применяется двойственность). Он также может быть объединен с ускоренными Бендерами с использованием вырезанных пулов и предварительной обработки.
  • Возможности параллелизации: Подзадачи на разных итерациях (или в разных сценариях) могут быть решены независимо, что позволяет параллельным вычислениям сократить время настенных часов.
  • Теплое начало: Если известно хорошее исходное целое число, основная задача может быть засеяна небольшим набором перспективных разрезов, ускоряющих конвергенцию.

Эти преимущества делают разложение Бендеров предпочтительным методом во многих промышленных условиях, где время решения имеет решающее значение.

Проблемы и стратегии смягчения

Несмотря на свою силу, разложение Бендеров не является панацеей. Практикующие должны знать о нескольких распространенных подводных камнях и принимать стратегии для их смягчения:

Медленная конвергенция

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

Бедный мастер проблемы инициализации

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

Большая проблема мастера IP

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

Численность стабильности

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

Подпроблема неосуществимости

Когда подзадача неосуществима для данного xk, то необходимо создать выполнимость.] Это вырезание получено из двойного экстремального луча невыполнимой LP. В некоторых формулировках (например, без ограничений «большого М») подзадача может быть неосуществима для многих целых комбинаций, что приводит к многим выполнимым вырезам до достижения выполнимой области. Эластичное программирование или добавление переменных слакса с затратами на штраф может облегчить эту проблему.

Приложения в промышленности

Декомпозиция Бендеров успешно применяется в различных реальных условиях:

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

Каждое приложение использует основное преимущество: скрывая непрерывную структуру внутри LP, комбинаторная сложность локализуется в основной целочисленной программе.

Сравнение с другими методами разложения

Декомпозиция Бендеров часто сравнивается с другими подходами декомпозиции:

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

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

Рассмотрение осуществления

Для эффективного осуществления разложения Бендеров требуется внимание к нескольким практическим деталям:

  • Выбор растворителя: Основная задача (целое число) может быть решена с помощью решателя MILP, такого как Gurobi, CPLEX или SCIP. Подзадача (LP) выигрывает от быстрого решателя LP; многие современные решатели MILP также позволяют эффективно решать LP без загрузки полной модели каждый раз.
  • Стратегия генерации сокращений: Вместо добавления всего одного разреза на итерацию часто полезно добавлять несколько разрезов (например, по одному из каждой крайней точки двойного). Также для ускорения конвергенции следует реализовать Парето-оптимальные разрезы Библиотеки, такие как Pyomo и JuMP, предоставляют обертки для разложения Бендеров, которые обрабатывают эти детали.
  • Формулировка основной задачи: Вспомогательная переменная θ должна иметь явную нижнюю границу (например, значение релаксации LP), чтобы избежать неограниченных мастер-итераций. Добавление решения с теплым стартом может резко сократить количество итераций.
  • Критерии остановки: Используйте относительный или абсолютный разрыв (например, 0,1%). Но в некоторых приложениях приемлемо почти оптимальное решение, поэтому толерантность может быть ослаблена.
  • Отладка: Обычная ошибка генерирует неправильные сокращения из-за двойного вырождения или неправильной интерпретации. Всегда проверяйте, что разрез действителен, проверяя его на исходную проблему. Подсчет итерации регистрации и связанные улучшения помогают диагностировать медленную конвергенцию.

Для всеобъемлющего руководства по реализации с примерами кода в Python, пример Gurobi Benders Example является ценным ресурсом.Кроме того, документация IBM ILOG CPLEX по алгоритму Бендеров обеспечивает понимание автоматического и ручного разложения.

Заключение

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