Formulations and Algorithms for the Kidney Exchange Problem
Important advances in healthcare management by means of Operations Research techniques have been achieved over the past few years. One area in particular is in helping patients in need of a kidney reduce their usually long waiting times. One way to do this is through a kidney exchange program. If...
| Autor principal: | |
|---|---|
| Formato: | Tesis |
| Lenguaje: | Spanish / Castilian |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | http://eprints.uanl.mx/18121/2/tesisM_2017_Caro.pdf |
| _version_ | 1824415138500837376 |
|---|---|
| author | Riascos Álvarez, Lizeth Carolina |
| author_facet | Riascos Álvarez, Lizeth Carolina |
| author_sort | Riascos Álvarez, Lizeth Carolina |
| collection | Repositorio Institucional |
| description | Important advances in healthcare management by means of Operations Research techniques have been achieved over the past few years. One area in particular
is in helping patients in need of a kidney reduce their usually long waiting times.
One way to do this is through a kidney exchange program. If a patient needing a
kidney brings along a person (a relative or friend) willing to donate one of her/his
kidneys and if they both are clinically compatible then the donation can be done
immediately by mutual agreement. However, if this patient-donor pair (PDP) is not
compatible, an exchange with another PDP could take place. This could happen for
instance when the donor of one pair is compatible with the patient of another pair
and vice-versa. If such a pair is found, then they can agree to have a simultaneous
donation, have their kidney exchange surgeries relatively faster, avoiding the waiting
list. In some other cases, altruist donors, those without requiring a kidney in return,
may trigger a sequence of donations involving a series of incompatible PDPs. Now,
given a pool of PDPs with their compatibility information among pairs, finding the
largest amount of matches implies finding the largest amount of people that could
have their needed kidney surgeries in a timely fashion, rather than going to the
waiting list. Formally, the kidney exchange problem (KEP) is defined as finding the
largest amount of matches (either in form of cycles or chains) among a pool of PDPs.
In this thesis, we address the KEP by presenting and comparing a variety of existing
models and algorithms that cover almost all the kidney exchange variants known so
far. In particular, for one of the fundamental Kidney Exchange Problem formulations
encountered in the literature, a reduction method for substantially decreasing
the size of the problem is proposed. Moreover, we will set a natural partition on
the directed graph based on graph theory concepts in order to model reduced-size
instances, while keeping optimality. The proposed approach turns out to be very
effective to solve the KEP in terms of quality of solution and computational effort,
in many cases outperforming other KEP formulations. |
| format | Tesis |
| id | eprints-18121 |
| institution | UANL |
| language | Spanish / Castilian |
| publishDate | 2017 |
| record_format | eprints |
| spelling | eprints-181212020-08-19T18:12:47Z http://eprints.uanl.mx/18121/ Formulations and Algorithms for the Kidney Exchange Problem Riascos Álvarez, Lizeth Carolina Físico Matemáticas y Ciencias de la Tierra QA Matemáticas, Ciencias computacionales Important advances in healthcare management by means of Operations Research techniques have been achieved over the past few years. One area in particular is in helping patients in need of a kidney reduce their usually long waiting times. One way to do this is through a kidney exchange program. If a patient needing a kidney brings along a person (a relative or friend) willing to donate one of her/his kidneys and if they both are clinically compatible then the donation can be done immediately by mutual agreement. However, if this patient-donor pair (PDP) is not compatible, an exchange with another PDP could take place. This could happen for instance when the donor of one pair is compatible with the patient of another pair and vice-versa. If such a pair is found, then they can agree to have a simultaneous donation, have their kidney exchange surgeries relatively faster, avoiding the waiting list. In some other cases, altruist donors, those without requiring a kidney in return, may trigger a sequence of donations involving a series of incompatible PDPs. Now, given a pool of PDPs with their compatibility information among pairs, finding the largest amount of matches implies finding the largest amount of people that could have their needed kidney surgeries in a timely fashion, rather than going to the waiting list. Formally, the kidney exchange problem (KEP) is defined as finding the largest amount of matches (either in form of cycles or chains) among a pool of PDPs. In this thesis, we address the KEP by presenting and comparing a variety of existing models and algorithms that cover almost all the kidney exchange variants known so far. In particular, for one of the fundamental Kidney Exchange Problem formulations encountered in the literature, a reduction method for substantially decreasing the size of the problem is proposed. Moreover, we will set a natural partition on the directed graph based on graph theory concepts in order to model reduced-size instances, while keeping optimality. The proposed approach turns out to be very effective to solve the KEP in terms of quality of solution and computational effort, in many cases outperforming other KEP formulations. 2017-04-01 Tesis NonPeerReviewed text es cc_by_nc_nd http://eprints.uanl.mx/18121/2/tesisM_2017_Caro.pdf http://eprints.uanl.mx/18121/2.haspreviewThumbnailVersion/tesisM_2017_Caro.pdf Riascos Álvarez, Lizeth Carolina (2017) Formulations and Algorithms for the Kidney Exchange Problem. Maestría thesis, Universidad Autónoma de Nuevo León. |
| spellingShingle | Físico Matemáticas y Ciencias de la Tierra QA Matemáticas, Ciencias computacionales Riascos Álvarez, Lizeth Carolina Formulations and Algorithms for the Kidney Exchange Problem |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Formulations and Algorithms for the Kidney Exchange Problem |
| title_full | Formulations and Algorithms for the Kidney Exchange Problem |
| title_fullStr | Formulations and Algorithms for the Kidney Exchange Problem |
| title_full_unstemmed | Formulations and Algorithms for the Kidney Exchange Problem |
| title_short | Formulations and Algorithms for the Kidney Exchange Problem |
| title_sort | formulations and algorithms for the kidney exchange problem |
| topic | Físico Matemáticas y Ciencias de la Tierra QA Matemáticas, Ciencias computacionales |
| url | http://eprints.uanl.mx/18121/2/tesisM_2017_Caro.pdf |
| work_keys_str_mv | AT riascosalvarezlizethcarolina formulationsandalgorithmsforthekidneyexchangeproblem |