LowestFee: tighten the BnB bound when candidates have unconfirmed ancestors

[evanlinjin]

Background

Branch and bound (BnB) walks a tree of possible coin selections. At each node it asks the metric for a bound: the lowest score anything in this part of the tree could possibly reach. If that bound is already worse than the best answer found so far, the whole branch is skipped.

Two rules follow from that:

• A tighter (higher) bound prunes more, so the search is faster.
• A bound that is too high — above a score that really is reachable down that branch — makes BnB throw away the true best answer. Bounds must never do this. The word for "never too high" is admissible.

Current state (after #64)

When a problem has unconfirmed ancestors, LowestFee::bound gives up its tight reasoning and returns a plain floor:

fee_floor = max( rate·(child weight) + ancestor_bump_lower_bound,
                 absolute fee,
                 RBF minimum )

The rest is switched off, because the tight path leans on two assumptions that ancestors break:

1. "Selecting more never un-funds a selection." False — a coin can drag in an unconfirmed parent whose bump costs more than the coin is worth.
2. "A candidate costs its own weight." False — a coin sharing an already-paid-for ancestor is cheaper than it looks; a coin dragging its own unpaid chain is dearer.

Why it matters

Same candidates, ancestry declared vs not:

problem	rounds
n=14, no ancestry (tight path)	3304
n=14, with ancestry	6945
n=16, no ancestry (tight path)	8000
n=16, with ancestry	13769

Roughly 2× the work. Answers are correct, just slower. (Not perfectly controlled — the optima differ because ancestors genuinely cost more — so read it as a rough ceiling on the headroom.)

Plan

1. Marginal cost helper. Add "what would adding candidate i cost this selection right now?" = its own input weight priced at the target rate, plus the extra ancestor bump it brings given what is already dragged in. Cheap thanks to the private/shared split from #64: for privately reachable ancestors the delta is a fixed per-candidate pair; only shared ones need a lookup.

2. Value-shortfall relaxation. Rebuild the "resize" idea on marginal cost instead of raw value-per-weight: walk unselected candidates by best marginal value per marginal cost until funded, then allow a fractional slice of the last one. The ordering is only a heuristic once ancestors exist, so this step must never return None (see step 4).

3. Funded-node bound. Today a funded node's own score is not used, because a descendant can owe less (an ancestor that overpays nets against the deficit). Use score − maximum reachable surplus instead — the surplus figure already exists as ancestor_bump_lower_bound. Admissible, and much closer than the floor.

4. Leave the None prunes off unless proven. select_iter().find(is_funded)? returning None claims "nothing in this subtree can be funded". That is invalid when funding is not monotone, so it stays disabled.

Watch out

#56 reports that the existing resize relaxation is already inadmissible on master (the greedy prefix's segwit corrections inflate ideal_fee). Re-enabling it for ancestors must not inherit that bug. Fixing #56 first, or building step 2 on marginal costs, both sidestep it.

Done when

• The proptests in tests/ancestor.rs stay green: every bound ≤ every descendant score, None really means no solution in the subtree, and BnB == brute force. These catch exactly this class of mistake — three of them failed when the bound was deliberately made too tight.
• run_bnb_lowest_fee_ancestors/{private,shared}/{20,50,100} (benches added in feat!: ancestor-aware coin selection (CPFP bump via SelectionProblem) #64) drop, closing most of the ~2× gap. Rough target: within ~1.2× of the no-ancestor path.