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

Методът на клоните и границите (англ. Branch and Bound, съкр. B&B или BnB) е обща парадигма за изграждане на точни алгоритми за решаване на задачи от дискретна и комбинаторна оптимизация, по-специално NP-трудни задачи. Методът представлява стратегия за насочено изчерпване, при която цялото множество от допустими решения последователно се разделя на подмножества (разклоняване), а за всяко от тях се изчисляват оценки (граници) на стойността на целевата функция. Тези оценки позволяват да се отхвърлят (отрязват) онези подмножества, които очевидно не съдържат оптимални решения, което съществено намалява пространството за търсене.

Методът е предложен за първи път от А. Ленд и А. Дойг през 1960 година за решаване на задачи от целочислено програмиране. Оттогава той се превърна в един от най-фундаменталните подходи в изследването на операциите и компютърните науки. Ключова особеност на метода е неговата гъвкавост: той не е конкретен алгоритъм, а стратегическа схема от високо ниво (framework), адаптивна към структурата на решаваната задача.

Ключови компоненти на метода

В основата на метода лежат три фундаментални операции, приложими към подмножества от пространството на решенията, организирани като дърво за търсене.

• Разклоняване (англ. Branching) — това е процес на рекурсивно разделяне на текущото множество от допустими решения $S_i$ на няколко по-малки, като правило непресичащи се подмножества $S_{i1},S_{i2},\dots ,S_{ik}$. Всяко такова подмножество съответства на нова подзадача и се представя като дъщерен възел в дървото за търсене. Например, в задачите на целочислено програмиране разклоняването често се извършва по променлива, която има дробна стойност в решението на LP-релаксацията.

• Оценка на границите (англ. Bounding) — за всеки възел от дървото за търсене (т.е. за всяка подзадача) се изчислява оценка на стойността на целевата функция. За задача за минимизиране това е долна граница (lower bound), която е гарантирана оценка отдолу за всяко решение в дадено подмножество. Най-често тази оценка се получава чрез решаване на релаксация на изходната подзадача — опростена версия, в която някои сложни ограничения (например за целочисленост) временно се игнорират. Най-разпространена е LP-релаксацията.

• Отрязване (англ. Pruning) — това е процес на изключване от разглеждане на възли (и съответстващите им цели поддървета), които очевидно не могат да съдържат оптималното решение. Един възел се отрязва в един от следните случаи:

1. Отрязване по граница: Долната граница за дадения възел се оказва не по-добра (т.е. по-голяма или равна при задача за минимизиране) от стойността на най-доброто намерено дотук допустимо решение, наречено рекорд (incumbent).
2. Отрязване по допустимост: Решението на релаксацията за даден възел е допустимо за изходната задача (например всички променливи са целочислени). Това решение се сравнява с текущия рекорд и ако е по-добро, рекордът се обновява. По-нататъшно разклоняване от този възел не е необходимо.
3. Отрязване по неразрешимост: Подзадачата, съответстваща на възела, няма допустими решения.

Общ алгоритъм

Обобщеният алгоритъм на метода на клоните и границите за задача за минимизиране може да бъде описан със следните стъпки:

1. Инициализация: Намери начално допустимо решение (например с помощта на евристика) и задай стойността му като начална горна граница (рекорд) $U$. Създай опашка от активни възли $Q$, съдържаща коренния възел (изходната задача).
2. Основен цикъл: Докато опашката $Q$ не е празна:
   • Избери възел от $Q$ в съответствие със стратегията за търсене (например търсене в дълбочина или по най-добра оценка).
   • Реши релаксацията за този възел, получавайки долна граница $L$.
   • Отрежи възела, ако $L\ge U$.
   • Ако решението на релаксацията е допустимо за изходната задача, обнови рекорда: $U\leftarrow L$.
   • Ако възелът не е отрязан и решението не е допустимо, извърши разклоняване, разделяйки го на дъщерни възли, и ги добави в опашката $Q$.
3. Завършване: Когато опашката $Q$ стане празна, алгоритъмът завършва. Намереното решение, съответстващо на рекорда $U$, е глобално оптимално.

Ключови свойства и теореми

• Коректност и сходимост: Алгоритъмът гарантирано намира глобално оптимално решение за краен брой стъпки, ако множеството от допустими решения е крайно, а процедурата за разклоняване е сходяща (т.е. при рекурсивно разбиване подмножествата се „свиват" към точки).
• Стратегия за търсене: Ефективността на алгоритъма силно зависи от стратегията за избор на следващия възел за разклоняване (например търсене в дълбочина, търсене в ширина, търсене по най-добра оценка) и от избора на променлива за разклоняване. Съвременните решатели (solvers) често използват хибридни стратегии.

Примери

• Задача за целочислено програмиране: Класическо приложение на метода. Като релаксация се използва линейно програмиране. Разклоняването се извършва по дробна променлива $x_j$, създавайки две подзадачи с допълнителни ограничения $x_j\le \lfloor x_j^{*}\rfloor$ и $x_j\ge \lceil x_j^{*}\rceil$.
• Задача на търговския пътник: Пространството на решенията са всички възможни хамилтонови цикли в графа. Разклоняването може да се извършва по ребра (включване/изключване на ребро от маршрута). Като долни граници могат да се използват решения на по-прости задачи, като задачата за назначаване или изграждане на минимално покриващо дърво.

Свързани понятия и приложения

• Метод на клоните и отрязванията (Branch-and-Cut): Хибриден метод, обединяващ B&B с метода на отсичащите равнини. На всеки възел от дървото за търсене, освен решаване на релаксацията, се генерират допълнителни неравенства (отрязвания), които усилват долната граница, което води до по-ефективно отрязване на клони.
• Търсене с връщане (Backtracking): Методът на клоните и границите може да се разглежда като обобщение на този алгоритъм за задачи за оптимизация.
• Алфа-бета отрязване: Концептуална аналогия, използвана в игрови дървета за отрязване на заведомо губещи клони.

Вижте също

• Целочислено програмиране
• Комбинаторна оптимизация
• Задача на търговския пътник
• NP-трудна задача
• Симплекс метод

Бележки

</references>