(Algorithms)

Where exact debt settlement stops being practical

The bounded exact/greedy balance solver that sits beside CashFlow's newer obligation-clearing engine.

July 2026 · 3 min read

Money has to balance first

This note covers CashFlow's optional balance-settlement solver. The current obligation engine asks different questions: how much can cancel without new counterparties, how to certify that optimum, and which partial clearing leaves fewer parties unable to pay. None of those is the same as finding the fewest payments for an already reduced balance state.

The solver cannot repair bad accounting. With binary floating point, a balance that should be zero can end up as a collection of tiny residuals. I store every value as integer cents so equality and conservation checks stay exact at the stored currency precision.

After expenses are reduced, positive balances belong to creditors and negative balances to debtors. They must sum to zero. Every proposed payment moves value from one side to the other without changing that total.

const total = balances.reduce((sum, value) => sum + value, 0)
if (total !== 0) throw new Error("Balances must sum to zero")

// Values are integer cents: 1299 means 12.99 in the base currency.

Decide what ‘minimum’ means

A settlement could minimize the money moved, the number of payments, the largest payment, or some measure of fairness. For this balance-only solver, the target is the fewest payments. That is not the objective of CashFlow's separate maximum-circulation or rescue algorithms.

A greedy debtor-to-creditor match is quick and often good enough, but it can use more transactions than necessary. The exact path explores valid transfers, prunes equivalent states, and remembers the best remaining count.

Cap exact search at 12 balances

The search space grows combinatorially with the number of non-zero balances. I cap exact minimum-payment search at 12 rather than pretend it stays practical for groups of any size.

Remove zero balances before selecting a strategy.
Choose one unsettled participant and pair it with compatible opposite-sign balances.
Apply a transfer, recurse, then restore the previous state.
Memoize normalized balance states and prune branches that cannot beat the best plan.
Use stable participant ordering so equal inputs produce equal outputs.

function settle(balances) {
  const active = balances.filter(({ cents }) => cents !== 0)
  return active.length <= 12
    ? exactMinimumPayments(active)
    : deterministicGreedy(active)
}

Use a predictable fallback

Above the limit, the fallback repeatedly matches a debtor and creditor in a stable order. It settles every balance and returns the same plan for the same input, but it does not promise the global minimum.

That repeatability matters to both tests and users. Two people refreshing the same group should not get different recommendations just because a map or database returned its members in another order.

Why I keep WebAssembly optional

The repository includes a matching C++ implementation that compiles to WebAssembly. It supports runtime comparisons and parity tests, but changing languages does not change the combinatorial cost of exact search. The browser's current obligation-clearing comparison runs in TypeScript; it does not use this optional WASM solver.

The interface reports which strategy and runtime produced a plan. Both implementations have to satisfy the same accounting invariants.