Схема метода ветвей и границ для общей задачи дискретного программирования.

Поиск с возвратами

Широко распространенным приемом, используемым для построения эффективных алгоритмов решения оптимизационных задач ДО является поиск с возвратами (backtracking)[1].

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

В общем случае полагаем, что решение задачи состоит из вектора конечной, но неопределенной длины, удовлетворяющего некоторым ограничениям. Каждое , где ‑ конечное линейно упорядоченное множество. Таким образом, при исчерпывающем поиске должны рассматриваться элементы множества для в качестве возможных решений. В качестве исходного частичного решения примем пустой вектор и на основании имеющихся ограничений выясним, какие элементы из являются кандидатами в . Обозначим это подмножество кандидатов через . В результате имеем частичное решение . В общем случае для расширения частичного решения от до кандидаты на роль выбираются из . Если частичное решение не представляет возможности для выбора элемента , то ; возвращаемся и выбираем новый элемент . Если новый элемент выбрать нельзя, возвращаемся еще дальше и выбираем новый элемент и т.д. Этот процесс удобно представлять в терминах прохождения дерева поиска в глубину. Процедура поиска с возвратами для нахождения всех решений представлена на рис. 6.1.

Рис. 6.1. Алгоритм поиска с возвратами.

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

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

Схема метода ветвей и границ для общей задачи дискретного программирования.

Метод ветвей и границ (branch and bound)[2] представляет собой систематическую схему неявного перебора конечного числа допустимых решений ЗЦЛП. Хотя теоретически размер дерева перебора является экспоненциальным от параметров задачи, в большинстве случаев метод исключает большое число допустимых решений. Основные шаги метода ветвей и границ

(1) Выбор/Исключение одной или более текущих задач из списка задач-кандидатов.

(2) Релаксация (ослабление) выбранной текущей задачи для получения верхней границы (оценки сверху) (для задачи максимизации) целевой функции текущей задачи.

(3) Зондирование, если это возможно, текущей задачи.

(4) Стратегия ветвления: Если текущая задача не зондируется, процедура ветвления строит подзадачи, дкоторые добавляются к списку задач-кандидатов.

Описанные шаги повторяются до тех пор, пока список задач-кандидатов не станет пустым. Метод ветвей и границ последовательно исследует задачи, которые добавляются в список задач-кандидатов или исключаются из этого списка. Опишем подробнее алгоритм ветвей и границ для решения задачи ЦЛП.

0. Инициализация. Вначале список задач-кандидатов содержит только исходную задачу ЦЛП следующего вида

.

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

Наилучшее решение, известное для задачи ,называется текущимрекордом.Соответствующее значение ЦФ обозначим Для данной задачи ДО (P) значение целевой функции рекорда находится с помощью какой-либо эвристики[3] (если же допустимое решение задачи (P) не может быть найдено, нужно положить ). Внести в список задач-кандидатов задачу (P): .

1. Оптимальность. Если и , то задача (P) недопустима, конец вычислений. Если и , то рекорд является оптимальным решением задачи (P), конец вычислений.

2. Выбор/Исключение. Используя одно из правил выбора задач-кандидатов, выбрать и удалить задачу (P) из списка . Выбранная задача называется в дальнейшем задача-кандидат (ЗК). Алгоритм кончает работу, если список задач-кандидатов пуст. В самом начале нет проблем с выбором, так как список задач-кандидатов содержит лишь одну задачу .Однако во время работы алгоритма список задач-кандидатов может содержать много задач и поэтому нужно использовать правило выбора текущей задачи. Соответствующие правила выбора, называющиеся также стратегиями ветвления, рассматриваются далее.

В принципе могут быть одновременно выбраны и исключены сразу несколько задач из списка задач-кандидатов. Однако большинство версий алгоритма ветвей и границ выбирает только одну задачу из списка задач-кандидатов, в дальнейшем так и будем считать.

Время счета для алгоритма ветвей и границ существенно зависит от порядка, в котором изучаются задачи из списка задач-кандидатов. Здесь могут быть использованы различные эвристические правила. На практике обычно используются для выбора задач две стратегии общего назначения:

(А) Выбрать задачу, добавленную последней в список задач-кандидатов. Это правило LIFO (last-in-first-out, т.е. первой выбирается задача, добавленная последней в в список) называется также поиском в глубину, т.к. добавление задачи-кандидата увеличивает глубину текущего дерева перебора.

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

3. Граница. Получить верхнюю границу для целевой функции задачи (P) с помощью релаксации (P_R) задачи (P) или с помощью применения специальных правил. Если (P_R) недопустима – вернуться к шагу 1. В противном случае, ‑ опимальное решение (P_R).

4. Зондирование. Если , вернуться к шагу 1. Иначе, если допустимо для задачи (P) и , положить , обновить рекорд (положив его равным ) и вернуться к шагу 1. И, наконец, если допустимо для задачи (P), но вернуться к шагу 1.

5. Разбиение. Используя правила разбиения или ветвления, разбить (P) на , положить и вернуться к шагу 1.

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

(6.1)

(6.2)

(6.3)

— целочисленный вектор. (6.4)

Для простоты изложения множество допустимых решений (6.2) ‑ (6.4) будем считать непустым и ограниченным.

Общая структура схемы Джеффриона и Марстена изображена на блок-схеме 6.1. Она состоит из следующих этапов.

Блок-схема 6.1. Схема Джеффриона и Марстена.

1. Начать список задач-кандидатов (ЗК) для ветвления 2, внеся в него задачу (6.1) ‑ (6.4) и положить рекорд 3 равным +∞.

2. Пуст ли список? Если пуст, то задача решена. Если непуст, переходим к шагу 3.

3. Выбрать ЗК для ветвления.

4. Релаксация (т. е. ослабление) условий целочисленности (переход от задачи частично-целочисленного программирования к соответствующей оценочной задаче линейного программирования).

5. Решение релаксированной задачи.

6. Пусто ли множество решений релаксированной задачи?

Если пусто, то переходим к шагу 2. Если непусто, переходим к шагу 7.

7. Оценка, полученная после решения ЗК, лучше рекорда? Если лучше, переходим к шагу 8. Если не лучше, переходим к шагу 2.

8. Получено ли оптимальное решение ЗК? Если получено, переходим к шагу 12. Если не получено, переходим к шагу 9.

9. Продолжать ли решение ЗК? Если да, то переходим к шагу 10. Если нет, переходим к шагу 11.

10. Модифицировать релаксацию (например, с учетом зафиксированных значений для некоторых из целочисленных переменных). Перейти к шагу 5.

11. Разветвить ЗК на задачи-потомки и занести их в список ЗК. Перейти к шагу 2.

12. Заменить рекорд и очистить список ЗК. Перейти к шагу 2.

Поясним общую схему.

1. Шаги 5, 6, 7, 8, 9, 10 ‑ это отдельные элементы процедуры оценивания.

2. Схема состоит из следующих основных элементов:

а) ветвление ‑ выбор ЗК и построение рекорда;

б) релаксация ‑ построение оценочных задач;

в) построение оценок.

3. Возможны различные способы ветвления, среди которых особо распространены:

α) покомпонентное ветвление;

β) ветвление с использованием дихотомии;

γ) сочетание α) и β);

4. Возможны различные стратегии ветвления (выбора ЗК), в частности:

а) ветвление по наименьшей нижней оценке;

б) одностороннее ветвление (ветвление по заранее намеченному пути);

в) ветвление по наименьшей нижней оценке среди множеств, достроенных на последнем шаге (или нескольких последних шагах);

г) ветвление в зависимости от разности между наименьшей нижней оценкой для множеств, построенных на последнем шаге, и множеств, построенных на предшествующих шагах;

д) эвристическое ветвление;

е) ветвление по вероятностным характеристикам;

ж) комбинация некоторых стратегий, перечисленных выше.

5. Оценивание:

а) оценки, получаемые через решение задач линейного программирования, можно существенно улучшить, если использовать штрафные добавки (об этом будет сказано ниже);

б) для определения оценок можно использовать также и эвристические процедуры.

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

(A) стратегии релаксации с эффективными решателями этих релаксаций.

(B) Эффективные структуры данных для поддержания списка задач-кандидатов.

(C) Разумнык стратегии выбора перспективных задач-кандидатов.

(D) Стратегии разбиения или ветвления, позволяющие эффективно сокращать дерево перебора.

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