Metoda ramificării și limitării

From Systems analysis Wiki
Jump to navigation Jump to search

Metoda ramificării și marginalizării (engl. Branch and Bound, abrev. B&B sau BnB) — este o paradigmă generală de construire a algoritmilor exacți pentru rezolvarea problemelor de optimizare discretă și combinatorială, în particular a problemelor NP-dificile[1]. Metoda reprezintă o strategie de enumerare dirijată, în care întreaga mulțime a soluțiilor admisibile este împărțită succesiv în submulțimi (ramificare), iar pentru fiecare dintre acestea se calculează estimări (margini) ale valorii funcției obiectiv. Aceste estimări permit eliminarea (tăierea) acelor submulțimi care în mod evident nu conțin soluții optime, reducând semnificativ spațiul de căutare[2].

Metoda a fost propusă pentru prima dată de A. Land și A. Doig în 1960 pentru rezolvarea problemelor de programare în numere întregi[3]. De atunci, ea a devenit una dintre cele mai fundamentale abordări în cercetarea operațională și în informatică. Caracteristica esențială a metodei este flexibilitatea sa: ea nu reprezintă un algoritm concret, ci o schemă strategică de nivel înalt (framework), adaptabilă la structura problemei rezolvate.

Componentele cheie ale metodei

La baza metodei se află trei operații fundamentale, care se aplică submulțimilor spațiului soluțiilor, organizate sub forma unui arbore de căutare.

  • Ramificarea (engl. Branching) — este procesul de divizare recursivă a mulțimii curente de soluții admisibile Si în mai multe submulțimi mai mici, în general disjuncte Si1,Si2,…,Sik. Fiecare astfel de submulțime corespunde unei noi subprobleme și este reprezentată ca un nod fiu în arborele de căutare. De exemplu, în problemele de programare în numere întregi, ramificarea se efectuează adesea după variabila care are o valoare fracționară în soluția relaxării LP.
  • Estimarea marginilor (engl. Bounding) — pentru fiecare nod al arborelui de căutare (adică pentru fiecare subproblemă) se calculează o estimare a valorii funcției obiectiv. Pentru o problemă de minimizare, aceasta este marginea inferioară (lower bound), care reprezintă o estimare garantată de jos pentru orice soluție din submulțimea dată. Cel mai adesea, această estimare se obține prin rezolvarea relaxării subproblemei inițiale — o versiune simplificată în care anumite constrângeri dificile (de exemplu, de integritate) sunt ignorate temporar. Cea mai răspândită este relaxarea LP.
  • Tăierea (engl. Pruning) — este procesul de excludere din considerare a nodurilor (și a subarborilor corespunzători) care în mod evident nu pot conține soluția optimă. Un nod este tăiat în unul dintre următoarele cazuri:
  1. Tăiere după margine: Marginea inferioară pentru nodul dat nu este mai bună (adică este mai mare sau egală, pentru problema de minimizare) decât valoarea celei mai bune soluții admisibile găsite până în prezent, numită soluție curentă optimă (incumbent).
  2. Tăiere după admisibilitate: Soluția relaxării nodului este admisibilă pentru problema inițială (de exemplu, toate variabilele sunt întregi). Această soluție este comparată cu soluția curentă optimă și, dacă este mai bună, soluția curentă optimă este actualizată. Ramificarea ulterioară din acest nod nu este necesară.
  3. Tăiere după infezabilitate: Subproblema corespunzătoare nodului nu are soluții admisibile.

Algoritmul general

Algoritmul generalizat al metodei ramificării și marginalizării pentru o problemă de minimizare poate fi descris prin următorii pași:

  1. Inițializare: Se găsește o soluție admisibilă inițială (de exemplu, cu ajutorul unei euristici) și se stabilește valoarea acesteia ca limită superioară inițială (soluție curentă optimă) U. Se creează o coadă de noduri active Q, conținând nodul rădăcină (problema inițială).
  2. Bucla principală: Cât timp coada Q nu este goală:
    • Se selectează un nod din Q conform strategiei de căutare (de exemplu, căutare în adâncime sau după cea mai bună estimare).
    • Se rezolvă relaxarea pentru acest nod, obținând marginea inferioară L.
    • Se taie nodul dacă L≥U.
    • Dacă soluția relaxării este admisibilă pentru problema inițială, se actualizează soluția curentă optimă: U←L.
    • Dacă nodul nu a fost tăiat și soluția nu este admisibilă, se efectuează ramificarea, împărțindu-l în noduri fii, care sunt adăugate în coadă Q.
  3. Terminare: Când coada Q devine goală, algoritmul se încheie. Soluția găsită, corespunzătoare soluției curente optime U, este optim global.

Proprietăți cheie și teoreme

  • Corectitudine și convergență: Algoritmul garantează găsirea soluției optim global într-un număr finit de pași, dacă mulțimea soluțiilor admisibile este finită, iar procedura de ramificare este convergentă (adică, prin divizare recursivă, submulțimile „se contractă" către puncte)[4].
  • Strategia de căutare: Eficiența algoritmului depinde în mare măsură de strategia de selectare a următorului nod pentru ramificare (de exemplu, căutare în adâncime, căutare în lățime, căutare după cea mai bună estimare) și de alegerea variabilei de ramificare. Solverele moderne utilizează adesea strategii hibride[5].

Exemple

  • Problema programării în numere întregi: Aplicația clasică a metodei. Ca relaxare se utilizează programarea liniară. Ramificarea se efectuează după variabila fracționară xj, creând două subprobleme cu constrângeri suplimentare xj≤⌊xj∗⌋ și xj≥⌈xj∗⌉.
  • Problema comis-voiajorului: Spațiul soluțiilor cuprinde toate ciclurile hamiltoniene posibile dintr-un graf. Ramificarea poate fi realizată după muchii (a include/exclude o muchie din traseu). Ca margini inferioare pot fi utilizate soluțiile unor probleme mai simple, precum problema de atribuire sau construirea arborelui de acoperire minim[6].

Noțiuni conexe și aplicații

  • Metoda ramificării și tăierilor (Branch-and-Cut): O metodă hibridă care combină B&B cu metoda planelor de tăiere. La fiecare nod al arborelui de căutare, pe lângă rezolvarea relaxării, se generează inegalități suplimentare (tăieri) care întăresc marginea inferioară, conducând la o tăiere mai eficientă a ramurilor.
  • Căutarea cu revenire (Backtracking): Metoda ramificării și marginalizării poate fi privită ca o generalizare a acestui algoritm pentru problemele de optimizare.
  • Tăierea alfa-beta: O analogie conceptuală utilizată în arborii de joc pentru eliminarea ramurilor în mod evident perdante.

Vezi și

  • Programare în numere întregi
  • Optimizare combinatorială
  • Problema comis-voiajorului
  • Problemă NP-dificilă
  • Metoda simplex

Note

  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. ↑ Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 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. ↑ 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. ↑ 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. ↑ 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_ramificării_și_limitării&oldid=4311"