--- title: "Metoda podziału i ograniczeń" source: "https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84" wiki: "systems-analysis.info/int" article: "Metoda_podziału_i_ograniczeń" language: "pl" categories: - "Category:Operations research" - "Category:Polish" revision_id: 4310 wiki_created_at: 2026-09-06T23:33:26Z wiki_modified_at: 2026-09-06T23:33:26Z downloaded_at: 2026-09-07T23:01:57Z --- # Metoda podziału i ograniczeń **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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-en-wiki-bnb-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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-ru-wiki-bnb-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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-land-doig-1960-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ń $S_{i}$ na kilka mniejszych, z reguły rozłącznych podzbiorów $S_{i1},S_{i2},\ldots,S_{ik}$. 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 \geq U$. - Jeśli rozwiązanie relaksacji jest dopuszczalne dla wyjściowego zadania, zaktualizować rekord: $U\leftarrow 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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-conitzer-duke-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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-maudet-danoy-2024-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 $x_{j}$, tworząc dwa podproblemy z dodatkowymi ograniczeniami $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ i $x_{j} \geq \lceil x_{j}^{\ast}\rceil$. - **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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-little-1963-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\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-en-wiki-bnb-1) [\[2\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-ru-wiki-bnb-2) [\[3\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-land-doig-1960-3) [\[4\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-conitzer-duke-4) [\[5\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-maudet-danoy-2024-5) [\[6\]](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_note-little-1963-6) \ 1. ↑ [1.0](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-en-wiki-bnb_1-0) [1.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-en-wiki-bnb_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](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-ru-wiki-bnb_2-0) [2.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-ru-wiki-bnb_2-1) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. ↑ [3.0](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-land-doig-1960_3-0) [3.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-land-doig-1960_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](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-conitzer-duke_4-0) [4.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-conitzer-duke_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](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-maudet-danoy-2024_5-0) [5.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-maudet-danoy-2024_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](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-little-1963_6-0) [6.1](https://systems-analysis.info/int/Metoda_podzia%C5%82u_i_ogranicze%C5%84#cite_ref-little-1963_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