Implement strategies for BnB.
MODIFY
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
WalletWasabi.Tests/UnitTests/Blockchain/TransactionBuilding/BranchAndBoundTests.cs
using System.Collections.Generic;
using System.Linq;
using WalletWasabi.Blockchain.TransactionBuilding;
+using WalletWasabi.Blockchain.TransactionBuilding.BnB;
using Xunit;
namespace WalletWasabi.Tests.UnitTests.Blockchain.TransactionBuilding;
@@ -13,13 +14,14 @@ public class BranchAndBoundTests
private static Random Random { get; } = new();
[Fact]
- public void RandomizedTest()
+ public void ExactMatch_RandomizedTest()
{
List<long> inputValues = GenerateListOfRandomValues();
- BranchAndBound selector = new(inputValues);
long target = 100_000_000;
- bool successful = selector.TryGetExactMatch(target, out List<long>? selectedValues);
+ BranchAndBound algorithm = new(inputValues);
+ ExactMatchStrategy strategy = new(target);
+ bool successful = algorithm.TryGetMatch(strategy, out List<long>? selectedValues);
Assert.True(successful);
Assert.NotNull(selectedValues);
@@ -27,14 +29,15 @@ public class BranchAndBoundTests
}
[Fact]
- public void SimpleSelectionTest()
+ public void ExactMatch_SimpleSelectionTest()
{
List<long> inputValues = new() { 120_000, 100_000, 100_000, 50_000, 40_000 };
- BranchAndBound selector = new(inputValues);
List<long> expectedValues = new() { 100_000, 50_000, 40_000 };
long target = 190_000;
- bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+ BranchAndBound algorithm = new(inputValues);
+ ExactMatchStrategy strategy = new(target);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.True(wasSuccessful);
Assert.NotNull(selectedCoins);
@@ -42,14 +45,15 @@ public class BranchAndBoundTests
}
[Fact]
- public void CanSelectEveryCoin()
+ public void ExactMatch_CanSelectEveryCoin()
{
List<long> inputValues = new() { 120_000, 100_000, 100_000 };
- BranchAndBound selector = new(inputValues);
List<long> expectedValues = new() { 120_000, 100_000, 100_000 };
long target = 320000;
- bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+ BranchAndBound algorithm = new(inputValues);
+ ExactMatchStrategy strategy = new(target);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.True(wasSuccessful);
Assert.NotNull(selectedCoins);
@@ -60,34 +64,52 @@ public class BranchAndBoundTests
/// Tests that sum of input values must be larger or equal to the target otherwise we end up searching all options in vain.
/// </summary>
[Fact]
- public void TargetIsBiggerThanBalance()
+ public void ExactMatch_TargetIsBiggerThanBalance()
{
- long target = 5_000;
List<long> inputValues = new();
+ long target = 5_000;
for (int i = 0; i < target - 1; i++)
{
inputValues.Add(1);
}
- BranchAndBound selector = new(inputValues);
- bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+ BranchAndBound algorithm = new(inputValues);
+ ExactMatchStrategy strategy = new(target);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
Assert.Null(selectedCoins);
}
[Fact]
- public void ReturnNullIfNoExactMatchFoundTest()
+ public void ExactMatch_ReturnNullIfNoExactMatchFoundTest()
{
List<long> inputValues = new() { 120_000, 100_000, 100_000, 50_000, 40_000 };
- BranchAndBound selector = new(inputValues);
long target = 300000;
- bool wasSuccessful = selector.TryGetExactMatch(target, out List<long>? selectedCoins);
+ BranchAndBound algorithm = new(inputValues);
+ ExactMatchStrategy strategy = new(target);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
+
+ Assert.False(wasSuccessful);
+ Assert.Null(selectedCoins);
+ }
+
+ /// <summary>Tests that best found solution is found when exact solution does not exist.</summary>
+ [Fact]
+ public void PruneByBest_NoExactSolution()
+ {
+ List<long> inputValues = new() { 2, 3, 5, 7, 11 }; // Sum is 28.
+ long target = 27; // Target that we cannot get as a sum of input values.
+
+ BranchAndBound algorithm = new(inputValues);
+ PruneByBestStrategy strategy = new(target);
+ bool wasSuccessful = algorithm.TryGetMatch(strategy, out List<long>? selectedCoins);
Assert.False(wasSuccessful);
Assert.Null(selectedCoins);
+ Assert.Equal(new long[] { 11, 7, 5, 3 }, strategy.GetBestSolution());
}
private List<long> GenerateListOfRandomValues(int count = 1000)

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/ExactMatchStrategy.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+public class ExactMatchStrategy : ISearchStrategy
+{
+ /// <inheritdoc/>
+ public long Target { get; }
+
+ public ExactMatchStrategy(long target)
+ {
+ Target = target;
+ }
+
+ /// <inheritdoc/>
+ public EvaluationResult Evaluate(long[] solution, int depth, long effValue)
+ {
+ if (effValue > Target)
+ {
+ // Excessive funds, cut the branch!
+ return EvaluationResult.SkipBranch;
+ }
+ else if (effValue == Target)
+ {
+ // Match found!
+ return EvaluationResult.Match;
+ }
+ else if (depth + 1 == solution.Length)
+ {
+ // Leaf reached, no match
+ return EvaluationResult.SkipBranch;
+ }
+
+ return EvaluationResult.Continue;
+ }
+}

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/ISearchStrategy.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+/// <summary>
+/// Search strategy for Branch and Bound algorithm.
+/// </summary>
+public interface ISearchStrategy
+{
+ /// <summary>Target value we want to, ideally, sum up from the input values.</summary>
+ long Target { get; }
+
+ /// <summary>
+ /// Evaluation function that evaluates each step of the Branch and Bound algorithm and
+ /// tells the algorithm what to do next.
+ /// </summary>
+ EvaluationResult Evaluate(long[] solution, int depth, long effValue);
+}
+
+public enum EvaluationResult
+{
+ /// <summary>Select a value to the selection and continue on.</summary>
+ Continue,
+
+ /// <summary>Omit a value from the selection.</summary>
+ SkipBranch,
+
+ /// <summary>Match was found!</summary>
+ Match
+}
\ No newline at end of file

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/PruneByBestStrategy.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+/// <summary>
+/// Strategy that stores the best solution found along the way and prunes
+/// search space where we would find worse solutions that we already have.
+/// </summary>
+public class PruneByBestStrategy : ISearchStrategy
+{
+ private long _bestTargetSoFar = long.MaxValue;
+ private long[]? _bestSolutionSoFar;
+
+ public PruneByBestStrategy(long target)
+ {
+ Target = target;
+ }
+
+ /// <inheritdoc/>
+ public long Target { get; }
+
+ public long[]? GetBestSolution() => _bestSolutionSoFar;
+
+ /// <inheritdoc/>
+ public EvaluationResult Evaluate(long[] solution, int depth, long effValue)
+ {
+ if (effValue > _bestTargetSoFar)
+ {
+ // Our solution is already better than what we might get here.
+ return EvaluationResult.SkipBranch;
+ }
+ else if (effValue >= Target)
+ {
+ if (_bestTargetSoFar > effValue)
+ {
+ _bestTargetSoFar = effValue;
+ _bestSolutionSoFar = solution[0..depth];
+ }
+
+ if (effValue > Target)
+ {
+ // Excessive funds, cut the branch!
+ return EvaluationResult.SkipBranch;
+ }
+ else
+ {
+ // Match found!
+ return EvaluationResult.Match;
+ }
+ }
+ else if (depth + 1 == solution.Length)
+ {
+ // Leaf reached, no match
+ return EvaluationResult.SkipBranch;
+ }
+
+ return EvaluationResult.Continue;
+ }
+}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
@@ -2,7 +2,8 @@ using NBitcoin;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
-using WalletWasabi.Logging;
+using System.Threading;
+using WalletWasabi.Blockchain.TransactionBuilding.BnB;
namespace WalletWasabi.Blockchain.TransactionBuilding;
@@ -10,10 +11,14 @@ namespace WalletWasabi.Blockchain.TransactionBuilding;
public class BranchAndBound
{
private readonly Random _random = new();
+ private readonly Func<bool> _randomFn;
/// <param name="values">All values must be strictly positive.</param>
- public BranchAndBound(List<long> values)
+ /// <param name="randomFn">Function returning randomly <c>true</c> and <c>false</c>.</param>
+ public BranchAndBound(List<long> values, Func<bool>? randomFn = null)
{
+ _randomFn = randomFn ??= () => _random.Next(0, 2) == 1;
+
if (values.Count == 0)
{
throw new ArgumentException("List is empty.");
@@ -55,19 +60,19 @@ public class BranchAndBound
/// <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>
+ /// <param name="searchStrategy">Search strategy that affects how the algorithm searches through the options.</param>
+ /// <param name="selectedValues">Solution of the search algorithm based on <paramref name="searchStrategy"/>.</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)
+ public bool TryGetMatch(ISearchStrategy searchStrategy, [NotNullWhen(true)] out List<long>? selectedValues, CancellationToken cancellationToken = default)
{
selectedValues = null;
- if (SortedValues.Sum() < target)
+ if (SortedValues.Sum() < searchStrategy.Target)
{
return false;
}
- if (TryFindSolution(target, out long[]? solution))
+ if (TryFindSolution(searchStrategy, out long[]? solution, cancellationToken))
{
selectedValues = new List<long>();
@@ -79,15 +84,13 @@ public class BranchAndBound
}
}
- Logger.LogInfo($"{Count} coins were involved in 'Branch and Bound' selection.");
-
return true;
}
return false;
}
- private bool TryFindSolution(long target, [NotNullWhen(true)] out long[]? solution)
+ private bool TryFindSolution(ISearchStrategy searchStrategy, [NotNullWhen(true)] out long[]? solution, CancellationToken cancellationToken = default)
{
// Current effective value.
long effValue = 0L;
@@ -99,8 +102,11 @@ public class BranchAndBound
NextAction[] actions = new NextAction[Count];
actions[0] = GetRandomNextAction();
+ int i = 0;
+
do
{
+ i++;
NextAction action = actions[depth];
// Branch WITH the value included.
@@ -111,21 +117,16 @@ public class BranchAndBound
solution[depth] = SortedValues[depth];
effValue += solution[depth];
- if (effValue > target)
+ EvaluationResult result = searchStrategy.Evaluate(solution, depth, effValue);
+
+ if (result == EvaluationResult.SkipBranch)
{
- // Excessive funds, cut the branch!
continue;
}
- else if (effValue == target)
+ else if (result == EvaluationResult.Match)
{
- // Match found!
return true;
}
- else if (depth + 1 == Count)
- {
- // Leaf reached, no match
- continue;
- }
depth++;
actions[depth] = GetRandomNextAction();
@@ -153,6 +154,12 @@ public class BranchAndBound
solution[depth] = 0;
depth--;
}
+
+ // Micro optimization: Do not check cancellation token every time as it requires accessing volatile memory.
+ if (i % 10_000 == 0 && cancellationToken.IsCancellationRequested)
+ {
+ return false;
+ }
}
while (depth >= 0);
@@ -161,7 +168,7 @@ public class BranchAndBound
private NextAction GetRandomNextAction()
{
- return _random.Next(0, 2) == 1 ? NextAction.IncludeFirstThenOmit : NextAction.OmitFirstThenInclude;
+ return _randomFn() ? NextAction.IncludeFirstThenOmit : NextAction.OmitFirstThenInclude;
}
private NextAction GetNextStep(NextAction action)

Implement strategies for BnB.