Implement Branch and Bound algorithm.
ADD
WalletWasabi.Tests/UnitTests/BranchAndBoundTests.cs
+using NBitcoin;
+using System.Collections.Generic;
+using System.Linq;
+using WalletWasabi.BranchNBound;
+using Xunit;
+
+namespace WalletWasabi.Tests.UnitTests
+{
+ /// <summary>
+ /// Tests for <see cref="BranchAndBound"/> class.
+ /// </summary>
+ public class BranchAndBoundTests
+ {
+ private Random Random { get; } = new();
+
+ [Fact]
+ public void RandomizedTest()
+ {
+ List<long> inputValues = GenerateList();
+ BranchAndBound selector = new(inputValues);
+ long target = 100000000;
+
+ bool successful = selector.TryGetExactMatch(target, out List<long>? selectedValues);
+
+ Assert.True(successful);
+ Assert.NotNull(selectedValues);
+ Assert.Equal(target, selectedValues!.Sum());
+ }
+
+ [Fact]
+ public void SimpleSelectionTest()
+ {
+ List<long> inputValues = new() { 120000, 100000, 100000, 50000, 40000 };
+ BranchAndBound selector = new(inputValues);
+ List<long> expectedCoins = new() { 100000, 50000, 40000 };
+ long target = 190000;
+
+ bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+
+ Assert.True(wasSuccessful);
+ Assert.NotNull(selectedCoins);
+ Assert.Equal(expectedCoins, selectedCoins);
+ }
+
+ [Fact]
+ public void CanSelectEveryCoin()
+ {
+ List<long> inputValues = new() { 120000, 100000, 100000 };
+ BranchAndBound selector = new(inputValues);
+ List<long> expectedCoins = new() { 120000, 100000, 100000 };
+ long target = 320000;
+
+ bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+
+ Assert.True(wasSuccessful);
+ Assert.NotNull(selectedCoins);
+ Assert.Equal(expectedCoins, selectedCoins);
+ }
+
+ [Fact]
+ public void TargetIsBiggerThanBalance()
+ {
+ List<long> inputValues = GenerateList();
+ BranchAndBound selector = new(inputValues);
+ long target = 11111111111111111;
+
+ bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+
+ Assert.False(wasSuccessful);
+ Assert.Null(selectedCoins);
+ }
+
+ [Fact]
+ public void ReturnNullIfNoExactMatchFoundTest()
+ {
+ List<long> inputValues = new() { 120000, 100000, 100000, 50000, 40000 };
+ BranchAndBound selector = new(inputValues);
+ long target = 300000;
+
+ bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+
+ Assert.False(wasSuccessful);
+ Assert.Null(selectedCoins);
+ }
+
+ private List<long> GenerateList(int count = 1000)
+ {
+ List<long> values = new();
+
+ for (int i = 0; i < 1000; i++)
+ {
+ values.Add(Random.Next(1000, 99999999));
+ }
+ return values;
+ }
+ }
+}

ADD
WalletWasabi/BranchNBound/BranchAndBound.cs
+using NBitcoin;
+using System.Collections.Generic;
+using System.Diagnostics.CodeAnalysis;
+using System.Linq;
+using WalletWasabi.Logging;
+
+namespace WalletWasabi.BranchNBound
+{
+ public class BranchAndBound
+ {
+ private readonly Random _random = new();
+
+ public BranchAndBound(List<long> values)
+ {
+ Count = values.Count;
+ SortedValues = values.OrderByDescending(x => x).ToArray();
+ }
+
+ private enum NextAction
+ {
+ /// <summary>First try to include a coin and then try not to include the coin in the selection.</summary>
+ AandB,
+
+ /// <summary>First try NOT to include a coin and then try to include the coin in the selection.</summary>
+ BandA,
+
+ /// <summary>Include coin.</summary>
+ A,
+
+ /// <summary>Omit coin.</summary>
+ B,
+
+ /// <summary>Current selection is wrong, rolling back and trying different combination.</summary>
+ Backtrack
+ }
+
+ /// <remarks>Input values sorted in descending order.</remarks>
+ private long[] SortedValues { get; }
+
+ /// <summary>Number of input values.</summary>
+ private int Count { get; }
+
+ /// <summary>
+ /// Attempts to find a set of values that sum up to the target value.
+ /// </summary>
+ /// <param name="target">Target value we want to sum up from the input values.</param>
+ /// <param name="selectedValues">Values that sum up to the <paramref name="target"/> value.</param>
+ /// <returns><c>true</c> when a match is found, <c>false</c> otherwise.</returns>
+ public bool TryGetExactMatch(long target, [NotNullWhen(true)] out List<long>? selectedValues)
+ {
+ using (BenchmarkLogger.Measure())
+ {
+ if (SortedValues.Sum() < target)
+ {
+ selectedValues = null;
+ return false;
+ }
+
+ selectedValues = new List<long>();
+
+ try
+ {
+ if (Search(target, out long[]? solution))
+ {
+ for (int i = 0; i < Count; i++)
+ {
+ if (solution[i] > 0)
+ {
+ selectedValues.Add(SortedValues[i]);
+ }
+ }
+ Logger.LogInfo($"{Count} coins were involved in 'Branch and Bound' selection.");
+
+ return true;
+ }
+ selectedValues = null;
+ return false;
+ }
+ catch (Exception ex)
+ {
+ Logger.LogError("Couldn't find the right pair. ", ex);
+ return false;
+ }
+ }
+ }
+
+ private bool Search(long target, [NotNullWhen(true)] out long[]? solution)
+ {
+ // Current effective value.
+ long effValue = 0L;
+
+ // Current depth (think of the depth in the recursive algorithm sense).
+ int depth = 0;
+
+ solution = new long[Count];
+ NextAction[] actions = new NextAction[Count];
+ actions[0] = GetRandomNextAction();
+
+ do
+ {
+ NextAction action = actions[depth];
+
+ // Branch WITH the UTXO included.
+ if ((action == NextAction.AandB) || (action == NextAction.A))
+ {
+ actions[depth] = GetNextStep(action);
+
+ solution[depth] = SortedValues[depth];
+ effValue += solution[depth];
+
+ if (effValue > target)
+ {
+ // Excessive funds, cut the branch!
+ continue;
+ }
+ else if (effValue == target)
+ {
+ // Match found!
+ return true;
+ }
+ else if (depth + 1 == Count)
+ {
+ // Leaf reached, no match
+ continue;
+ }
+
+ depth++;
+ actions[depth] = GetRandomNextAction();
+ }
+ else if ((action == NextAction.BandA) || (action == NextAction.B))
+ {
+ actions[depth] = GetNextStep(action);
+
+ // Branch WITHOUT the UTXO included.
+ effValue -= solution[depth];
+ solution[depth] = 0;
+
+ if (depth + 1 == Count)
+ {
+ // Leaf reached, no match
+ continue;
+ }
+
+ depth++;
+ actions[depth] = GetRandomNextAction();
+ }
+ else
+ {
+ effValue -= solution[depth];
+ solution[depth] = 0;
+ depth--;
+ }
+ }
+ while (depth >= 0);
+
+ return false;
+ }
+
+ private NextAction GetRandomNextAction()
+ {
+ return _random.Next(0, 2) == 1 ? NextAction.AandB : NextAction.BandA;
+ }
+
+ private NextAction GetNextStep(NextAction action)
+ {
+ return action switch
+ {
+ NextAction.AandB => NextAction.B,
+ NextAction.BandA => NextAction.A,
+ NextAction.A => NextAction.Backtrack,
+ NextAction.B => NextAction.Backtrack,
+ NextAction.Backtrack => throw new InvalidOperationException("This should never happen."),
+ _ => throw new InvalidOperationException("No other values are valid.")
+ };
+ }
+ }
+}

Implement Branch and Bound algorithm.