Half-cycle: A new formulation for modelling kidney exchange problems

Maxence Delorme; David Manlove; Tom Smeets

doi:10.1016/j.orl.2023.02.009

Half-cycle: A new formulation for modelling kidney exchange problems

Maxence Delorme^*
, David Manlove
, Tom Smeets

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

3 Citations (Scopus)

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.

Original language	English
Pages (from-to)	234-241
Number of pages	8
Journal	Operations Research Letters
Volume	51
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2023.02.009
Publication status	Published - May 2023

Keywords

Cycle formulation
Integer programming
Kidney exchange
Preprocessing
Reduced-cost variable fixing

Access to Document

10.1016/j.orl.2023.02.009

Cite this

@article{29ed5df39e5243fcbc79f11d9637ec38,

title = "Half-cycle: A new formulation for modelling kidney exchange problems",

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.",

keywords = "Cycle formulation, Integer programming, Kidney exchange, Preprocessing, Reduced-cost variable fixing",

author = "Maxence Delorme and David Manlove and Tom Smeets",

note = "Funding Information: We would like to thank the anonymous reviewers for their valuable comments that have helped to improve the presentation of this paper. Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = may,

doi = "10.1016/j.orl.2023.02.009",

language = "English",

volume = "51",

pages = "234--241",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Half-cycle

T2 - A new formulation for modelling kidney exchange problems

AU - Delorme, Maxence

AU - Manlove, David

AU - Smeets, Tom

N1 - Funding Information: We would like to thank the anonymous reviewers for their valuable comments that have helped to improve the presentation of this paper. Publisher Copyright: © 2023 The Author(s)

PY - 2023/5

Y1 - 2023/5

N2 - 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.

AB - 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.

KW - Cycle formulation

KW - Integer programming

KW - Kidney exchange

KW - Preprocessing

KW - Reduced-cost variable fixing

UR - https://www.scopus.com/pages/publications/85150346378

U2 - 10.1016/j.orl.2023.02.009

DO - 10.1016/j.orl.2023.02.009

M3 - Article

AN - SCOPUS:85150346378

SN - 0167-6377

VL - 51

SP - 234

EP - 241

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Half-cycle: A new formulation for modelling kidney exchange problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this