Metoda podziału i ograniczeń

From Systems analysis Wiki
Jump to navigation Jump to search

Metoda podziału i ograniczeń (ang. Branch and Bound, skrót B&B lub BnB) — to ogólna paradygmat budowania dokładnych algorytmów do rozwiązywania zadań dyskretnej i kombinatorycznej optymalizacji, w szczególności zadań NP-trudnych[1]. Metoda stanowi strategię ukierunkowanego przeglądu, w której cały zbiór dopuszczalnych rozwiązań jest kolejno dzielony na podzbiory (rozgałęzianie), a dla każdego z nich obliczane są oceny (ograniczenia) wartości funkcji celu. Oceny te pozwalają odrzucać (odcinać) te podzbiory, które z góry nie zawierają optymalnych rozwiązań, co istotnie redukuje przestrzeń poszukiwań[2].

Metoda została po raz pierwszy zaproponowana przez A. Land i A. Doig w 1960 roku do rozwiązywania zadań programowania całkowitoliczbowego[3]. Od tego czasu stała się jednym z najbardziej fundamentalnych podejść w badaniach operacyjnych i informatyce. Kluczową cechą metody jest jej elastyczność: nie jest ona konkretnym algorytmem, lecz wysokopoziomowym schematem strategicznym (frameworkiem), adaptacyjnym do struktury rozwiązywanego problemu.

Kluczowe komponenty metody

U podstaw metody leżą trzy fundamentalne operacje, które stosuje się do podzbiorów przestrzeni rozwiązań, zorganizowanych w postaci drzewa poszukiwań.

  • Rozgałęzianie (ang. Branching) — to proces rekurencyjnego podziału bieżącego zbioru dopuszczalnych rozwiązań Si na kilka mniejszych, z reguły rozłącznych podzbiorów Si1,Si2,…,Sik. Każdy taki podzbiór odpowiada nowej podproblemowi i jest reprezentowany jako węzeł potomny w drzewie poszukiwań. Na przykład, w zadaniach programowania całkowitoliczbowego rozgałęzianie często przeprowadza się według zmiennej mającej wartość ułamkową w rozwiązaniu relaksacji LP.
  • Wyznaczanie ograniczeń (ang. Bounding) — dla każdego węzła drzewa poszukiwań (tj. dla każdego podproblemu) obliczana jest ocena wartości funkcji celu. Dla zadania minimalizacji jest to dolne ograniczenie (lower bound), które stanowi gwarantowaną ocenę od dołu dla dowolnego rozwiązania w danym podzbiorze. Najczęściej ocena ta jest uzyskiwana poprzez rozwiązanie relaksacji wyjściowego podproblemu — uproszczonej wersji, w której pewne skomplikowane ograniczenia (np. całkowitoliczbowości) są tymczasowo pomijane. Najbardziej rozpowszechnioną jest relaksacja LP.
  • Przycinanie (ang. Pruning) — to proces wykluczania z rozpatrywania węzłów (i odpowiadających im całych poddrzew), które z góry nie mogą zawierać optymalnego rozwiązania. Węzeł jest przycinany w jednym z następujących przypadków:
  1. Przycinanie według ograniczenia: Dolne ograniczenie dla danego węzła okazuje się nie lepsze (tj. większe lub równe dla zadania minimalizacji) niż wartość najlepszego jak dotąd znalezionego dopuszczalnego rozwiązania, zwanego rekordem (incumbent).
  2. Przycinanie według dopuszczalności: Rozwiązanie relaksacji węzła jest dopuszczalne dla wyjściowego zadania (np. wszystkie zmienne są całkowitoliczbowe). Rozwiązanie to jest porównywane z bieżącym rekordem i, jeśli jest lepsze, rekord jest aktualizowany. Dalsze rozgałęzianie z tego węzła nie jest wymagane.
  3. Przycinanie według nierozwiązywalności: Podproblem odpowiadający węzłowi nie ma dopuszczalnych rozwiązań.

Ogólny algorytm

Uogólniony algorytm metody podziału i ograniczeń dla zadania minimalizacji można opisać następującymi krokami:

  1. Inicjalizacja: Znaleźć początkowe dopuszczalne rozwiązanie (np. za pomocą heurystyki) i ustawić jego wartość jako początkowe górne ograniczenie (rekord) U. Utworzyć kolejkę aktywnych węzłów Q zawierającą węzeł korzenia (zadanie wyjściowe).
  2. Pętla główna: Dopóki kolejka Q nie jest pusta:
    • Wybrać węzeł z Q zgodnie ze strategią poszukiwania (np. przeszukiwanie w głąb lub według najlepszej oceny).
    • Rozwiązać relaksację dla tego węzła, uzyskując dolne ograniczenie L.
    • Przyciąć węzeł, jeśli L≥U.
    • Jeśli rozwiązanie relaksacji jest dopuszczalne dla wyjściowego zadania, zaktualizować rekord: U←L.
    • Jeśli węzeł nie został przycięty i rozwiązanie nie jest dopuszczalne, wykonać rozgałęzianie, dzieląc go na węzły potomne i dodając je do kolejki Q.
  3. Zakończenie: Gdy kolejka Q staje się pusta, algorytm kończy działanie. Znalezione rozwiązanie odpowiadające rekordowi U jest globalnie optymalne.

Kluczowe właściwości i twierdzenia

  • Poprawność i zbieżność: Algorytm gwarantuje znalezienie globalnie optymalnego rozwiązania w skończonej liczbie kroków, jeśli zbiór dopuszczalnych rozwiązań jest skończony, a procedura rozgałęziania jest zbieżna (tzn. przy rekurencyjnym podziale podzbiory „kurczą się" do punktów)[4].
  • Strategia poszukiwania: Efektywność algorytmu silnie zależy od strategii wyboru następnego węzła do rozgałęziania (np. przeszukiwanie w głąb, przeszukiwanie wszerz, przeszukiwanie według najlepszej oceny) oraz od wyboru zmiennej do rozgałęziania. Współczesne solwery często stosują strategie hybrydowe[5].

Przykłady

  • Zadanie programowania całkowitoliczbowego: Klasyczne zastosowanie metody. Jako relaksacja stosowane jest programowanie liniowe. Rozgałęzianie odbywa się według zmiennej ułamkowej xj, tworząc dwa podproblemy z dodatkowymi ograniczeniami xj≤⌊xj∗⌋ i xj≥⌈xj∗⌉.
  • Problem komiwojażera: Przestrzeń rozwiązań to wszystkie możliwe cykle Hamiltona w grafie. Rozgałęzianie może być realizowane według krawędzi (włącz/wyklucz krawędź z trasy). Jako dolne ograniczenia można stosować rozwiązania prostszych zadań, takich jak problem przydziału lub wyznaczanie minimalnego drzewa rozpinającego[6].

Powiązane pojęcia i zastosowania

  • Metoda podziału i cięć (Branch-and-Cut): Metoda hybrydowa łącząca B&B z metodą płaszczyzn tnących. W każdym węźle drzewa poszukiwań, oprócz rozwiązania relaksacji, generowane są dodatkowe nierówności (cięcia), które wzmacniają dolne ograniczenie, co prowadzi do bardziej efektywnego przycinania gałęzi.
  • Przeszukiwanie z nawrotami (Backtracking): Metodę podziału i ograniczeń można traktować jako uogólnienie tego algorytmu dla zadań optymalizacyjnych.
  • Cięcie alfa-beta: Koncepcyjna analogia stosowana w drzewach gry do odcinania z góry przegranych gałęzi.

Zobacz też

  • Programowanie całkowitoliczbowe
  • Optymalizacja kombinatoryczna
  • Problem komiwojażera
  • Zadanie NP-trudne
  • Metoda simplex

Przypisy

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.info/int/index.php?title=Metoda_podziału_i_ograniczeń&oldid=4310"