Implementation of BnB is not a Branch and Bound algorithm

[murchandamus]

The Branch and Bound algorithm in Bitcoin searches the complete powerset of the UTXOs skipping over parts of the set that cannot yield sufficient input sets or are equivalent to previously tried combinations.

This is implemented as a depth first search with backtracking. The implementation here uses two nested loops. Two nested loops are insufficient to enumerate the complete power set. (Two nested loops can only generate n² combinations, while a power set has 2ⁿ elements.) As implemented, it only tries the inclusion and omission branches of all starting points of the input sets, but only generates some of the input sets with those starting points.

E.g. when traversing the UTXOs in alphabetical order, if A+C is smaller than the target, but A+C+D is bigger than the target, it will try to combine A+C+D and A+C+E, but it will not combine A+D+E.

[yancyribbens]

This is implemented as a depth first search with backtracking.

I wanted to write a simple BnB implementation in Rust to check my understanding. To that end, here is a depth first search which has a bounding parameter.

Note it's remarkable how simple recursive solutions are! The recursion does the backtracking for us through use of the callstack.

recursive implementation.

 // recursive dfs bound by node sum.
fn dfs(node: &Node, path: &mut Vec<usize>, bound: usize) {
    path.push(node.key);
    let sum: usize = path.iter().sum();

    if sum <= bound {
        println!("* path: {:?}", path);

        let descendants = &node.descendants;

        for d in descendants {
            dfs(d, path, bound);
        }
    }

    path.pop();
}

And here is the same idea, but using an iterative approach instead of relying on recursion:

fn dfs_iter(root: &Node, bound: usize) {
    let mut visited = vec![];
    let mut call_stack = vec![];
    let mut path = vec![];

    call_stack.push(root);
    visited.push(root);

    while !call_stack.is_empty() {
        let node = call_stack.pop().unwrap();

        path.push(node);
        visited.push(node);
        let sum: usize = path.iter().map(|n| n.key).sum();

        if sum <= bound {
            println!("* path: {:?}", path.iter().map(|n| n.key).collect::<Vec<usize>>());

            let descendants = &node.descendants;

            for d in descendants {
                call_stack.push(d);
            }
        }

        // if greater than bound or a leaf node.
        if sum > bound || node.descendants.is_empty() {
            path.pop();

            // backtrack
            loop {
                let n = path.last();

                match n {
                    None => break,
                    Some(n) => {
                        let is_explored = is_explored(n, &visited);
                        if is_explored {
                            path.pop();
                        } else {
                            break;
                        }
                    }
                }
            }
        }
    }
}

Given a tree such as:

          5
        / | \
       /  |  \
      3   1   4
      |  / \
      | 3   2
      2

The two implementations yield the following results if bounded by 8 for example (path sums not greater than 8). The results are the same, but the iterative solution explores nodes in a different order as a by product of the implementation:

recursive: 
* path: [5]
* path: [5, 3]
* path: [5, 1]
* path: [5, 1, 2]

iterative: 
* path: [5]
* path: [5, 1]
* path: [5, 1, 2]
* path: [5, 3]``

[murchandamus]

It’s not obvious to me what the source of the "tree" structure in your UTXO pool would be, or what you would consider "descendants" in the context of a UTXO pool. E.g. it’s not clear to me how your algorithm would generate solutions that do not include 5?

It’s great to experiment with various algorithms, but it might be confusing to your reviewers if you refer to a very different Branch and Bound-based approach as "BnB".

[yancyribbens]

E.g. it’s not clear to me how your algorithm would generate solutions that do not include 5

It's true that this branch and bound algorithm does not pertain to coin-selection in particular, and instead is just an examination of the structure of a branch and bound search in general. However, the general structure can be expanded. For example, the search tree could be:

Pardon my poor ascii art skills :)

        5
include/ \ exclude
      /   \
     3     3
include     exclude
...

This is as you describe in your thesis. Of course, the UTXO set is not in a tree structure as above, so it must be examined and enumerated from a set of values (the utxo set).

[yancyribbens]

On pg 39, Algorithm 10 (Branch and Bound: Search) the sort happens for each recursive call. Line 3 sorts U every time the recursive call happens (Line 15, Line 19). Apologies, I'm not sure if this is the correct place to point out inequities with the algorithm described in in the masters theses as I find them.

[yancyribbens]

Rust isn't guaranteed to implement tail recursion, so unfortunately, like the C++ version, it will need to be implemented as a loop. Anyway, for comparison, here is the translated recursive version looks.

fn branch_and_bound<'a>(
    depth: usize,
    current_selection: &'a mut Vec<WeightedUtxo>,
    utxo_sorted: &'a Vec<WeightedUtxo>,
    eff_value: Amount,
    target: Amount,
    fee_rate: FeeRate,
) -> Option<&'a mut Vec<WeightedUtxo>> {
    if eff_value > target + CHANGE_LOWER {
        return None;
    } else if eff_value >= target {
        return Some(current_selection);
    } else if depth >= utxo_sorted.len() {
        return None;
    } else {
        let weighted_utxo = utxo_sorted[depth].clone();
        let satisfaction_weight = weighted_utxo.satisfaction_weight;
        let weight = satisfaction_weight.checked_add(TxIn::BASE_WEIGHT).unwrap();
        let input_fee = fee_rate.checked_mul_by_weight(weight).unwrap();

        let mut new_current_selection = current_selection.clone();
        new_current_selection.push(weighted_utxo.clone());

        let with_this = branch_and_bound(
            depth + 1,
            &mut new_current_selection,
            utxo_sorted,
            eff_value + weighted_utxo.utxo.value - input_fee,
            target,
            fee_rate,
        );

        if with_this.is_none() {
            return None;
        } else {
            let without_this = branch_and_bound(
                depth + 1,
                current_selection,
                utxo_sorted,
                eff_value,
                target,
                fee_rate,
            );
            if without_this.is_none() {
                return None;
            }
        }
    }   

    Some(current_selection)
}

[yancyribbens]

I've started a new feature branch which I'll PR when it's ready: https://github.com/p2pderivatives/rust-bitcoin-coin-selection/tree/feature/iter-branch-and-bound

// select_coins_bnb performs a depth first search on a binary tree.  This can be thought of as
// exploring a binary tree where the left branch is the inclusion of a node and the right branch is
// the exclusion.  For example, if the utxo set consist of a list of utxos: [4,3,2,1], and the
// target is 5, the selection process works as follows:
//
// Start at 4 and try including 4 in the total the first loop.  We therefore have a tree with only
// one root node that is less than the total, so the next iteration occurs.  The second iteration
// examines a tree where 4 is the root and the left branch is 3.
//      o
//     /
//    4
//   /
//  3
//
// At this point, the total is determined to be 7 which exceeds the target of 5.  We therefore
// remove 3 from the left branch and it becomes the right branch since 3 is now excluded
// (backtrack).
//      o
//     /
//    4
//   / \
//      3
//
// We next try including 2 on the left branch of 3 (add 2 to the inclusion branch).
//      o
//     /
//    4
//   / \
//      3
//     /
//    2
//
// The sum is now 6, since the sum of the right branch totals 6.  Once again, we find the total
// exceeds 5, so we explore the exclusion branch of 2.
//      o
//     /
//    4
//   / \
//      3
//     / \
//        2
//
// Finally, we add 1 to the inclusion branch.  This ends our depth first search by matching two
// conditions, it is both the leaf node (end of the list) and matches our search criteria of
// matching 5.  Both 4 and 1 are on the left inclusion branch.  We therefore record our solution
// and backtrack to next try the exclusion branch of our root node 4.
//      o
//     / \
//    4
//   / \
//      3
//     / \
//        2
//       /
//      1
// 
// We try excluding 4 now
//      o
//     / \
//        4
//       / \
//      3
//
// 3 is less than our target, so we next add 2 to our inclusion branch
//      o
//     / \
//        4
//       / \
//      3
//     /
//    2
//
// We now stop our search again noticing that 3 and 2 equals our target as 5, and since this
// solution was found last, then [3, 2] overwrites the previously found solution [4, 1].  We next
// backtrack and exclude our root node of this sub tree 3.  Since our new sub tree starting at 2
// doesn't have enough value left to meet the target, we conclude our search at [3, 2].

cc @murchandamus @Tibo-lg

[yancyribbens]

closed by https://github.com/p2pderivatives/rust-bitcoin-coin-selection/pull/28

[yancyribbens]

@murchandamus I'm ready to cut a new release. I am wondering if you could check https://github.com/p2pderivatives/rust-bitcoin-coin-selection/pull/30 to make sure this closes the issue you opened. Thanks!

[yancyribbens]

closed by https://github.com/p2pderivatives/rust-bitcoin-coin-selection/pull/30