Branch and bound-metoden

From Systems analysis Wiki
Jump to navigation Jump to search

Metoden för grenar och gränser (eng. Branch and Bound, förk. B&B eller BnB) — är ett allmänt paradigm för att konstruera exakta algoritmer för att lösa problem inom diskret och kombinatorisk optimering, i synnerhet NP-svåra problem[1]. Metoden utgör en strategi för riktad sökning, där hela mängden tillåtna lösningar successivt delas upp i delmängder (förgrening), och för var och en av dessa beräknas uppskattningar (gränser) av målfunktionens värde. Dessa uppskattningar gör det möjligt att förkasta (beskära) de delmängder som uppenbarligen inte innehåller optimala lösningar, vilket väsentligt minskar sökrummet[2].

Metoden föreslogs första gången av A. Land och A. Doig år 1960 för att lösa problem inom heltalsprogrammering[3]. Sedan dess har den blivit ett av de mest grundläggande angreppssätten inom operations­forskning och datavetenskap. Metodens viktigaste egenskap är dess flexibilitet: den är inte en specifik algoritm, utan ett övergripande strategiskt schema (framework), anpassningsbart till strukturen hos det problem som ska lösas.

Metodens nyckelkomponenter

Metoden bygger på tre fundamentala operationer som tillämpas på delmängder av lösningsrummet, organiserade i form av ett sökträd.

  • Förgrening (eng. Branching) — är processen att rekursivt dela upp den aktuella mängden tillåtna lösningar Si i flera mindre, vanligtvis icke-överlappande delmängder Si1,Si2,…,Sik. Varje sådan delmängd motsvarar ett nytt delproblem och representeras som en barnnod i sökträdet. Inom heltalsprogrammering utförs förgrening exempelvis ofta med avseende på en variabel som har ett bråkvärde i LP-relaxationslösningen.
  • Gränsberäkning (eng. Bounding) — för varje nod i sökträdet (dvs. för varje delproblem) beräknas en uppskattning av målfunktionens värde. För ett minimeringsproblem är detta en undre gräns (lower bound), som utgör en garanterad underifrån-uppskattning för varje lösning i den aktuella delmängden. Denna uppskattning erhålls oftast genom att lösa en relaxation av det ursprungliga delproblemet — en förenklad version där vissa svåra begränsningar (t.ex. heltalskrav) tillfälligt ignoreras. Den vanligaste är LP-relaxationen.
  • Beskärning (eng. Pruning) — är processen att utesluta noder (och motsvarande hela delträd) som uppenbarligen inte kan innehålla den optimala lösningen. En nod beskärs i ett av följande fall:
  1. Beskärning utifrån gräns: Den undre gränsen för den aktuella noden är inte bättre (dvs. är större än eller lika med, för ett minimeringsproblem) än värdet hos den hittills bästa funna tillåtna lösningen, kallad rekord (incumbent).
  2. Beskärning utifrån tillåtlighet: Relaxationslösningen för noden är tillåten för det ursprungliga problemet (t.ex. är alla variabler heltal). Denna lösning jämförs med det aktuella rekordet och, om den är bättre, uppdateras rekordet. Ytterligare förgrening från denna nod krävs inte.
  3. Beskärning utifrån olöslighet: Det delproblem som motsvarar noden saknar tillåtna lösningar.

Allmän algoritm

Den generaliserade algoritmen för metoden för grenar och gränser, tillämpad på ett minimeringsproblem, kan beskrivas med följande steg:

  1. Initialisering: Hitta en inledande tillåten lösning (t.ex. med hjälp av en heuristik) och sätt dess värde som initial övre gräns (rekord) U. Skapa en kö med aktiva noder Q som innehåller rotnoden (det ursprungliga problemet).
  2. Huvudloop: Så länge kön Q inte är tom:
    • Välj en nod ur Q i enlighet med sökstrategin (t.ex. djupet-först-sökning eller bästa-först-sökning).
    • Lös relaxationen för denna nod och erhåll en undre gräns L.
    • Beskär noden om L≥U.
    • Om relaxationslösningen är tillåten för det ursprungliga problemet, uppdatera rekordet: U←L.
    • Om noden inte beskärs och lösningen inte är tillåten, utför förgrening genom att dela upp den i barnnoder och lägg till dem i kön Q.
  3. Avslutning: När kön Q blir tom avslutas algoritmen. Den funna lösning som motsvarar rekordet U är globalt optimal.

Viktiga egenskaper och satser

  • Korrekthet och konvergens: Algoritmen garanterar att en globalt optimal lösning hittas på ett ändligt antal steg, förutsatt att mängden tillåtna lösningar är ändlig och att förgreningsproceduren är konvergent (dvs. att delmängderna vid rekursiv uppdelning "krymper" mot punkter)[4].
  • Sökstrategi: Algoritmens effektivitet beror i hög grad på strategin för val av nästa nod att förgrena (t.ex. djupet-först-sökning, bredden-först-sökning, bästa-först-sökning) samt på valet av variabel att förgrena på. Moderna lösare använder ofta hybrida strategier[5].

Exempel

  • Heltalsprogrammeringsproblem: Metodens klassiska tillämpning. Som relaxation används linjär programmering. Förgrening sker med avseende på en bråkvariabel xj, vilket skapar två delproblem med ytterligare begränsningar xj≤⌊xj∗⌋ och xj≥⌈xj∗⌉.
  • Handelsresandeproblemet: Lösningsrummet utgörs av alla möjliga Hamiltonska cykler i grafen. Förgrening kan ske med avseende på kanter (inkludera/exkludera en kant i rutten). Som undre gränser kan lösningar till enklare problem användas, såsom tilldelningsproblemet eller konstruktion av ett minimalt uppspännande träd[6].

Relaterade begrepp och tillämpningar

  • Grene-och-snitt-metoden (Branch-and-Cut): En hybridmetod som kombinerar B&B med skärningsplansmetoden. I varje nod i sökträdet genereras, utöver relaxationslösningen, ytterligare olikheter (snitt) som förstärker den undre gränsen, vilket leder till effektivare beskärning av grenar.
  • Sökning med återgång (Backtracking): Metoden för grenar och gränser kan betraktas som en generalisering av denna algoritm för optimeringsproblem.
  • Alfa-beta-beskärning: En konceptuell analogi som används i spelträd för att beskära grenar som uppenbarligen leder till förlust.

Se även

  • Heltalsprogrammering
  • Kombinatorisk optimering
  • Handelsresandeproblemet
  • NP-svårt problem
  • Simplexmetoden

Noter

[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=Branch_and_bound-metoden&oldid=809"