EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1468. Half-Cycle: A new formulation for modelling kidney exchange problems
Invited abstract in session TD-10: Kidney Exchange II, stream OR in Health Services (ORAHS).
Tuesday, 14:30-16:00Room: 11 (building: 116)
Authors (first author is the speaker)
1. | David Manlove
|
School of Computing Science, University of Glasgow | |
2. | Mathijs Barkel
|
Department of Econometrics and Operations Research, Tilburg University | |
3. | Maxence Delorme
|
University of Bologna | |
4. | William Pettersson
|
University of Glasgow | |
5. | Tom Smeets
|
Tilburg University |
Abstract
A patient who requires a kidney transplant, and who has a willing but incompatible donor, may be able to 'swap' their donor with that of another patient, who is in a similar situation, in a cyclic fashion. Also, non-directed donors can trigger 'chains' of transplants involving multiple donor-recipient pairs. In this talk we introduce the Half-Cycle Formulation (HCF), an integer programming (IP) model for finding optimal sets of exchanges involving cycles and chains among incompatible donor-recipient pairs. In HCF, a cycle (i.e., set of kidney swaps) is represented by two compatible halves, and we also demonstrate how the model can be extended to incorporate chains. After giving several algorithmic enhancements for HCF, we show through computational experiments with an IP solver that our model is competitive in relation to other formulations for certain cycle and chain size limits.
Keywords
- Combinatorial Optimization
- Programming, Integer
- Health Care
Status: accepted
Back to the list of papers