Разложение Данцига – Вольфа

Декомпозиция Данцига – Вольфа — это алгоритм решения линейного программирования задач со специальной структурой. Первоначально он был разработан Джорджем Данцигом и Филипом Вулфом и впервые опубликован в 1960 году. ^{[ 1 ]} Во многих текстах по линейному программированию есть разделы, посвященные обсуждению этого алгоритма декомпозиции . ^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

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

Требуемая форма

Чтобы использовать разложение Данцига – Вольфа, матрица ограничений линейной программы должна иметь определенную форму. Набор ограничений должен быть идентифицирован как «связывающие», «связывающие» или «усложняющие» ограничения, при этом многие из переменных, содержащихся в ограничениях, имеют ненулевые коэффициенты. Остальные ограничения необходимо сгруппировать в независимые подматрицы таким образом, чтобы, если переменная имеет ненулевой коэффициент в одной подматрице, у нее не было ненулевого коэффициента в другой подматрице. Это описание визуализировано ниже:

Матрица D представляет ограничения связи, и каждый F _i представляет независимые подматрицы. Обратите внимание, что алгоритм можно запустить, когда имеется только одна F. подматрица

Переформулировка проблемы

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

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

Алгоритм

Хотя существует несколько вариантов реализации, алгоритм декомпозиции Данцига – Вольфа можно кратко описать следующим образом:

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

Выполнение

доступны примеры реализации разложения Данцига – Вольфа. с закрытым исходным кодом В AMPL ^{[ 8 ]} и ГАМС ^{[ 9 ]} программное обеспечение для математического моделирования. Существуют общие, параллельные и быстрые реализации, доступные в виде программного обеспечения с открытым исходным кодом , включая некоторые, предоставляемые JuMP и GNU Linear Programming Kit . ^{[ 10 ]}

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

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

Вычислительная оценка Данцига-Вульфа в целом, а также Данцига-Вульфа и параллельных вычислений (2001 г.) представляет собой докторскую диссертацию Дж. Р. Теббота. ^{[ 11 ]}

См. также

Ссылки

^ Джордж Б. Данциг; Филип Вулф (1960). «Принцип декомпозиции линейных программ». Исследование операций . 8 : 101–111. дои : 10.1287/opre.8.1.101 .
^ Димитрис Берцимас; Джон Н. Цициклис (1997). Линейная оптимизация . Афина Сайентифик.
^ Джордж Б. Данциг; Мукунд Н. Тапа (1997). Линейное программирование 2: Теория и расширения . Спрингер.
^ Васек Хватал (1983). Линейное программирование . Макмиллан.
^ Марош, Иштван; Митра, Гаутама (1996). «Симплексные алгоритмы». В Дж. Э. Бизли (ред.). Достижения в области линейного и целочисленного программирования . Оксфордская наука. стр. 1–46. МР 1438309 .
^ Марош, Иштван (2003). Вычислительные методы симплексного метода . Международная серия по исследованию операций и науке управления. Том. 61. Бостон, Массачусетс: Kluwer Academic Publishers. стр. хх+325. ISBN 1-4020-7332-1 . МР 1960274 .
^ Ласдон, Леон С. (2002). Теория оптимизации для больших систем (переиздание издания Macmillan 1970 года). Минеола, Нью-Йорк: Dover Publications, Inc., стр. xiii+523. МР 1888251 .
^ «Репозиторий кода AMPL с примером Данцига – Вольфа» . Проверено 26 декабря 2008 г.
^ Кальвелаген, Эрвин (май 2003 г.), Разложение Данцига-Вулфа с помощью GAMS (PDF) , получено 31 марта 2014 г. .
^ «Реализация Данцига-Вольфа с открытым исходным кодом» . Проверено 15 октября 2010 г.
^ Теббот, Джеймс Ричард (2001). Вычислительное исследование разложения Данцига-Вольфа (PDF) (кандидатская диссертация). Букингемский университет, Великобритания. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[1] Джордж Б. Данциг; Филип Вулф (1960). «Принцип декомпозиции линейных программ». Исследование операций . 8 : 101–111. дои : 10.1287/opre.8.1.101 .

[2] Димитрис Берцимас; Джон Н. Цициклис (1997). Линейная оптимизация . Афина Сайентифик.

[3] Джордж Б. Данциг; Мукунд Н. Тапа (1997). Линейное программирование 2: Теория и расширения . Спрингер.

[4] Васек Хватал (1983). Линейное программирование . Макмиллан.

[MarosMitra-5] Марош, Иштван; Митра, Гаутама (1996). «Симплексные алгоритмы». В Дж. Э. Бизли (ред.). Достижения в области линейного и целочисленного программирования . Оксфордская наука. стр. 1–46. МР 1438309 .

[6] Марош, Иштван (2003). Вычислительные методы симплексного метода . Международная серия по исследованию операций и науке управления. Том. 61. Бостон, Массачусетс: Kluwer Academic Publishers. стр. хх+325. ISBN 1-4020-7332-1 . МР 1960274 .

[7] Ласдон, Леон С. (2002). Теория оптимизации для больших систем (переиздание издания Macmillan 1970 года). Минеола, Нью-Йорк: Dover Publications, Inc., стр. xiii+523. МР 1888251 .

[8] «Репозиторий кода AMPL с примером Данцига – Вольфа» . Проверено 26 декабря 2008 г.

[9] Кальвелаген, Эрвин (май 2003 г.), Разложение Данцига-Вулфа с помощью GAMS (PDF) , получено 31 марта 2014 г. .

[10] «Реализация Данцига-Вольфа с открытым исходным кодом» . Проверено 15 октября 2010 г.

[11] Теббот, Джеймс Ричард (2001). Вычислительное исследование разложения Данцига-Вольфа (PDF) (кандидатская диссертация). Букингемский университет, Великобритания. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]