Разложение Данцига – Вульфа - это алгоритм решения задач линейного программирования со специальной структурой. Первоначально он был разработан Джорджем Данцигом и Филипом Вулфом и первоначально опубликован в 1960 году. [1] Во многих текстах по линейному программированию есть разделы, посвященные обсуждению этого алгоритма разложения . [2] [3] [4] [5] [6] [7]
Декомпозиция Данцига – Вульфа основана на генерации отложенного столбца для улучшения управляемости крупномасштабных линейных программ. Для большинства линейных программ, решаемых с помощью переработанного симплекс-алгоритма , на каждом шаге большинство столбцов (переменных) не входят в базис. В такой схеме основная задача, содержащая, по крайней мере, текущие активные столбцы (базис), использует подзадачу или подзадачи для генерации столбцов для входа в базис, так что их включение улучшает целевую функцию.
Обязательная форма
Чтобы использовать разложение Данцига – Вульфа, матрица ограничений линейной программы должна иметь определенную форму. Набор ограничений должен быть идентифицирован как «связывающие», «связывающие» или «усложняющие» ограничения, при этом многие из переменных, содержащихся в ограничениях, имеют ненулевые коэффициенты. Остальные ограничения необходимо сгруппировать в независимые подматрицы, чтобы, если переменная имеет ненулевой коэффициент в одной подматрице, она не будет иметь ненулевой коэффициент в другой подматрице. Это описание визуализировано ниже:
D матрица представляет муфты ограничения и каждый F я представляет независимые подматрицы. Обратите внимание, что можно запустить алгоритм, когда есть только одна подматрица F.
Переформулировка проблемы
После определения требуемой формы исходная проблема переформулируется в основную программу и n подпрограмм. Эта переформулировка основана на том факте, что каждая точка непустого ограниченного выпуклого многогранника может быть представлена как выпуклая комбинация его крайних точек .
Каждый столбец в новой главной программе представляет решение одной из подзадач. Основная программа обеспечивает выполнение ограничений связи с учетом набора доступных в настоящее время решений подзадач. Затем главная программа запрашивает дополнительные решения из подзадачи, так что общая цель исходной линейной программы улучшается.
Алгоритм
Хотя существует несколько вариантов реализации, алгоритм разложения Данцига – Вульфа можно кратко описать следующим образом:
- Начиная с возможного решения сокращенной основной программы, сформулируйте новые целевые функции для каждой подзадачи так, чтобы подзадачи предлагали решения, улучшающие текущую цель основной программы.
- Подзадачи повторно решаются с учетом их новых целевых функций. Мастер-программе предлагается оптимальное значение для каждой подзадачи.
- Основная программа включает в себя один или все новые столбцы, сгенерированные решениями подзадач на основе соответствующей способности этих столбцов улучшить цель исходной задачи.
- Мастер-программа выполняет x итераций симплекс-алгоритма, где x - количество включенных столбцов.
- Если цель улучшена, перейдите к шагу 1. В противном случае продолжайте.
- Основная программа не может быть улучшена никакими новыми столбцами из подзадач, поэтому вернитесь.
Выполнение
Существуют примеры реализации разложения Данцига – Вульфа, доступные в языках математического моделирования AMPL [8] и GAMS [9] . Доступна общая параллельная реализация [10], в которой используется GNU Linear Programming Kit с открытым исходным кодом .
Алгоритм можно реализовать так, чтобы подзадачи решались параллельно, поскольку их решения полностью независимы. В этом случае для главной программы есть варианты того, как столбцы должны быть интегрированы в мастер. Мастер может дождаться завершения каждой подзадачи, а затем включить все столбцы, улучшающие цель, или может выбрать меньшее подмножество этих столбцов. Другой вариант состоит в том, что мастер может взять только первый доступный столбец, а затем остановить и перезапустить все подзадачи с новыми задачами, основанными на включении самого нового столбца.
Другой вариант дизайна для реализации включает столбцы, которые выходят из базиса на каждой итерации алгоритма. Эти столбцы могут быть сохранены, немедленно отброшены или отброшены с помощью какой-либо политики после будущих итераций (например, удалять все неосновные столбцы каждые 10 итераций).
Недавняя (2001 г.) вычислительная оценка Данцига-Вульфа в целом и Данцига-Вульфа и параллельных вычислений - это докторская диссертация Дж. Р. Теббота [11]
Смотрите также
Рекомендации
- ^ Джордж Б. Данциг; Филип Вулф (1960). «Принцип декомпозиции для линейных программ». Исследование операций . 8 : 101–111. DOI : 10.1287 / opre.8.1.101 .
- ^ Димитрис Берцимас; Джон Н. Цициклис (1997). Линейная оптимизация . Афина Сайентифик.
- ^ Джордж Б. Данциг; Мукунд Н. Тапа (1997). Линейное программирование 2: теория и расширения . Springer.
- ^ Вашек Хватал (1983). Линейное программирование . Макмиллан.
- ^ Марош, Иштван; Митра, Гаутам (1996). «Симплексные алгоритмы». В JE Бизли (ред.). Успехи в линейном и целочисленном программировании . Оксфордская наука. С. 1–46. Руководство по ремонту 1438309 .
- ^ Марош, Иштван (2003). Вычислительные методы симплекс-метода . Международная серия исследований операций и управления. 61 . Бостон, Массачусетс: Kluwer Academic Publishers. С. xx + 325. ISBN 1-4020-7332-1. MR 1960274 .
- ^ Ласдон, Леон С. (2002). Теория оптимизации для больших систем (перепечатка 1970 Macmillan ed.). Минеола, Нью-Йорк: Dover Publications, Inc., стр. Xiii + 523. Руководство по ремонту 1888251 .
- ^ «Репозиторий кода AMPL на примере Данцига – Вульфа» . Проверено 26 декабря 2008 года .
- ^ Калвелаген, Эрвин (май 2003 г.), Разложение Данцига-Вульфа с помощью GAMS (PDF) , получено 31 марта 2014 г..
- ^ «Реализация Данцига-Вульфа с открытым исходным кодом» . Проверено 15 октября 2010 года .
- ^ Теббот, Джеймс Ричард (2001). Вычислительное исследование разложения Данцига-Вульфа (PDF) (кандидатская диссертация). Букингемский университет, Великобритания.