A Branch-Price-and-Cut Algorithm for the Kidney Exchange Problem

In this paper, we study a Kidney Exchange Problem (KEP) with altruistic donors and incompatible patient-donor pairs. Kidney exchanges can be modelled in a directed graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor. For medical reasons, circuits and paths are of limited length and are associated with a medical benefit to performing the transplants. The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality. Several solution methods are available in the literature to solve the KEP. However, they are usually most able to efficiently address instances with specific characteristics or of limited size. In this work, we propose an efficient method that stands out from the literature as it is able to report solutions of very good quality on large-size instances regardless of the characteristics (the type of objective function and the maximum length of circuits or paths). To do so, we consider a set-packing formulation for the KEP with exponentially many variables associated with circuits and paths, and develop a Branch-Price-and-Cut (BPC) algorithm to solve it. As a methodological contribution, the BPC algorithm features two novel heuristics to separate a well-known family of nonrobust inequalities, namely, the subset-row inequalities. The heuristics aim to detect such inequalities via an original transformation from violated clique and odd-hole inequalities. Extensive computational experiments have been performed on three sets of instances from the literature and on a newly generated set of challenging instances. On the easiest instances, the BPC algorithm yields results comparable with the literature, whereas on the other sets it clearly outperforms the previous approaches. History: Accepted by J. Paul Brooks, Area Editor for Applications in Biology, Medicine, and Healthcare. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0664 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0664 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .