2465. Refined ILP models for the kidney exchange problem with stability
Invited abstract in session MB-11: Kidney diseases and exchange, stream OR in Healthcare (ORAHS).
Monday, 10:30-12:00Room: Clarendon SR 1.03
Authors (first author is the speaker)
| 1. | Mathijs Barkel
|
| Department of Econometrics and Operations Research, Tilburg University | |
| 2. | Maxence Delorme
|
| Tilburg University | |
| 3. | David Manlove
|
| School of Computing Science, University of Glasgow |
Abstract
Kidney exchange programs allow patients with willing but incompatible donors to exchange their donors to obtain a compatible kidney. The Kidney Exchange Optimization Problem (KE-Opt) involves finding a matching of maximum size, i.e., a set of kidney exchanges involving cycles and chains that maximises the total number of transplants.
We consider the setting where recipients have ordinal preferences over their potential donors and where the objective is to find a maximum size stable matching, in which no exchange exists where all involved recipients prefer the donor in that exchange over their assigned one (if any). This problem is NP-hard, motivating the need for advanced methods.
To this end, we propose novel ILP models for KE-Opt with stability, building upon existing ones. We consider four previously defined types of stability, namely strong and weak stability, as well as strong and weak local stability.
Our models are based on existing cycle and chain models for KE-Opt, some of which had not been tested before in the setting with stability. Further contributions include preprocessing techniques, refined stability constraints and a constraint generation framework to effectively handle stability.
Additionally, we conduct extensive computational experiments on realistically generated instances to evaluate and compare the performance of our models against existing ones.
Keywords
- Programming, Integer
- Health Care
- Graphs and Networks
Status: accepted
Back to the list of papers