Optimizing kidney exchange programs with budget and time constraints

Abstract

End-stage renal disease a ects millions of people worldwide, with transplantation being the best form of treatment available. Most kidneys for transplants are obtained from deceased donors, but due to the increasing number of patients in need of a transplant, this supply has not been enough to meet the demand. This issue forced new transplantation strategies to emerge, namely obtaining kidneys from living donors. However, even when there is a willing living donor, in over 30% of the cases they are incompatible with the intended recipient of the transplant. Kidney Exchange Programs emerged to provide an alternative solution for patients with willing but incompatible donors, where two or more incompatible donor-patient pairs can nd a compatible transplant by swapping donors. A transplantation plan needs to be de ned in a pool of incompatible donor-patient pairs in order to decide which exchanges should take place. However, after the transplantation plan is de ned, more accurate compatibility tests are performed, possibly revealing new incompatibilities and leading to the cancellation of the plan. Furthermore, due to the complex logistics associated with these tests, there is also usually a time and budget limitation. In this dissertation we address the problem of deciding which tests to carry out in a pool of incompatible donor-patient pairs, taking into account probabilities of match failure, as well as budget and time constraints. We study three problems with varying degrees of limitation of resources in the context of Kidney Exchange Programs and present several methods for solving each one, based on Integer Programming.

A doença renal terminal afeta milhões de pessoas no mundo, sendo que a transplantação é o melhor tratamento disponível. A maioria dos rins para transplantes são obtidos de dadores cadavéricos, mas devido ao aumento do número de pacientes a necessitar de um transplante, esta oferta não é su ciente para responder à procura. Esta questão levou ao aparecimento de novas estratégias de transplantação, nomeadamente a obtenção de rins de dadores vivos. No entanto, mesmo quando existe um dador vivo disponível, em mais de 30% dos casos ele é siologicamente incompatível com o esperado recetor do transplante. Os Programas de Doação Renal Cruzada emergiram de forma a oferecer uma solução alternativa para pacientes com dadores vivos disponíveis, mas incompatíveis, onde dois ou mais pares incompatíveis de dadorrecetor podem encontrar um transplante compatível trocando de dador. Torna-se necessário de nir um plano de transplantação num conjunto de pares incompatíveis dador-recetor, de forma a decidir quais as trocas a efetuar. Contudo, após a de nição deste plano, são efetuados testes de compatibilidade mais precisos, podendo revelar novas incompatibilidades, levando ao cancelamento do plano. Além disso, devido à complexa logística associada a estes testes, existem também restrições a nível de tempo e de orçamento. Nesta dissertação, pretendemos responder ao problema de decidir quais os testes que devem ser efetuados dentro de um conjunto de pares incompatíveis dador-recetor, tendo em conta probabilidades de falha, bem como restrições de tempo e orçamento. Assim, estudamos três problemas com diferentes níveis de restrição destes recursos no contexto dos Programas de Doação Renal Cruzada e apresentamos vários métodos de resolução para cada um, baseados em Programação Inteira.