ChangePolicy should be decided by metrics in branch and bound

[LLFourn]

Right now we pass in a change policy when creating the metric type:

#[derive(Clone, Copy)]
pub struct LowestFee {
    /// The target parameters for the resultant selection.
    pub target: Target,
    /// The estimated feerate needed to spend our change output later.
    pub long_term_feerate: FeeRate,
    /// Policy to determine the change output (if any) of a given selection.
    pub change_policy: ChangePolicy,
}

But what if we pass in a really wacky change_policy that doesn't try and lower your fees? This means a whole lot of complicated logic is needed within the bound function of the metric to try and still get the correct bound with a ChangePolicy that is working against the metric!

This would allow us to remove this entire if/else statement:

coin-select/src/metrics/lowest_fee.rs

Lines 56 to 108 in 0f7cc31

	if let Some(drain_value) = drain_value {
	// it's possible that adding another input might reduce your long term fee if it
	// gets rid of an expensive change output. Our strategy is to take the lowest sat
	// per value candidate we have and use it as a benchmark. We imagine it has the
	// perfect value (but the same sats per weight unit) to get rid of the change output
	// by adding negative effective value (i.e. perfectly reducing excess to the point
	// where change wouldn't be added according to the policy).
	//
	// TODO: This metric could be tighter by being more complicated but this seems to be
	// good enough for now.
	let amount_above_change_threshold = drain_value - self.change_policy.min_value;
	if let Some((_, low_sats_per_wu_candidate)) = cs.unselected().next_back() {
	let ev = low_sats_per_wu_candidate.effective_value(self.target.fee.rate);
	// we can only reduce excess if ev is negative
	if ev < -0.0 {
	let value_per_negative_effective_value =
	low_sats_per_wu_candidate.value as f32 / ev.abs();
	// this is how much abosolute value we have to add to cancel out the excess
	let extra_value_needed_to_get_rid_of_change = amount_above_change_threshold
	as f32
	* value_per_negative_effective_value;
	// NOTE: the drain_value goes to fees if we get rid of it so it's part of
	// the cost of removing the change output
	let cost_of_getting_rid_of_change =
	extra_value_needed_to_get_rid_of_change + drain_value as f32;
	let cost_of_change = self
	.change_policy
	.drain_weights
	.waste(self.target.fee.rate, self.long_term_feerate);
	let best_score_without_change = Ordf32(
	current_score.0 + cost_of_getting_rid_of_change - cost_of_change,
	);
	if best_score_without_change < current_score {
	return Some(best_score_without_change);
	}
	}
	}
	} else {
	// Ok but maybe adding change could improve the metric?
	let cost_of_adding_change = self
	.change_policy
	.drain_weights
	.waste(self.target.fee.rate, self.long_term_feerate);
	let cost_of_no_change = cs.excess(self.target, Drain::none());
	let best_score_with_change =
	Ordf32(current_score.0 - cost_of_no_change as f32 + cost_of_adding_change);
	if best_score_with_change < current_score {
	return Some(best_score_with_change);
	}
	}

Can anyone think of a reason you'd want a change policy that is not inline with the metric you are trying to optimize for?

[jp1ac4]

I think this makes sense. The change output can be considered a part of the selection and therefore should only be included if it lowers the metric score.