As BnB is an algorithm specialized in seeking changeless solutions, the final selection amount (the sum of all the selected UTXOs amount) can be as high as one unit below the amount where the transaction creation process starts creating a change output. Which is: target + min_viable_change - 1.
In other words, the range of the possible solutions is: target <= solution_amount < target + min_viable_change - 1.
Code level description: We have a discrepancy on the threshold at which we create, or not, “change” between the BnB algorithm and the, higher level, transaction creation process.
BnB selection upper bound uses cost_of_change, while the transaction creation process uses
the min_viable_change variable to obtain the resulting change amount from the coin selection
solution (here).
Essentially, this means that under certain circumstances; when the BnB solution excess is
in-between min_viable_change and cost_of_change, the BnB algorithm returns a
successful solution which, under the transaction creation process perspective, requires to create
change output. This, isn’t an expected behavior as BnB is specialized to only return a changeless
solution.
This can happen when min_viable_change <= BnB_solution_amount - target < cost_of_change.
Note: This should solve the issue presented in #28372.
Testing Note: I have decoupled the test in a standalone commit so it can be easily cherry-picked on top of master to verify the test failure vs the test passing here after the changes.
