Tree Bisection Reconnection (TBR)

Tree Bisection and Reconnection is a search heuristic which reduces the number of topologies searched, so that we don’t have to perform an exhaustive search of all possible tree topologies.

TBR selects a subtree, and deletes the internal branch which connects it to the main tree. This subtree is now not connected to the main tree, which leaves us with 2 trees. The subtree is then reconnected to the main tree in all possible connections between the branches of the two trees. If any of the reconnected trees score better than the currently best tree, the algorithm selects that tree as the new best tree and performs another round of bisection, reconnection, and scoring.