branchandboundtechnieken

Branch-and-boundtechnieken vormen een verzameling algoritmen voor combinatoriële optimalisatie, gericht op het vinden van een optimale oplossing of het bewijs dat zo’n oplossing niet bestaat binnen een gegeven oplossingsruimte. Ze worden toegepast op problemer zoals knapsack, reizende handelaar, grafiekgerelateerde problemen en vele vormen van integer programming.

De methode werkt door een zoekboom te construire ren waar elk knooppunt een gedeeltelijke oplossing vertegenwoordigt. Voor elk knooppunt wordt een bound bepaald: bij minimisatie een ondergrens van de mogelijke doelwaarde, bij maximisatie een bovengrens. Als de bound slechter is dan de huidige beste oplossing, wordt het hele subboomgebied uitgebuimd (pruning). Op die manier worden veel ongunstige deelproblemen snel uitgesloten.

Bindende grenzen worden vaak verkregen door relaxaties van het probleem, bijvoorbeeld een lineaire program nar-relaxatie of andere exemplarische relaxaties die snel op te lossen zijn. Daarnaast wordt een feasible oplossing gezocht om een bovengegrens (of in minimisatie–upper bound) te leveren, zodat de zoekruimte sneller kan worden beperkt. Heuristische methoden kunnen een goede startoplossing geven en zo de efficiëntie van het prunen verhogen.

Branching-strategieën bepalen hoe het probleem wordt opgesplitst, bijvoorbeeld welke variabele wordt gekozen en op welke wijze de subproblemen ontstaan. Zoekvolgorde kan DFS, best-first of andere prioriteitsgebaseerde benaderingen zijn, vaak gestuurd door de boundwaarde van knopen.

Varianten zoals branch-and-cut (met snijvlakken), branch-and-price (met kolomgeneratie) en gerelateerde methoden worden vaak toegepast in operationele research en integer programming. De prestaties hangen af van boundkwaliteit, probleemstructuur en heuristische initiatieven. Historisch dateert het begin uit de jaren zestig met bijdragen van Land en Doig.