Project name (60 char limit)
MatchCycle
Elevator pitch (200 char limit)
More transplants, fairer access. Exact cycle-packing for kidney paired donation: 22 transplants by greedy matching, 37 by integer programming — and it quantifies what prioritising equity costs.
(196 characters.)
About the project (Markdown, LaTeX supported)
## Inspiration
A patient needs a kidney. A friend or relative volunteers. The crossmatch comes
back incompatible — and both are stuck, even though a willing donor is standing
right there.
Kidney paired donation solves this by pooling those pairs so donors and
recipients can be swapped between them. It is also one of operations research's
genuine triumphs: Alvin Roth's Nobel citation covers the market design behind it.
But the underlying selection problem is NP-hard, and getting it wrong costs
transplants that were medically available.
I wanted to see exactly how many.
## What it does
MatchCycle generates a realistic donor pool, then compares four allocation
strategies on the same pool and reports the difference:
| Strategy | Transplants |
| --- | --- |
| Greedy pairwise matching | 22 |
| Optimal, cycles ≤ 2 | 24 |
| Optimal, cycles ≤ 3 | **32** |
| Optimal, cycles ≤ 3 + altruistic chains | **37** |
**+68% over greedy, on identical medical data.** The jump from 24 to 32 is the
interesting one: that is not better search over the same options, it is 3-cycles
unlocking exchanges no set of 2-cycles can reach.
It then answers a second question that volume-maximising allocation hides.
## The mechanism
Transplants happen in **cycles**. In a 2-cycle, A's donor gives to B's patient
and B's donor gives to A's. In a 3-cycle, A → B → C → A.
Cycles must be executed **simultaneously**, because a pair whose patient has
already received a kidney could otherwise withdraw before their donor gives. That
surgical constraint is why real programmes cap cycles at three.
**Altruistic donors** are different. They start a *chain* rather than a cycle, and
because every participant receives before their own donor gives, nobody can renege
mid-chain — so chains need no simultaneity and may run longer.
## Why greedy fails
O-type donors can give to anyone; O-type patients can only receive from O. So
pools accumulate **hard pairs** — an O patient with an A donor is nobody's easy
match. Pairwise matching stalls on exactly these, and a 3-cycle can break a
deadlock no pair of 2-cycles can.
## The model
Let $D=(V,A)$ be the compatibility digraph, $L$ the maximum cycle length, and $C$
the set of all cycles in $D$ of length at most $L$. With $x_c \in \{0,1\}$
indicating that cycle $c$ is selected:
$$\max \sum_{c \in C} w_c\, x_c \quad\text{subject to}\quad \sum_{c \in C:\, v \in c} x_c \le 1 \;\; \forall v \in V$$
The constraint says each pair takes part in at most one selected cycle: a donor
cannot give twice, a patient cannot receive twice. Setting $w_c = |c|$ maximises
transplants; a per-pair weight $p_v$ lets the objective encode priority.
Chains from altruistic donors are enumerated as paths and enter the same
disjointness constraints, plus a one-use constraint per donor.
This is **NP-hard for $L \ge 3$**, which is precisely why greedy leaves
transplants unrealised. Solved with CP-SAT over the cycle formulation.
## Compatibility is modelled, not random
Random edges would make the whole result meaningless, so compatibility follows the
actual medical constraints.
**ABO blood type.** O donates to anyone; A to A and AB; B to B and AB; AB to AB
only. Population frequencies O 45% / A 40% / B 11% / AB 4%.
**Virtual crossmatch.** Even with a compatible blood type, a recipient may carry
antibodies against the donor's HLA. Modelled with PRA — the probability a random
donor is incompatible — with 10% of patients "highly sensitised" above 80.
**And the selection effect that matters most:** a pair is admitted only if direct
donation would have *failed*. Real pools are enriched for hard cases, because the
easy pairs already transplanted directly and left. Generating the pool without that
filter produced a graph twice as dense and far easier than reality — the single most
important correction I made.
## The equity trade-off
Maximising total transplants **systematically skips highly sensitised patients**:
they have few compatible donors, and a volume-seeking solver routes around them. So
MatchCycle adds a priority bonus $\beta$ for patients with PRA ≥ 80, sweeps it, and
re-solves at every setting to trace the frontier:
- $\beta = 0$: **32** transplants, **5** to highly sensitised patients
- $\beta = 3$: **30** transplants, **8** to highly sensitised patients
**Prioritising the hardest-to-match costs 2 transplants and gains 3.** Equity here
is close to free — which is an argument for doing it, and it is the kind of question
a solver can answer that intuition cannot.
## How I built it
Python 3.11, OR-Tools CP-SAT, FastAPI, a single page with hand-written SVG. No
database, no authentication, and no language model anywhere — the allocation is a
deterministic integer program, so an identical seed gives an identical result.
Cycle enumeration is a depth-first search with canonical-rotation dedup, bounded by
start-vertex ordering. Chains are enumerated as paths, **prefixes included** — a
shorter chain is sometimes optimal because stopping early frees a vertex for a cycle
worth more, so pruning to maximal paths would forfeit optimality.
## Challenges
**Verifying the solver rather than trusting it.** I wrote a brute-force optimum over
all vertex-disjoint packings and asserted CP-SAT matches it across 30 seeded
instances. That test then caught something worse: OR-Tools was not installed in my
environment, an `ImportError` was being swallowed, and the test had been validating a
fallback solver while I believed it validated CP-SAT. A silent `except` hid the one
thing I most needed to know.
**A solver that reported zero instead of failing.** Chain enumeration grows as
roughly (out-degree)^length. On a dense pool it produced 610,000 variables, CP-SAT
exhausted its time limit, and the empty selection surfaced as "0 transplants" —
indistinguishable from a pool with no possible exchange. It now refuses to report a
result it cannot prove.
**Defaults tuned on the wrong machine.** A time limit that was comfortable on my
laptop was impossible on a 0.1-CPU instance, so the deployed app returned 500 on
every request. Fixing that exposed a second layer: the model still could not be
*proven* there, so it silently dropped chains and reported a lower figure than my own
documentation. A default tuned on the fastest machine in the loop is not a default.
## What I learned
Getting the *domain* right mattered more than getting the solver right. The solver
was correct early. What changed the results was realising that pairs who could
transplant directly never enter a pool — which made the instance sparser, harder,
more realistic, **and** the optimiser's advantage larger.
And that the interesting output of an optimisation model is often not the optimum.
"Equity costs two transplants" is a more useful sentence than "the answer is 37".
## What's next
Branch-and-price instead of full cycle enumeration, which is how national programmes
handle thousands of pairs. Failure-aware matching, since a meaningful fraction of
planned exchanges collapse at the final crossmatch. And a dynamic policy for *when*
to run a match, rather than assuming a static pool.
## Honest limitations
- The pool is **synthetic**, generated from published population statistics. No real
patient data, and nothing here is clinically validated.
- Independent crossmatch draws per donor simplify real HLA antibody correlation.
- Cycle enumeration is exact but does not scale to national registry sizes.
- The hosted instance is on a free tier, so the first request after idle may take
~50 seconds to wake.
Built with (tags, up to 25)
python
or-tools
cp-sat
constraint-programming
integer-programming
operations-research
fastapi
uvicorn
docker
render
svg
optimization
healthcare
market-design
"Try it out" links
https://matchcycle-orion.onrender.com
https://github.com/Abhinav0905/kidney-exchange
Image gallery (3:2 ratio, up to 15)
Screenshot these four, in order:
- Hero plus the strategy table showing all four rows — this is the headline
- The equity frontier chart with the descending curve
- The selected exchange network graph
pytestoutput — 14 passed — beside the brute-force test
Video demo link
YouTube URL, public, 3–5 minutes. Video - https://youtu.be/Xoevn5VgtLw URL - https://matchcycle-orion.onrender.com Code - https://github.com/Abhinav0905/kidney-exchange
Thumbnail
Use image 1. 3:2 ratio, under 5 MB.
Log in or sign up for Devpost to join the conversation.