Kidney Exchange Optimization
OPTN/SRTR-based Integer Optimization Model
Introduction
Over 100,000 individuals in the US require a kidney transplant, but biological incompatibility remains a major hurdle.
Kidney exchange programs collect incompatible donor-patient pairs to find potential cross-matches. If donor1 is compatible with patient2 and vice versa, we can arrange an exchange.
Finding these exchanges manually is extremely time-consuming. Instead, we leverage Integer Optimization to maximize the number of transplants, increasing survival rates.
Altruistic Donor
While standard exchanges rely on mutual donor-patient pairs, we can also incorporate altruistic donors who donate without requiring a paired recipient.
We model this by creating a "dummy" patient for the altruistic donor. In our integer optimization formulation, this allows the donor to initiate non-directed exchange chains, effectively increasing the search space for potential matches and saving additional lives.
Results
Optimization Models
Our model improves as we add more constraints. The base model achieved 640 transplants, while adding altruistic donors saved 21 more lives (661 total).
Optimization Formulation
The objective is to maximize the weighted total of transplants across the network. The formulation incorporates:
- Maximum Match Flow: Maximizing the cardinality of the exchange.
- Cycle Constraints: Limiting the length of exchange chains (e.g., ) to manage surgical complexity and logistics.
- Biological Compatibility: Enforcing blood type and HLA cross-match constraints within the integer linear program.
- Altruistic Chaining: Utilizing non-directed donors to initiate non-simultaneous exchange chains.
Optimized Network Mapping
We visualized all matches across 1,000 donor-patient pairs and 20 centers. Each color represents a network of patients, donors, and transplant centers. The model successfully utilized high-capacity centers like MGH and Mayo Clinic.
