Branch-and-bound-methode

De methode van vertakkingen en grenzen (Engels: Branch and Bound, afgekort B&B of BnB) is een algemeen paradigma voor het construeren van exacte algoritmen voor het oplossen van discrete en combinatorische optimalisatieproblemen, in het bijzonder NP-moeilijke problemen. De methode is een strategie van gerichte enumeratie, waarbij de volledige verzameling van toegestane oplossingen stapsgewijs wordt opgedeeld in deelverzamelingen (vertakking), en voor elk daarvan schattingen (grenzen) van de doelfunctiewaarde worden berekend. Deze schattingen maken het mogelijk om die deelverzamelingen af te snijden die aantoonbaar geen optimale oplossingen bevatten, wat de zoekruimte aanzienlijk verkleint.

De methode werd voor het eerst voorgesteld door A. Land en A. Doig in 1960 voor het oplossen van geheeltallige programmeringsproblemen. Sindsdien is het een van de meest fundamentele benaderingen in operations research en de informatica geworden. Het belangrijkste kenmerk van de methode is haar flexibiliteit: het is geen concreet algoritme, maar een strategisch schema op hoog niveau (een framework) dat aanpasbaar is aan de structuur van het te behandelen probleem.

Kerncomponenten van de methode

De methode is gebaseerd op drie fundamentele operaties die worden toegepast op deelverzamelingen van de oplossingsruimte, georganiseerd als een zoekboom.

• Vertakking (Engels: Branching) — dit is het proces van het recursief opdelen van de huidige verzameling toegestane oplossingen $S_i$ in meerdere kleinere, doorgaans disjuncte deelverzamelingen $S_{i1},S_{i2},\dots ,S_{ik}$. Elk van deze deelverzamelingen correspondeert met een nieuw deelprobleem en wordt weergegeven als een kindknoop in de zoekboom. Bij geheeltallige programmeringsproblemen wordt er bijvoorbeeld vaak vertakt op een variabele die een fractionele waarde heeft in de LP-relaxatieoplossing.

• Grensschatting (Engels: Bounding) — voor elke knoop van de zoekboom (d.w.z. voor elk deelprobleem) wordt een schatting van de doelfunctiewaarde berekend. Voor een minimalisatieprobleem is dit de ondergrens (lower bound), een gegarandeerde schatting van beneden voor elke oplossing in de betreffende deelverzameling. Meestal wordt deze schatting verkregen door het oplossen van een relaxatie van het oorspronkelijke deelprobleem — een vereenvoudigde versie waarbij bepaalde zware beperkingen (zoals geheeltalligheid) tijdelijk worden genegeerd. De meest gebruikte vorm is de LP-relaxatie.

• Afsnijding (Engels: Pruning) — dit is het proces van het uitsluiten van knopen (en de bijbehorende gehele deelbomen) die aantoonbaar geen optimale oplossing kunnen bevatten. Een knoop wordt afgesneden in een van de volgende gevallen:

1. Afsnijding op basis van de grens: De ondergrens voor de betreffende knoop is niet beter (d.w.z. groter dan of gelijk aan, bij minimalisatie) dan de waarde van de beste tot dusver gevonden toegestane oplossing, het zogenoemde record (incumbent).
2. Afsnijding op basis van toelaatbaarheid: De relaxatieoplossing van de knoop is toelaatbaar voor het oorspronkelijke probleem (bijvoorbeeld wanneer alle variabelen geheeltallig zijn). Deze oplossing wordt vergeleken met het huidige record en als zij beter is, wordt het record bijgewerkt. Verdere vertakking vanuit deze knoop is niet nodig.
3. Afsnijding op basis van onoplostbaarheid: Het deelprobleem dat overeenkomt met de knoop heeft geen toegestane oplossingen.

Algemeen algoritme

Het gegeneraliseerde algoritme van de methode van vertakkingen en grenzen voor een minimalisatieprobleem kan worden beschreven aan de hand van de volgende stappen:

1. Initialisatie: Zoek een beginoplossing (bijvoorbeeld met behulp van een heuristiek) en stel de waarde ervan in als de beginbovengrens (record) $U$. Maak een wachtrij van actieve knopen $Q$ aan die de wortelknoop (het oorspronkelijke probleem) bevat.
2. Hoofdlus: Zolang de wachtrij $Q$ niet leeg is:
   • Selecteer een knoop uit $Q$ overeenkomstig de zoekstrategie (bijvoorbeeld diepte-eerst of beste-eerst zoeken).
   • Los de relaxatie voor deze knoop op en bereken de ondergrens $L$.
   • Snijd de knoop af als $L\ge U$.
   • Als de relaxatieoplossing toelaatbaar is voor het oorspronkelijke probleem, werk het record bij: $U\leftarrow L$.
   • Als de knoop niet is afgesneden en de oplossing niet toelaatbaar is, voer vertakking uit door de knoop op te splitsen in kindknopen en voeg deze toe aan de wachtrij $Q$.
3. Afronding: Wanneer de wachtrij $Q$ leeg wordt, eindigt het algoritme. De gevonden oplossing die overeenkomt met het record $U$ is globaal optimaal.

Belangrijke eigenschappen en stellingen

• Correctheid en convergentie: Het algoritme vindt gegarandeerd een globaal optimale oplossing in een eindig aantal stappen, mits de verzameling toegestane oplossingen eindig is en de vertakkingsprocedure convergent is (dat wil zeggen dat de deelverzamelingen bij recursieve opdeling «samentrekken» naar punten).
• Zoekstrategie: De efficiëntie van het algoritme is sterk afhankelijk van de strategie voor het selecteren van de volgende knoop om op te vertakken (zoals diepte-eerst, breedte-eerst of beste-eerst zoeken) en van de keuze van de vertakkingsvariabele. Moderne solvers maken vaak gebruik van hybride strategieën.

Voorbeelden

• Geheeltallig programmeringsprobleem: De klassieke toepassing van de methode. Als relaxatie wordt lineaire programmering gebruikt. Er wordt vertakt op een fractionele variabele $x_j$, waarbij twee deelproblemen worden gecreëerd met aanvullende beperkingen $x_j\le \lfloor x_j^{\ast }\rfloor$ en $x_j\ge \lceil x_j^{\ast }\rceil$.
• Handelsreizigersprobleem: De oplossingsruimte bestaat uit alle mogelijke Hamiltoniaanse kringen in een graaf. Vertakking kan plaatsvinden op kanten (een kant opnemen in of uitsluiten uit de route). Als ondergrenzen kunnen oplossingen van eenvoudigere problemen worden gebruikt, zoals het toewijzingsprobleem of de constructie van een minimaal opspannende boom.

Verwante begrippen en toepassingen

• Branch-and-Cut-methode (Branch-and-Cut): Een hybride methode die B&B combineert met de methode van snijdende vlakken. In elke knoop van de zoekboom worden, naast het oplossen van de relaxatie, aanvullende ongelijkheden (afsnijdingen) gegenereerd die de ondergrens versterken, wat leidt tot effectiever afsnijden van takken.
• Backtracking (Backtracking): De methode van vertakkingen en grenzen kan worden beschouwd als een generalisatie van dit algoritme voor optimalisatieproblemen.
• Alfa-bèta-afsnijding: Een conceptuele analogie die wordt gebruikt in spelboombenadering om aantoonbaar verliezende takken af te snijden.

Zie ook

• Geheeltallig programmeren
• Combinatorische optimalisatie
• Handelsreizigersprobleem
• NP-moeilijk probleem
• Simplexmethode

Noten

</references>