netmin

Settle a web of payment obligations in the fewest transfers, with a proof of optimality or an explicit gap.

The problem

Six subsidiaries owe each other money in a tangle: Paris owes London, London owes Berlin, Berlin owes Paris. Almost none of that money needs to move. The question is how few transfers actually clear the whole tangle — and it is worth asking, because every transfer costs a wire fee, an FX spread and a line someone has to reconcile at month end. The same question turns up in an expense-splitting app and in a corporate netting run, four orders of magnitude apart.

The usual answer pays the largest debtor into the largest creditor and repeats. It is fast, it often uses more transfers than necessary, and it cannot tell you how many more. Finding the true minimum is NP-hard, which is why most tools do not attempt it — and do not say that they are not attempting it.

netmin solves it exactly when the number of parties allows (up to about 24 with a nonzero position, in a fraction of a second). Above that it runs a fast heuristic and prints a proven lower bound beside it, so the worst-case gap is on the screen rather than assumed away.

It also handles the constraint that makes real netting runs different from the textbook problem: not every pair of parties is allowed to transfer to each other. Two subsidiaries may sit under legal entities that cannot move money between them, a currency may be under exchange control, or there may simply be no banking relationship. A plan that ignores that is a plan the treasury cannot execute.

How it works

Net positions. Obligations (payer, payee, amount) collapse to one signed position per party, in integer minor units (cents). Positive means the party is owed money. Floats are rejected everywhere; 12.34 in a CSV is parsed as the integer 1234.

The key identity. Split the n nonzero positions into groups that each sum to zero. A group of size s can always be settled with s - 1 transfers, and no plan does better, so

minimum transfers = n - (maximum number of disjoint zero-sum groups)

Exact solver: bitmask DP over subsets. With dp[mask] the most zero-sum groups a subset can be split into,

dp[mask] = max over i in mask of dp[mask without i]  +  (1 if sum[mask] == 0)

Evaluated one mask at a time in pure Python this takes about 0.8 s at n = 20. netmin evaluates the same recurrence one value at a time instead. Let U_v be the set of masks with dp >= v, stored as a single 2^n-bit Python integer, and Z the set of nonempty zero-sum masks. Then

U_{v+1} = up_closure(Z & one_step_up(U_v))

where both operators are n shift-and-mask operations on the big integer. Z itself is built by meet in the middle: subset sums of each half, then for each right-half sum the matching left-half masks are OR-ed in as a shifted block. The whole DP takes about 8 ms at n = 20 and 150 ms at n = 24 (benchmarks/bench.py prints the measured table). To rebuild the plan, netmin walks down from the full mask, removing one element at a time along a path that keeps the maximum. Each zero-sum mask it passes through closes a group.

Settling a group. Inside each group, the largest debtor pays the largest creditor. Every transfer zeroes at least one party and the last zeroes two, so a group of s takes at most s - 1 transfers (exactly s - 1, since optimal groups have no zero-sum subgroup). Money only moves from debtors to creditors, so gross volume equals the sum of all credits, which is the least any plan can move. Among plans with the fewest transfers, the exact plan therefore also has the smallest gross volume — a guarantee that blocked pairs, below, can cost.

Blocked pairs (src/netmin/constraints.py). When some pairs cannot transfer to each other, a zero-sum group of size s still settles in s - 1 transfers — but only if the allowed graph restricted to that group is connected. Take any spanning tree and peel it leaf by leaf: each leaf clears its whole position into its parent along one allowed edge, which is one transfer per tree edge.

The tempting shortcut is to filter Z down to the connected masks and reuse the DP above. That is wrong, and it is worth saying why. The fast recurrence credits a group whenever the running total hits zero while elements are peeled off, which is sound because a partition into zero-sum parts and a peeling whose prefixes sum to zero are the same thing. Connectivity is a property of the part, and a part there is the difference between two consecutive prefixes, not a prefix. So the parts have to be chosen directly:

f(mask) = 1 + max f(mask \ S)   over connected zero-sum S subset of mask

with S required to contain the lowest set bit, which reaches every partition exactly once. That recursion is only affordable because the candidate list is short, and it is short for a reason worth stating: distinct real amounts rarely sum to zero by accident. A 24-party run has a few dozen zero-sum subsets out of sixteen million, so the constrained solver is in practice faster than the unconstrained one, which pays for the full 2^n bitset regardless.

Two consequences the plan carries explicitly:

• Routing through an intermediary. If the debtor and creditor cannot pay each other directly, the money goes through a third party. The transfer count is still minimal, but gross volume can exceed the sum of credits, which is the floor without constraints.
• Funding order. A pass-through party must receive before it pays, or the treasury has to fund a party that is only passing money on. Money flows along a tree, so the flow graph is acyclic and a topological order always exists; the transfers are emitted in one.

If the allowed graph splits the parties into components that do not each net to zero, no plan of any length exists, and netmin says so rather than returning something unexecutable.

Heuristic for large n. (1) Cancel exact opposites {a, -a} with a hash map. (2) Find zero-sum triples: every such triple has two members of one sign, so scan same-sign pairs and look up the negated sum. (3) Settle whatever is left greedily, largest to largest.

Certificate. An upper bound on the group count gives a lower bound on transfers:

• every group needs a debtor and a creditor, so groups <= min(#debtors, #creditors);
• every group has at least 2 members. A 2-group is an opposite pair and a 3-group is a zero-sum triple; any other group has 4 or more. With g2 pairs (at most the maximum number of disjoint opposite pairs) and g3 triples (at most a third of the positions that belong to any zero-sum triple), n >= 2*g2 + 3*g3 + 4*(g - g2 - g3), so g <= (n + 2*g2 + g3) / 4.

The heuristic reports transfers, lower bound and gap = transfers - lower bound. A gap of 0 proves the plan optimal.

Worked example

examples/intercompany.csv has 8 obligations among 6 entities. They net to:

paris	london	berlin	madrid	rome	dublin
+1400.00	-900.00	+900.00	-800.00	-600.00	0

Greedy starts with the largest debtor (london, -900) and the largest creditor (paris, +1400). That breaks up both zero-sum groups, {london, berlin} and {paris, madrid, rome}, and greedy needs 4 transfers. The DP finds both groups, so 5 - 2 = 3 transfers. The bound also gives 3: there are 2 creditors, and the pair-and-triple size argument allows at most 2 groups.

Install and usage

Requires Python 3.9 or newer. There are no runtime dependencies.

From a checkout of this repository:

python -m venv .venv && . .venv/bin/activate
pip install -e ".[test]"

Plan a settlement (the input CSV has payer,payee,amount rows, and a header row is optional):

$ netmin plan examples/intercompany.csv
london -> berlin 900.00
madrid -> paris  800.00
rome   -> paris  600.00

parties:        6 (5 with a nonzero position)
method:         exact
transfers:      3
lower bound:    3
gap:            0 (optimal)
gross volume:   2300.00

The same input through plain greedy, for comparison:

$ netmin plan examples/intercompany.csv --method greedy
london -> paris  900.00
madrid -> berlin 800.00
rome   -> paris  500.00
rome   -> berlin 100.00

parties:        6 (5 with a nonzero position)
method:         greedy
transfers:      4
lower bound:    3
gap:            1 (not proven optimal)
gross volume:   2300.00

Pairs that cannot settle with each other

--blocked FILE takes a CSV of a,b rows. Paris and Milan sit under legal entities that cannot move money between them:

$ cat examples/blocked.csv
a,b
paris,milan

$ netmin plan examples/routed.csv | grep -v '^$'
paris -> milan  60.00
paris -> madrid 15.00
parties:        3 (3 with a nonzero position)
method:         exact
transfers:      2
lower bound:    2
gap:            0 (optimal)
gross volume:   75.00

$ netmin plan examples/routed.csv --blocked examples/blocked.csv | grep -v '^$'
paris  -> madrid 75.00
madrid -> milan  60.00
parties:        3 (3 with a nonzero position)
method:         exact
transfers:      2
lower bound:    2
gap:            0 (optimal)
gross volume:   135.00
blocked pairs:  1 (no transfer uses one)

Still two transfers, but the money now goes through Madrid, so gross volume rises from 75 to 135. Madrid is paid before it pays, so it never fronts the cash.

Measured over 90 instances of 14 parties (benchmarks/bench.py), that pattern holds generally — the transfer count is robust to blocks, the volume is not:

blocked pairs	extra transfers (mean)	extra transfers (worst)	gross volume vs unconstrained
1	0.00	0	1.07x
2	0.00	0	1.09x
4	0.01	1	1.27x
8	0.01	1	1.44x

Blocks only ever remove options, so the constrained answer is never below the unconstrained one. The solver refuses rather than guesses when --blocked is combined with a method that cannot honour it.

Above --exact-limit nonzero positions (default 20), auto switches to the heuristic:

$ netmin generate planted --parties 300 --seed 1 > big.csv
$ netmin plan big.csv | tail -6
parties:        300 (300 with a nonzero position)
method:         heuristic
transfers:      272
lower bound:    217
gap:            55 (not proven optimal)
gross volume:   888377674047.00

Other options: --method auto|exact|heuristic|greedy, --scale N for currencies with N decimal places (use 0 for JPY and 3 for KWD), and --json for machine-readable output. - reads from stdin. Bad input exits with status 2 and prints a line-numbered message, for example netmin: error: line 1: party 'a' cannot owe itself. python -m netmin works the same as netmin.

Generate seeded synthetic data with netmin generate {random,clustered,planted} --parties N --seed S [--groups K]:

• random: uniform random edges.
• clustered: dense obligations inside entity clusters and a few across them.
• planted: exactly K minimal zero-sum groups, hidden under chain obligations and zero-net cycles.

Library:

from netmin import net_positions, solve_exact, solve_heuristic, lower_bound, apply_transfers

positions = net_positions([("a", "b", 1250), ("b", "c", 1250)])   # integer cents
plan = solve_exact(positions)          # or solve_heuristic for any size
plan.transfers                         # [Transfer(payer='a', payee='c', amount=1250)]
plan.count, plan.lower_bound, plan.gap, plan.volume
assert set(apply_transfers(positions, plan.transfers).values()) == {0}
lower_bound(positions)                 # relaxation bound only

# Pairs that cannot transfer to each other. Order does not matter, and a pair
# naming a party with no position is ignored.
triangle = net_positions([("a", "b", 1000), ("b", "c", 400), ("c", "a", 250)])
solve_exact(triangle).transfers
# [Transfer('a', 'b', 600), Transfer('a', 'c', 150)]
solve_exact(triangle, blocked={("a", "b")}).transfers
# [Transfer('a', 'c', 750), Transfer('c', 'b', 600)]   -- same count, routed through c

solve_exact raises ObligationError when the blocks make settlement impossible, and netmin.violations(transfers, blocked) re-checks a plan from outside the solver.

Run the tests:

pytest

Results

Reproduce with one command (about a minute):

python benchmarks/bench.py

The run below used seed 0 and Python 3.14.6 on an Apple Silicon (arm64) Mac. Transfer counts are deterministic for a given seed. Runtimes depend on the machine. Each family has 1,000 instances with n cycling through 12..24 parties. "Excess" is transfers minus the exact optimum.

family	instances	greedy mean excess	greedy worst	greedy optimal	heuristic mean excess	heuristic worst	heuristic optimal	exact - lower bound (mean)
random	1000	0.022	1	97.8%	0.017	1	98.3%	3.05
clustered	1000	1.743	4	2.9%	1.725	4	3.1%	1.32
planted	1000	2.851	5	1.2%	1.850	4	6.4%	0.31

Exact solver runtime (full solve_exact, including plan reconstruction), by number of nonzero positions:

n	instances	mean ms	max ms
14	227	0.14	0.20
16	234	0.40	0.62
18	230	1.59	2.43
20	222	7.28	11.09
21	229	14.67	22.35
22	246	28.96	46.04
23	219	63.66	96.09
24	201	151.32	239.95

Runtime roughly doubles with each added party, as a 2^n table should. n = 24 is where a fraction of a second stops being one.

Blocked pairs, over 90 instances of 14 parties each:

blocked pairs	infeasible	extra transfers (mean)	extra transfers (worst)	gross volume vs unconstrained
1	0	0.00	0	1.07x
2	0	0.00	0	1.09x
4	0	0.01	1	1.27x
8	0	0.01	1	1.44x

At n = 1,000 (5 instances per family), the heuristic runs with the certified gap:

family	heuristic s	greedy transfers	heuristic transfers	lower bound	gap mean	gap worst
random	0.031	975.8	970.2	735.0	235.2	238
clustered	0.032	991.0	989.0	747.6	241.4	244
planted	0.035	997.4	897.0	716.4	180.6	186

What the numbers say:

• On random graphs, zero-sum structure almost never exists, so greedy is already optimal and the problem is easy.
• On clustered and planted graphs, greedy misses 1.7 to 2.9 transfers on average and up to 5.
• The heuristic helps where the hidden groups are pairs and triples, but not much where they are larger. For those, the exact solver is the tool.
• Blocked pairs almost never cost a transfer — the count is robust. What they cost is gross volume, up to 1.44x with eight blocked pairs, because the money has to go around. If the two quantities were equally expensive, this would be the wrong objective.
• At n = 1,000 the certified gap is wide (about 24% of n). The bound only rules out groups of size 2 and 3, so it cannot tell "no structure exists" from "structure exists but was not found".

Design notes

The most useful decision was to evaluate the subset DP over bitsets by dp value, not mask by mask. The recurrence is the textbook one. What changes is that dp never exceeds n/2, so the table can be stored as n/2 nested up-closed sets, and each set is a 2^n-bit integer that CPython shifts and ANDs in C. This gives about a 100x speedup over the loop in pure Python, with no NumPy and no C extension. The test suite keeps the one-mask-at-a-time DP as an oracle and checks both against brute-force enumeration of set partitions. The cost is memory: a few 2^n-bit integers live at once, which is why the exact limit defaults to 20 in the CLI and 24 in the library (both can be raised, at 2^n memory and time).

The second decision was to settle each group debtor-to-creditor instead of as a chain. A chain x1 -> x2 -> ... -> xs also uses s - 1 transfers, but it routes money through intermediaries and inflates gross volume. Settling each group greedily keeps the same count and moves exactly the sum of credits. That makes the secondary objective (least volume among plans with the fewest transfers) come for free and easy to check, and every unconstrained test asserts it. Blocked pairs are the case where it has to be given up: when the greedy routing inside a group would use a forbidden pair, netmin falls back to the spanning tree, keeps the transfer count, and lets the volume rise. The tests for that path assert a different, weaker contract, which is why they use their own helper rather than relaxing the main one.

Limitations

• Exact solving stops at about 24 nonzero positions. Above that you get the heuristic and a bound, not an optimum.
• The lower bound is weak on large unstructured inputs. It reasons only about groups of size 2 and 3, so on 1,000 random parties it proves about 735 transfers when the truth is probably close to 999. Adding feasibility for 4-sums (by hashing pair sums) would tighten it, but that is not implemented.
• The heuristic only looks for pairs and triples. Larger hidden groups are left to greedy. The triple scan is quadratic and is skipped above 8 million same-sign pairs (a few thousand parties). The bound stays valid in that case, only looser.
• One currency per run. Amounts are integers at a single --scale. netmin does not do FX, payment limits or fee-weighted objectives. Every transfer counts as 1.
• Blocked pairs need the exact solver. The heuristic and greedy paths do not honour them, so --blocked with either is refused rather than silently producing a plan that uses a forbidden pair. In practice that caps constrained runs at --exact-limit parties.
• A constrained plan minimises the count, not the volume. Without blocks the plan also moves the least money any plan can. With blocks, routing through an intermediary can move more — 1.07x to 1.44x in the measured table above, and unbounded in principle. If gross volume is what costs you rather than transfer count, this is the wrong objective.
• The constrained search assumes zero-sum subsets stay rare. That is what real amounts do, but an input built from small round numbers can have many, and the partition recursion is exponential in how many. It stops at MAX_PARTITION_STATES with a message rather than running forever.
• Planted instances are optimal with overwhelming probability, not by construction. Each group is checked to have no zero-sum subgroup, but a zero-sum set that mixes groups is only ruled out by drawing amounts from a range of 10^12.

License

MIT. See LICENSE.