Optimization Online


A new matheuristic and improved instance generation for kidney exchange programmes

Maxence Delorme(m.delorme***at***tilburguniversity.edu)
Sergio García(sergio.garcia-quiles***at***ed.ac.uk)
Jacek Gondzio(j.gondzio***at***ed.ac.uk)
Joerg Kalcsics(Joerg.Kalcsics***at***ed.ac.uk)
David Manlove(david.manlove***at***glasgow.ac.uk)
William Pettersson(william.pettersson***at***glasgow.ac.uk)
James Trimble(j.trimble.1***at***research.gla.ac.uk)

Abstract: Kidney exchange programmes increase the rate of living donor kidney transplants, and operations research techniques are vital to such programmes. These techniques, as well as changes to policy regarding kidney exchange programmes, are often tested using random instances created by a Saidman generator. We devise a new matheuristic that can optimally solve a benchmark set of Saidman instances in seconds: these instances have not been solved in under thirty minutes previously. This is possible as we take advantage of particular properties of these random instances that are noticeably different in real-world instances. We follow up this matheuristic with new techniques for generating random kidney exchange instances that are far more similar to real-world instances from the UK kidney exchange programme. This new process for generating random instances provides a more accurate base for comparisons of algorithms and models, and gives policy-makers a better understanding of potential changes to policy leading to an improved decision-making process.

Keywords: matheuristic, kidney exchange, saidman generator

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

Category 2: Combinatorial Optimization (Other )

Citation: Unpublished: Technical Report, University of Glasgow, May 2021

Download: [PDF]

Entry Submitted: 06/02/2021
Entry Accepted: 06/02/2021
Entry Last Modified: 06/02/2021

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