Scalable Operations Research for Transplant Exchange

This DARPA funded project is looking to improve the scalability and quality of Kidney Exchange Problem solution methods by incorporating graph neural network models into the solution process. Kidney exchange, also known as kidney transplant chain or paired donation, is a process in which two or more people who are unable to donate a kidney to their intended recipient due to incompatible blood types, antigens, or physical characteristics can still participate in kidney transplantation. This is made possible by finding another pair of incompatible donors and recipients who are willing to exchange kidneys.

The Kidney Exchange Problem (KEP) is a mathematical optimization problem that arises in the context of kidney transplantation. It involves finding a maximal matching of cycles of incompatible donors and recipients who are willing to exchange kidneys to facilitate transplantation. The goal is to maximize the number of transplants that can be performed by identifying the optimal kidney exchange cycles and chains to perform.

The kidney exchange problem is a complex optimization problem (NP-Hard) that is challenging due to the structure and the many variables and constraints. It has applications in the design of kidney exchange programs and has been the subject of extensive operations research and computer science research. Several algorithms and approaches have been proposed for solving the kidney exchange problem and are in use today, however many of these solutions fail to scale well to larger problem sizes. These approaches aim to find a match that maximizes the number of transplants while considering various constraints, such as blood and tissue compatibility, surgical feasibility, and ethical considerations such as the prioritization of hard to match recipients.

Our proposed research, termed Scalable Operations Research for Transplant Exchange (SORTE), is to investigate a hybrid approach to solve organ transplantation exchange problems. The hybrid technique will fuse three principal methodologies: Optimization, Machine Learning, and Meta-Heuristics. We term this approach HyLOS (Hybrid Learning-Optimization Solver). The hypothesis is that multiple managed algorithms aiding each other will not only provide better quality solutions for NP-Hard problems, but it will do so in a fraction of the time of current methods. Our approach will enable solving larger problems which could facilitate international exchange programs for example. The research team includes incoming mechanical and industrial engineering Ph.D. students Calvin Nau and Payam Khazaelpour as well as collaborators from the University of Buffalo: Dr. Moises Sudit and Dr. Liise Kayler and Roswell Park Comprehensive Cancer Center: Dr. Philip McCarthy.

The project or effort depicted was or is sponsored by the Defense Advanced Research Projects Agency. The content of the information does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred.