We introduce the half-cycle formulation (HCF), a new integer programming (IP) model for the kidney exchange problem, which has life-saving applications. In HCF, a cycle (i.e., set of kidney swaps) is represented by two compatible halves. After giving several algorithmic enhancements for HCF, we show through extensive computational experiments with an IP solver that our new model outperforms existing formulations when the cycle size limit is set to 4, 5, or 6, depending on the density of the compatibility graph.
Delorme, M., Manlove, D., Smeets, T. (2023). Half-cycle: A new formulation for modelling kidney exchange problems. OPERATIONS RESEARCH LETTERS, 51(3), 234-241 [10.1016/j.orl.2023.02.009].
Half-cycle: A new formulation for modelling kidney exchange problems
Delorme M.
;
2023
Abstract
We introduce the half-cycle formulation (HCF), a new integer programming (IP) model for the kidney exchange problem, which has life-saving applications. In HCF, a cycle (i.e., set of kidney swaps) is represented by two compatible halves. After giving several algorithmic enhancements for HCF, we show through extensive computational experiments with an IP solver that our new model outperforms existing formulations when the cycle size limit is set to 4, 5, or 6, depending on the density of the compatibility graph.| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0167637723000329-main.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
397.66 kB
Formato
Adobe PDF
|
397.66 kB | Adobe PDF | Visualizza/Apri |
|
1-s2.0-S0167637723000329-mmc1.pdf
accesso aperto
Tipo:
File Supplementare
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
108.46 kB
Formato
Adobe PDF
|
108.46 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
