Przejdź do treści
Wróć do wyników wyszukiwania

Metoda podziału i ograniczeń (branch and bound)

Autor metody
Ailsa Land & Alison Doig
Rok
1960
Typ
Exact combinatorial optimization algorithm
Rodzina
Mathematical programming

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Metoda podziału i ograniczeń (ang. branch and bound) to systematyczny, dokładny algorytm dla kombinatorycznych i całkowitoliczbowych problemów optymalizacyjnych, wprowadzony przez Ailsę Land i Alison Doig w 1960 roku.

Organizuje on przestrzeń poszukiwań jako drzewo podproblemów, wykorzystuje górne ograniczenia wyprowadzone z relaksacji do przycinania gałęzi, które nie mogą poprawić najlepszego znanego rozwiązania, i gwarantuje znalezienie globalnie optymalnego rozwiązania całkowitoliczbowego. Jest to podstawa nowoczesnych solverów programowania mieszanego całkowitoliczbowego, stosowanych w badaniach operacyjnych, logistyce, harmonogramowaniu i projektowaniu inżynierskim.

Intuicja stojąca za metodą

Wyobraźmy sobie poszukiwanie przedmiotu o najwyższej wartości ukrytego w ogromnym labiryncie pokoi. Zamiast sprawdzać każdy pokój, szacujemy maksymalną możliwą wartość, którą można osiągnąć z każdego korytarza, zanim się do niego wejdzie. Jeśli ten pułap jest niższy niż najlepszy przedmiot, który już posiadamy, pomijamy cały korytarz bez zaglądania do środka. Metoda podziału i ograniczeń działa w ten sam sposób: dzieli problem na mniejsze części, oblicza optymistyczne górne ograniczenia dla każdej części i natychmiast odrzuca każdą część, która z definicji nie może przewyższyć obecnego najlepszego rozwiązania.

Historia

Land i Doig opublikowali fundamentalny artykuł o metodzie podziału i ograniczeń w „Econometrica” w 1960 roku, przedstawiając ją jako automatyczną metodę programowania dyskretnego. Little i in. (1963) zastosowali tę technikę do problemu komiwojażera, umacniając jej rolę w optymalizacji kombinatorycznej. Dakin (1965) wprowadził rozgałęzianie oparte na relaksacji LP, formę najczęściej stosowaną dzisiaj. Kolejne dekady przyniosły integrację płaszczyzn tnących (branch-and-cut) i generacji kolumn (branch-and-price), czyniąc metodę podziału i ograniczeń podstawą wszystkich głównych komercyjnych solverów programowania całkowitoliczbowego.

Kiedy stosować

Używaj metody podziału i ograniczeń, gdy musisz znaleźć udowodnione optymalne rozwiązanie programu liniowego mieszanego lub czysto całkowitoliczbowego i nie możesz zaakceptować przybliżonej odpowiedzi. Zakłada ona, że problem można sformułować za pomocą relaksacji liniowych (lub wypukłych), które dostarczają użytecznych ograniczeń. Jest mniej odpowiednia dla bardzo dużych instancji, gdzie drzewo enumeracji eksploduje, dla nieliniowych programów całkowitoliczbowych bez ścisłych relaksacji, lub dla zastosowań w czasie rzeczywistym, gdzie czas obliczeń jest ściśle ograniczony. W takich przypadkach preferowane mogą być heurystyki lub metaheurystyki.

Ograniczenia i uwagi

  • Złożoność w najgorszym przypadku jest wykładnicza; na źle ustrukturyzowanych instancjach drzewo może rosnąć do ogromnych rozmiarów.
  • Efektywność metody jest silnie zależna od na wybór zmiennej rozgałęzienia i strategii wyboru węzła.
  • Wymaga relaksacji o niskim koszcie obliczeniowym (tractable), która dostarcza znaczących górnych ograniczeń; słabe ograniczenia prowadzą do minimalnego przycinania.
  • Wymagania pamięciowe mogą być znaczne, gdy wiele otwartych węzłów musi być przechowywanych jednocześnie.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Gwarantuje globalną optymalność dla programów całkowitoliczbowych i kombinatorycznych.
  • Dramatycznie redukuje przeszukiwanie dzięki przycinaniu opartemu na ograniczeniach — często badana jest tylko niewielka część pełnego drzewa enumeracji.
  • Elastyczna: może zawierać płaszczyzny tnące (branch-and-cut) lub ograniczenia heurystyczne (branch-and-price) dla dalszej efektywności.
  • Szeroko zaimplementowana w dojrzałych komercyjnych solverach (CPLEX, Gurobi) i narzędziach open-source (GLPK, CBC).

Zastosowania

  • Harmonogramowanie załóg lotniczych i przydział flot w badaniach operacyjnych.
  • Projektowanie sieci łańcucha dostaw i problemy lokalizacji obiektów.
  • Układ obwodów VLSI i alokacja rejestrów w inżynierii komputerowej.
  • Predykcja struktury białek i składanie genomów w biologii obliczeniowej.
  • Optymalizacja portfela finansowego z ograniczeniami kardynalności.

Jak to działa

Jak to działa

1

Algorytm rozpoczyna się od rozwiązania zrelaksowanej wersji problemu — zazwyczaj relaksacji liniowej (LP) — która ignoruje ograniczenia całkowitoliczbowości. Ta relaksacja daje górne ograniczenie na prawdziwą optymalną wartość, ponieważ każde dopuszczalne rozwiązanie całkowitoliczbowe jest również dopuszczalne w relaksacji. Jeśli zrelaksowane rozwiązanie przypadkiem ma wartość całkowitą, problem jest rozwiązywany natychmiast.

Wzór
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

Gdy zrelaksowane rozwiązanie zawiera zmienną ułamkową, algorytm dzieli obszar dopuszczalny, dodając ograniczenia komplementarne, które wymuszają, aby zmienna przyjmowała wartość albo swojego sufitu, albo podłogi. Każdy podział tworzy nowy węzeł potomny w drzewie poszukiwań, skutecznie dzieląc jeden podproblem na dwa mniejsze podproblemy o węższych dziedzinach.

Wzór
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Każdy aktywny węzeł otrzymuje własne ograniczenie relaksacji LP. Węzeł, którego ograniczenie nie przekracza najlepszego znalezionego dotychczas rozwiązania całkowitoliczbowego — zwanego inkumbentem — nie może zawierać lepszego rozwiązania, więc jest przycinany. Ścisłe ograniczenia są kluczowe: im ściślejsze ograniczenie, tym mniej węzłów trzeba zbadać.

Wzór
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Węzeł jest zamykany (fathomed — trwale wyłączany z dalszego przeszukiwania) w trzech warunkach: jego relaksacja jest niedopuszczalna, jego ograniczenie nie jest lepsze niż inkumbent, lub jego zrelaksowane rozwiązanie jest już dopuszczalne całkowitoliczbowo. W tym ostatnim przypadku inkumbent jest aktualizowany, jeśli nowe rozwiązanie go poprawia. Algorytm kończy działanie, gdy wszystkie węzły są zamknięte, a inkumbent jest globalnym optimum.

Wzór
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Częste pułapki

  • Niewłaściwy wybór zmiennej rozgałęzienia (np. zawsze rozgałęzianie na pierwszej zmiennej ułamkowej) często prowadzi do głębokich, niezbalansowanych drzew i powolnej zbieżności.
  • Ignorowanie prawidłowych nierówności (płaszczyzn tnących) oznacza utratę możliwości znaczącego zaostrzenia ograniczeń relaksacji.
  • Przedwczesne zakończenie z luką suboptymalności, która nie jest zgłaszana jako taka, może wprowadzić praktyków w błąd, traktując rozwiązanie bliskie optymalnemu jako dokładne.
  • Zastosowanie metody podziału i ograniczeń do nieliniowych lub niewypukłych relaksacji bez specjalistycznej konweksyfikacji może prowadzić do nieprawidłowych ograniczeń i błędnych wyników.

Najczęściej zadawane pytania

Czym metoda podziału i ograniczeń różni się od enumeracji wyczerpującej?

Enumeracja wyczerpująca ocenia każde dopuszczalne rozwiązanie całkowitoliczbowe jawnie, co jest obliczeniowo niewykonalne dla dużych problemów. Metoda podziału i ograniczeń unika tego, obliczając górne ograniczenia oparte na relaksacji w każdym węźle drzewa poszukiwań i przycinając całe poddrzewa, gdy ograniczenie nie może przekroczyć już znalezionego najlepszego rozwiązania. W praktyce badana jest tylko niewielka część drzewa.

Jaka jest rola relaksacji LP w metodzie podziału i ograniczeń?

Relaksacja LP pomija ograniczenia całkowitoliczbowości, dzięki czemu problem można rozwiązać w czasie wielomianowym za pomocą metody simplex lub metod punktu wewnętrznego. Jej wartość optymalna służy jako górne ograniczenie dla odpowiadającego podproblemu całkowitoliczbowego. Gdy to ograniczenie jest ścisłe — bliskie prawdziwemu optimum całkowitoliczbowemu — trzeba zbadać mniej gałęzi. Ściślejsze relaksacje, często osiągane przez dodanie prawidłowych nierówności, dramatycznie przyspieszają cały algorytm.

Kiedy powinienem używać metody podziału i ograniczeń zamiast metaheurystyki, takiej jak algorytmy genetyczne?

Wybierz metodę podziału i ograniczeń, gdy potrzebujesz certyfikatu optymalności i możesz pozwolić sobie na czas obliczeń. Jest idealna dla problemów średniej wielkości z dobrze ustrukturyzowanymi relaksacjami LP. Metaheurystyki są preferowane, gdy problem jest niezwykle duży, brakuje mu użytecznej relaksacji lub musi być rozwiązany w ścisłym budżecie czasowym, gdzie akceptowalne jest rozwiązanie bliskie optymalnemu. Wielu praktyków łączy oba podejścia: używa metody podziału i ograniczeń z tolerancją luki przy wczesnym zakończeniu.

Pokrewne metody

Źródła

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    Otwórz odnośnik DOI
    Skopiowano.