Finding long chains in kidney exchange using the traveling salesman problem

Area of Science:

• Nephrology
• Transplantation Surgery
• Operations Research

Background:

• Over 100,000 patients were on deceased donor kidney transplant waiting lists by May 2014.
• The demand for kidney transplants significantly exceeds the supply of deceased donors annually.
• Kidney paired donation (KPD) offers a solution by facilitating exchanges between incompatible donor-recipient pairs.

Purpose of the Study:

• To address the limitations of existing algorithms in optimizing kidney exchanges within KPD programs.
• To develop novel computational methods for maximizing kidney transplants through KPD.
• To overcome the NP-hard nature of the kidney exchange optimization problem.

Main Methods:

• Developed two new algorithms utilizing integer programming techniques.
• One algorithm was inspired by methods used for the Traveling Salesman Problem.
• Applied these algorithms to optimally solve the kidney exchange problem.

Main Results:

• The new integer programming algorithms provide optimal solutions for kidney exchanges.
• These algorithms enable efficient searching over all possible long chains of exchanges.
• Demonstrated practical applicability for finding optimal solutions in KPD.

Conclusions:

• The developed algorithms offer a significant advancement in solving the kidney exchange optimization problem.
• These tools can enhance the efficiency and effectiveness of kidney paired donation programs.
• Improved KPD optimization can lead to an increased number of kidney transplants, benefiting patients on waiting lists.