Pamamaraang branch and bound

Pamamaraan ng mga sanga at hangganan (Ingles: Branch and Bound, pinaikli B&B o BnB) — ito ay isang pangkalahatang paradigma ng pagbuo ng tumpak na mga algorithm para sa paglutas ng mga problema ng discrete at combinatorial optimization, lalo na ng mga NP-mahirap na problema^[1]. Ang pamamaraan ay kumakatawan sa isang estratehiya ng nakatuong paghahanap, kung saan ang buong hanay ng mga katanggap-tanggap na solusyon ay sunud-sunod na nahahati sa mga subset (pag-sanga), at para sa bawat isa sa kanila ay kinakalkula ang mga pagtatantya (mga hangganan) ng halaga ng objective function. Ang mga pagtatantyang ito ay nagpapahintulot na itapon (putulin) ang mga subset na tiyak na hindi naglalaman ng mga optimal na solusyon, na makabuluhang nagpapababa ng espasyo ng paghahanap^[2].

Ang pamamaraan ay unang iminungkahi nina A. Land at A. Doig noong 1960 para sa paglutas ng mga problema ng integer programming^[3]. Mula noon, ito ay naging isa sa mga pinaka-pundamental na diskarte sa operations research at computer science. Ang pangunahing katangian ng pamamaraan ay ang kakayahang umangkop nito: ito ay hindi isang tiyak na algorithm, kundi isang mataas na antas na estratehikong pamamaraan (framework), na angkop sa istraktura ng problemang nireresolba.

Mga Pangunahing Bahagi ng Pamamaraan

Sa pundasyon ng pamamaraan ay tatlong pundamental na operasyon, na inilalapat sa mga subset ng espasyo ng mga solusyon, na nakaayos sa anyo ng isang puno ng paghahanap.

Pag-sanga (Ingles: Branching) — ito ang proseso ng rekursibong paghahati ng kasalukuyang hanay ng mga katanggap-tanggap na solusyon $S_{i}$ sa ilang mas maliit, kadalasan ay hindi magkakapatong na mga subset $S_{i 1}, S_{i 2}, \dots, S_{i k}$ . Ang bawat naturang subset ay tumutugma sa isang bagong subproblema at kinakatawan bilang isang child node sa puno ng paghahanap. Halimbawa, sa mga problema ng integer programming, ang pag-sanga ay kadalasang ginagawa ayon sa variable na may fractional na halaga sa solusyon ng LP-relaxation.

Pagtatantya ng mga hangganan (Ingles: Bounding) — para sa bawat node ng puno ng paghahanap (ibig sabihin, para sa bawat subproblema) ay kinakalkula ang pagtatantya ng halaga ng objective function. Para sa problema ng minimization, ito ay ang lower bound, na isang garantisadong pagtatantya mula sa ibaba para sa anumang solusyon sa ibinigay na subset. Kadalasan, ang pagtatantyang ito ay nakuha sa pamamagitan ng paglutas ng relaxation ng orihinal na subproblema — isang pinasimpleng bersyon, kung saan ang ilang mahirap na hadlang (halimbawa, integridad) ay pansamantalang hindi pinapansin. Ang pinaka-karaniwang ginagamit ay ang LP-relaxation.

Pagputol (Ingles: Pruning) — ito ang proseso ng pagbubukod mula sa pagsasaalang-alang ng mga node (at ng kani-kanilang mga buong subtree), na tiyak na hindi maaaring maglaman ng optimal na solusyon. Ang isang node ay pinutol sa isa sa mga sumusunod na kaso:

Pagputol ayon sa hangganan: Ang lower bound para sa ibinigay na node ay hindi mas mabuti (ibig sabihin, mas malaki o katumbas para sa problema ng minimization) kaysa sa halaga ng pinakamahusay na nahanap na katanggap-tanggap na solusyon sa kasalukuyan, na tinatawag na rekord (incumbent).
Pagputol ayon sa katanggap-tanggap: Ang solusyon ng relaxation ng node ay katanggap-tanggap para sa orihinal na problema (halimbawa, lahat ng variable ay integer). Ang solusyong ito ay inihahambing sa kasalukuyang rekord at, kung ito ay mas mabuti, ang rekord ay ina-update. Ang karagdagang pag-sanga mula sa node na ito ay hindi na kinakailangan.
Pagputol ayon sa hindi malulutas: Ang subproblema na tumutugma sa node ay walang mga katanggap-tanggap na solusyon.

Pangkalahatang Algorithm

Ang pangkalahatang algorithm ng pamamaraan ng mga sanga at hangganan para sa problema ng minimization ay maaaring ilarawan sa mga sumusunod na hakbang:

Pagsisimula: Hanapin ang paunang katanggap-tanggap na solusyon (halimbawa, sa tulong ng heuristic) at itakda ang halaga nito bilang paunang upper bound (rekord) $U$ . Lumikha ng pila ng mga aktibong node $Q$ , na naglalaman ng root node (ang orihinal na problema).
Pangunahing ikot: Habang ang pila Q ay hindi walang laman:
- Pumili ng node mula sa $Q$ ayon sa estratehiya ng paghahanap (halimbawa, depth-first search o best-first search).
- Resolbahin ang relaxation para sa node na ito, na makukuha ang lower bound $L$ .
- Putulin ang node, kung $L \geq U$ .
- Kung ang solusyon ng relaxation ay katanggap-tanggap para sa orihinal na problema, i-update ang rekord: $U \leftarrow L$ .
- Kung ang node ay hindi pinutol at ang solusyon ay hindi katanggap-tanggap, magsagawa ng pag-sanga, na hahati nito sa mga child node, at idagdag ang mga ito sa pila $Q$ .
Pagtatapos: Kapag ang pila $Q$ ay naging walang laman, ang algorithm ay natatapos. Ang nahanap na solusyon na tumutugma sa rekord $U$ ay globally optimal.

Mga Pangunahing Katangian at Teorema

Kawastuhan at konverhensia: Ang algorithm ay garantisadong makakahanap ng globally optimal na solusyon sa loob ng isang tiyak na bilang ng mga hakbang, kung ang hanay ng mga katanggap-tanggap na solusyon ay may hangganan, at ang pamamaraan ng pag-sanga ay konverxente (ibig sabihin, sa rekursibong paghahati, ang mga subset ay "nagkukompresyon" patungo sa mga punto)^[4].
Estratehiya ng paghahanap: Ang kahusayan ng algorithm ay lubos na nakasalalay sa estratehiya ng pagpili ng susunod na node para sa pag-sanga (halimbawa, depth-first search, breadth-first search, best-first search) at sa pagpili ng variable para sa pag-sanga. Ang mga modernong solver ay kadalasang gumagamit ng mga hybrid na estratehiya^[5].

Mga Halimbawa

Problema ng integer programming: Klasikong aplikasyon ng pamamaraan. Bilang relaxation, ginagamit ang linear programming. Ang pag-sanga ay nagaganap ayon sa fractional na variable $x_{j}$ , na lumilikha ng dalawang subproblema na may karagdagang mga hadlang $x_{j} \leq ⌊ x_{j}^{*} ⌋$ at $x_{j} \geq ⌈ x_{j}^{*} ⌉$ .
Problema ng travelling salesman: Ang espasyo ng mga solusyon ay lahat ng posibleng Hamiltonian cycle sa isang graph. Ang pag-sanga ay maaaring isagawa ayon sa mga gilid (isama/ibukod ang gilid mula sa ruta). Bilang mga lower bound, maaaring gamitin ang mga solusyon ng mas simpleng mga problema, tulad ng problema ng assignment o pagbuo ng minimum spanning tree^[6].

Mga Kaugnay na Konsepto at Aplikasyon

Branch-and-Cut: Isang hybrid na pamamaraan na pinagsama ang B&B sa pamamaraan ng cutting planes. Sa bawat node ng puno ng paghahanap, bukod sa paglutas ng relaxation, ang mga karagdagang hindi pagkakapantay-pantay (mga pagputol) ay nabubuo, na nagpapalakas ng lower bound, na humahantong sa mas mahusay na pagputol ng mga sanga.
Backtracking: Ang pamamaraan ng mga sanga at hangganan ay maaaring ituring bilang isang pagpapalawak ng algorithm na ito para sa mga problema ng optimization.
Alpha-beta pruning: Isang konseptwal na pagkakatulad, na ginagamit sa mga game tree para sa pagputol ng mga sangay na tiyak na matatalo.

Tingnan din

Integer programming
Combinatorial optimization
Problema ng travelling salesman
NP-mahirap na problema
Simplex method

Mga Tala

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

↑ ^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.0 ^2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
↑ ^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.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.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.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

[en-wiki-bnb-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

[ru-wiki-bnb-2] 2.0 ^2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ

[land-doig-1960-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

[conitzer-duke-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

[maudet-danoy-2024-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

[little-1963-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

[1]

[2]

[3]

[4]

[5]

[6]

Pamamaraang branch and bound

Contents

Mga Pangunahing Bahagi ng Pamamaraan

Pangkalahatang Algorithm

Mga Pangunahing Katangian at Teorema

Mga Halimbawa

Mga Kaugnay na Konsepto at Aplikasyon

Tingnan din

Mga Tala

Navigation menu

Pamamaraang branch and bound

Mga Pangunahing Bahagi ng Pamamaraan

Pangkalahatang Algorithm

Mga Pangunahing Katangian at Teorema

Mga Halimbawa

Mga Kaugnay na Konsepto at Aplikasyon

Tingnan din

Mga Tala

Navigation menu

Search