Deakin University
Browse

File(s) under permanent embargo

Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange

journal contribution
posted on 2020-03-01, 00:00 authored by E Lam, Vicky MakVicky Mak
The establishment of kidney exchange programs has dramatically improved rates for kidney transplants by matching donors to compatible patients who would otherwise fail to receive a kidney for transplant. Rather than simply swapping kidneys between two patient-donor pairs, having multiple patient-donor pairs simultaneously donate kidneys in a cyclic manner enables more patients to receive a kidney for transplant. For practicality reasons, the cycles must be limited to short lengths. Finding these cycles can be accomplished by solving the Cardinality-constrained Multi-cycle Problem, which generalizes the Prize-collecting Assignment Problem with constraints that bound the length of the subtours. This paper presents a series of additions to existing works—new constraints, some polyhedral results, new separation algorithms and a new pricing algorithm—and integrates them in the first branch-and-cut-and-price model of the problem. The model is shown to empirically outperform the state-of-the-art by solving 149 of 160 standard benchmarks, compared to 115 by the position-indexed chain-edge formulation and 114 by the position-indexed edge formulation.

History

Journal

Computers and Operations Research

Volume

115

Article number

ARTN 104852

Pagination

1 - 11

Location

Amsterdam, The Netherlands

ISSN

0305-0548

eISSN

1873-765X

Language

English

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2019, Elsevier

Publisher

PERGAMON-ELSEVIER SCIENCE LTD