Метод ветвей и границ

МЕТОД  ВЕТВЕЙ И ГРАНИЦ

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

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

 Рассмотрим общую схему метода.

Общая схема метода 

Рассмотрим   задачу  дискретной оптимизации  вида 

 

где  Ω - некоторое конечное множество   из  Rⁿ .  

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

1) построение  дерева  допустимых вариантов; 

2) составление  оценочных  задач; 

3) определение  правила   обхода  дерева  вариантов; 

4)  отбрасывание  “неперспективных”   множеств   вариантов; 

5) проверка  критерия  останова.

Рассмотрим   подробно   каждый из  указанных модулей .

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

на  конечное число   непересекающихся  подмножеств . Факт разбиения множества называется  ветвлением и производится  на  очередном шаге метода  в соответствии  со   сформулированным заранее правилом. Это   правило   связано   со спецификой конкретного допустимого множества исследуемой задачи. Однако   если  исходная  задача  среди прочих   имеет ограничения вида x_j∈={1,0} , j=1..n (т.е.  является   задачей   с булевыми переменными),  то   можно воспользоваться универсальным  правилом  ветвления:  Ω = Ω₁ ∪ Ω₂ ,   где Ω₁={x∈Ω: x_i=1} ;            Ω₂={x∈Ω: x_i=0}; i -   зафиксированный   номер   координаты   1≤ i ≤ n. Порядок фиксирования  координат  оговаривается  в  правиле  ветвления. Отметим , что   правило   разбиения множества на  подмножества  в конкретной задаче  может быть  не  единственным. 

2)  Оценкой   функции   ϕ(x) задачи (1) на  множестве  Ω  называется  такое число  ξ= ξ(Ω), что   ϕ(x)≥ ξ, ∀x∈Ω. Для  получения  оценок составляется  оценочная  задача, решение  которой используется  для  вычисления  соответствующей  оценки. К  оценочным задачам   предъявляются  следующие  требования: с одной стороны , их   решение не  должно   занимать  много времени. Но вместе   с тем   оценки, полученные с их   помощью   должны   быть  как   можно   точнее (т.е. разность   не  должна  быть  слишком большой). Такие требования  объясняются тем , что   именно   оценки используются  при отбрасывании  неперспективных множеств  (следовательно , при сокращении  перебора). При составлении оценочных задач можно   воспользоваться универсальным правилом: отбросить в   исходной задаче  наиболее  “тяжелые” (трудновыполнимые)  ограничения (например,  требование  целочисленности ).  Получаемые оценки  должны   обладать  монотонностью   в том смысле,  что   оценки  подмножеств   не  должны   быть  меньше оценки  разветвленного множества (то  есть  если  Ω=Υ_kΩ_k, то   должно   быть  выполнено   условие ξ (Ω )≤ ξ (Ω_k) ∀k .

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

3)  Правило   обхода  дерева  вариантов в процессе  работы   алгоритма называют  стратегией  обхода  дерева.  Существует  множество   различных стратегий .

Наиболее  распространенными  являются  три  из  них.

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

b)  Односторонний обход   дерева  вариантов. Для  последующего  разбиения  выбирается  одно   из  подмножеств , полученных на  предыдущем   шаге (например, подмножество , в котором x_l =1, 1≤ l ≤ n). Если  соответствующая ветвь дерева  оказывается пройденной до   конца (или отброшена как неперспективная), то   происходит  возвращение к ближайшему из  предыдущих   шагов, где сохранилась альтернатива. 

c)  Смешанная  стратегия.  В  этом случае  для  продвижения   “вниз  по дереву”  используется  односторонний   обход дерева  вариантов,  а  при  “подъеме  вверх”  ищется  множество   с  минимальной оценкой. 

Отметим, что при односторонней схеме ветвления нет необходимости запоминать все элементы разбиения, достаточно иметь информацию о первом элементе разбиения и объединении остальных элементов. 

 

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

 

 

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

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

 

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

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

ходу  решения  задачи  рекорд  обновляется. Справедливо   следующее утверждение. Если   оценка  некоторого   подмножества больше имеющегося  рекорда , то   среди   точек данного   подмножества нет решения задачи. Это утверждение позволяет сформулировать  основное правило   сокращения  перебора: если  оценка  множества  больше рекордного значения, то   такое множество   вариантов выбрасывается  из  дальнейшего рассмотрения.  Отметим , что   множество   может  не  подвергаться  последующему ветвлению   и  по другим   причинам : если  при  решении  оценочной задачи  на  данном множестве была  получена  точка, являющаяся  допустимой в исходной задаче, или  если допустимое множество   оценочной задачи  пусто .  Если значение целевой функции на очередном решении меньше рекордного, то происходит смена рекорда. Будем говорить, что подмножество решений просмотрено, если установлено, что оно не содержит решения лучше рекорда.

 

5)  Работа   метода  останавливается  в  соответствии  с  критерием оптимальности. 

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

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

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

 

 

 

 

         Алгоритмическая схема метода

 

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

 

 

 

 

 

 

 

Список литературы:

1)

2) Сигал И.Х., Иванова А.П. Введение в прикладное дискретдискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 с.