A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem
Preprint
Abstract
Kidney paired donation programs allow patients registered with an incompatible donor to receive a suitable kidney from another donor, as long as the latter's co-registered patient, if any, also receives a kidney from a different donor. The kidney exchange problem (KEP) aims to find an optimal collection of kidney exchanges taking the form of cycles and chains. Existing exact solution methods for KEP either are designed for the case where only cyclic exchanges are considered, or can handle long chains but are scalable as long as cycles are short. We develop the first decomposition method that is able to deal with long cycles and long chains for large realistic instances. More specifically, we propose a branch-and-price framework, in which the pricing problems are solved (for the first time in packing problems in a digraph) through multi-valued decision diagrams. Also, we present a new upper bound on the optimal value of KEP, stronger than the one proposed in the literature, which is obtained via our master problem. Computational experiments show superior performance of our method over the state of the art by optimally solving almost all instances in the PrefLib library for multiple cycle and chain lengths.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-priceMathematical Programming Computation, 2024
- Improved instance generation for kidney exchange programmesComputers & Operations Research, 2022
- A comparison of matching algorithms for kidney exchange programs addressing waiting timeCentral European Journal of Operations Research, 2020
- Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchangeComputers & Operations Research, 2020
- Maximizing the expected number of transplants in kidney exchange programs with branch-and-priceAnnals of Operations Research, 2017
- Maximising expectation of the number of transplants in kidney exchange programmesComputers & Operations Research, 2016
- On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approachesJournal of Combinatorial Optimization, 2015
- A New Branch-and-Price Approach for the Kidney Exchange Problem2014
- PrefLib: A Library for Preferences http://www.preflib.org2013
- Reducibility among Combinatorial Problems1972