How does the Branch and Bound coin selection algorithm work?

_{Disclosure: I’m describing my own work: the Branch and Bound algorithm was first described in my own Master thesis.}

The Branch and Bound algorithm searches for the least wasteful input set that produces a changeless transaction. To that end it deterministically searches all possible relevant combinations of the wallet’s UTXO pool. Since the powerset of a collection grows exponentially in the size of the collection, Branch and Bound bounds its search in a number of ways whenever an area in the search tree cannot yield any better solutions.

The gist of the algorithm is as follows:

1. Calculate the effective value of each UTXO: effective_value = amount - input_weight × feerate
2. Sort the UTXOs descendingly by effective value
3. In order of the sorted UTXOs, keep adding the next UTXO until the total_selected_effective_value exceeds the selection_target
4. If total_selected_effective_value is also smaller than selection_target + cost_of_change_output, we have found an input set that would produce a changeless transaction. Keep this input set if it has a better waste score than the prior best input set.
5. Whenever you exceed the target, backtrack by deselecting the last selected UTXO and omitting it instead.

Let’s assume we have three UTXOs with effective values of 0.1 ₿, 0.09 ₿, and 0.05 ₿. We are searching for an input set that raises 0.14 ₿. Our search would look like this:

^{via Erhardt: An Evaluation of Coin Selection Strategies (2016) [PDF]}

1. {0.1}: We have insufficient funds and continue.
2. {0.1, 0.09}: We select 0.1 ₿, then select 0.09  for a total of 0.19 ₿. We have overshot above the target window. We backtrack.
3. {0.1, 0.05}: We deselect 0.09 ₿, then select 0.05 ₿ for a total of 0.15 ₿. We have overshot above the target window and backtrack. The omission branch of 0.05 ₿ leaves us with insufficient funds. We have completely searched the subtree that starts by selecting the 0.1 UTXO and continue by skipping the 0.1 ₿ UTXO.
4. {0.09}: We have insufficient funds and continue.
5. {0.09, 0.05}: With a total of 0.14 ₿, we have found an input set that produces a changeless transaction. This is our new best input set. The omission branch of 0.05 ₿ has insufficient funds. The omission branch of 0.09 ₿ also only has at most 0.05 ₿, so we cannot find any solution there.

For a wallet with a larger UTXO pool, this search would likely yield multiple solutions. In that case, we would compare the input set candidates on basis of the waste metric and keep the input set with the best (i.e. lowest) waste score.

So far this just generates all possible combinations of inputs, skipping just input sets for which a prefix already exceeded the target.
The implementation in Bitcoin Core limits the number of attempts to 100,000 and has a number of optimizations to skip parts of the search tree that cannot yield better solutions:

• more wasteful: if our current selection already has a worse waste score than the best solution, and we are in the high-feerate mode, we can exit early as adding more inputs can never produce a better solution
• lookahead: by keeping track of the total available effective value in the remaining UTXOs, we can exit subtrees early when there are insufficient funds to reach the target
• max_weight exceeded: if our input set causes the transaction to be bigger than the limit for standard transactions we can exit early, because we cannot find a solution
• skipping clones: if the previous UTXO matches the current UTXO in weight and effective value but is not selected, selecting this UTXO would regenerate equivalent input sets to ones created prior. We can therefore skip selection of this UTXO.