Optimization Online


Branch-and-cut-and-price for the Cardinality-constrained Multi-cycle Problem in Kidney Exchange

Edward Lam(edward.lam***at***monash.edu)
Vicky Mak-Hau(vicky.mak***at***deakin.edu.au)

Abstract: 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-donors pairs simultaneously donate kidneys in a cyclic manner enables all participants 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.

Keywords: kidney exchange, subtour, cycle, separation, pricing, column generation, facet, branch-and-cut-and-price

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Applications -- Science and Engineering (Biomedical Applications )

Citation: Monash University, September 2019

Download: [PDF]

Entry Submitted: 10/03/2019
Entry Accepted: 10/04/2019
Entry Last Modified: 10/03/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society