# A Branch-Price-and-Cut algorithm for the Kidney Exchange Problem

Matteo Petris, Claudia Archetti, Diego Cattaruzza, Maxime Ogier, Frédéric Semet

► To cite this version:

Matteo Petris, Claudia Archetti, Diego Cattaruzza, Maxime Ogier, Frédéric Semet. A Branch-Price-and-Cut algorithm for the Kidney Exchange Problem. INFORMS Journal on Computing, 2025. hal-04475586v2

HAL Id: hal-04475586

https://inria.hal.science/hal-04475586v2

Submitted on 19 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Branch-Price-and-Cut Algorithm for the Kidney Exchange
Problem

Matteo Petris<sup>a,b,*</sup>, Claudia Archetti<sup>c</sup>, Diego Cattaruzza<sup>d,e</sup>, Maxime Ogier<sup>e</sup>, Frédéric Semet<sup>e</sup>

<sup>a</sup>Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

<sup>b</sup>CERMICS, ENPC, Institut Polytechnique de Paris, Marne-la-Vallée, France

<sup>c</sup>Department of Economics and Management, University of Brescia, Italy

<sup>d</sup>Department of Mathematics, Computer Science and Physics, University of Udine, Via delle Scienze 206,
33100 Udine, Italy

<sup>e</sup>Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

**Abstract**

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 perform 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 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 solution of very good quality on large-size instances regardless of the characteristics (the type of objective function, 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 algorithm (BPC) to solve it. As a methodological contribution, the BPC algorithm features two novel heuristics to separate a well-known family of non-robust inequalities, namely the subset-row inequalities.

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: matteo.petris@enpc.fr (Matteo Petris), claudia.archetti@unibs.it (Claudia Archetti), diego.cattaruzza@uniud.it (Diego Cattaruzza), maxime.ogier@centralelille.fr (Maxime Ogier), frederic.semet@centralelille.fr (Frédéric Semet)</footnote>
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 comparable results with the literature, while on the other sets it clearly outperforms the previous approaches.

# 1. Introduction

Kidneys are essential organs for the survival of the human body, but unfortunately, they may suffer from chronic diseases or failures which prevent them to perform their usual tasks.

Chronic kidney diseases or failures are often treated by dialysis or transplantation, the latter being the most preferable treatment: it affects less the quality of life of the patients, it offers a longer expectancy of life and it is more cost efficient (Yoo et al., 2016).

However, such operations have to be performed with extreme care in order to minimise the risk of rejection. For this reason, several medical requirements must be met for a patient and a donor to be considered eligible for a transplant. Precisely, patient and donor must be *compatible* according to several indicators such as blood type and presence of specific antibodies (Kälble et al., 2005). In addition, when different patients and donors are compatible between each other, each possible transplant is assigned with a *medical benefit* which quantifies the medical interest of performing the transplant.

Kidneys are harvested from either deceased or living donors. Usually, the former case constitutes the majority of the transplants. However, often a patient is capable of finding a willing donor with whom it is unfortunately not compatible. Together, they can form an *incompatible patient-donor pair* and join a *kidney exchange program* (Roth et al. (2004)). Such programs aim to determine the best (in terms of medical benefit) set of kidney exchanges in a pool of incompatible patient-donor pairs. An *exchange* takes place when a donor of a pair gives a kidney to a patient of another pair with whom he/she is compatible. For obvious reasons, in this context, a donor is willing to be in an exchange only if his/her
associated patient is guaranteed to receive a kidney as well. Hence, the set of exchanges to be determined must give rise to *cycles of donations*. The transplants associated with a cycle of donation are usually performed simultaneously to avoid the risk of donor withdrawals. Hence, for practical reasons (e.g., limited facilities or medical staff), regulations impose a maximal number of pairs in a cycle, usually set up to four (Biró et al., 2019).

25

In recent years, *altruistic donors*, i.e., donors who are not paired with any patient, may join the pool of a kidney exchange program (Roodnat et al., 2010). Thanks to their presence, the set of exchanges may also include *chains of donations* (domino donations) where the altruistic donors are at the start of the chains. In a chain of donation, surgeries are not required to be performed simultaneously, hence, the number of incompatible pairs involved in them is larger than the one of the cycles.

30

Typically, kidney exchange programs are run regularly (e.g., each one, three, or four months depending on the country regulation, Biró et al. (2021)) within one or more hospitals belonging to a single or different countries. At each round, an optimisation algorithm is called to solve the *Kidney Exchange Problem* (KEP) whose aim is to determine a set of cycles and chains of donations in the current pool of incompatible patient-donor pairs and altruistic donors such that the overall medical benefit is maximized.

35

In our work, we propose an exact approach to efficiently solve the KEP with both long cycles and chains and where the objective function is either the maximization of the medical benefit or the maximization of the number of transplants. We notice that this constitutes an advancement with respect to the current state-of-the-art on exact approaches for the KEP, as several exact solution algorithms have been proposed, but they are usually able to efficiently address instances with specific characteristics or of limited size. Precisely, we propose a *Branch-Price-and-Cut* (BPC) algorithm based on the *cycle formulation* for the KEP introduced by Roth et al. (2007), i.e., a *set-packing* formulation where the exponentially-many variables correspond to cycles and chains. Examples of efficient solution approaches based on column generation for set-packing (or set-covering) formulations include Lusby et al. (2011);

40

45
Pessoa et al. (2020). We exploit the theoretical results of Arslan et al. (2024) to solve as few as possible *Elementary Longest Path Problem with Length Constraints (ELPPLC)*s. However, instead of calling an integer program to solve the ELPPLC in the case of the chains, as done by Arslan et al. (2024), we make use of a labelling algorithm. Labelling algorithms are known to be more efficient than integer programs to solve ELPPLCs, and the set of resources to consider can be extended to manage the dual variables of non-robust inequalities. In this respect, we strengthen the linear relaxation of the formulation by including non-robust inequalities, namely the *subset-row* inequalities. The separation of these inequalities is an NP-complete problem Jepsen et al. (2008). Usually, in the literature, only small cardinality (less than or equal to five) subset-row inequalities are separated by enumeration (Pecin et al., 2017). However, given the size of the KEP instances, adopting such a procedure becomes intractable in terms of computational time. Hence, we propose two fast heuristics to separate them. These heuristics are based on the separation of the *clique* and *odd-hole* inequalities, respectively. Precisely, first, we separate the clique and odd-hole inequalities via two fast procedures from the literature and, then, we apply two original procedures to transform them into subset-row inequalities. In addition, we prove that each violated odd-hole inequality leads to a subset-row inequality with the same violation. We highlight that these separation heuristics are generic, i.e., they can be applied to separate the subset-row inequalities in the context of any formulation in which these inequalities are valid (typically set-packing or set-covering formulations). Moreover, they allow to quickly detect subset-row inequalities of different cardinality (even larger than five).

We identified in the literature three different sets of instances for the KEP, and we generated an additional set of instances. Each set has different characteristics, summarized in the following: (i) the PrefLib dataset contains instances with small cycles and chains and requires the maximization of the number of transplants (medical benefit set to value one) where Arslan et al. (2024) report the state-of-art results, (ii) the set of instances introduced by Pansart et al. (2022) with long chains, (iii) the set of instances introduced by Delorme
et al. (2023) with long cycles only, and (iv) the new set of instances generated via the well-established generator by Delorme et al. (2022) with long cycles and chains, requiring the maximization of the medical benefit. We decided to build the new set of instances as it encodes the characteristics of the most challenging problem version, i.e., long cycles and chains and the maximization of the medical benefit as objective. Such instances were not formerly available in the literature. Contrary to the solution approaches presented in the literature, our approach has the advantage of being able to efficiently solve all these sets of instances, and in particular the most difficult ones. Indeed, the solution approach of Arslan et al. (2024) struggles on instances with long chains and maximization of the medical benefit as it will be discussed in Section 5.2.2. The approach of Pansart et al. (2022) is a restricted master heuristic that provides lower and upper bounds by solving the root node of the branch-and-bound tree, but it does not perform branching. As a consequence, this approach is not able to prove optimality when branching is required, that is especially on the largest instances. The results in Delorme et al. (2023) show that their approach already struggles on instances with maximal length of the cycles equal to six and the maximization of the number of transplants, thus preventing it to efficiently scale on instances with long cycles/chains or the maximization of the medical benefit. Finally, the new set of instances is introduced as a benchmark of extremely challenging instances. For the above-mentioned reasons, the approaches by Arslan et al. (2024), Pansart et al. (2022) and (Delorme et al., 2023) are not promising to address such a set of instances. Hence, we compare the performance of the BPC algorithm against a well-established compact formulation for the KEP, namely the *hybrid position-indexed edge formulation* (HPIEF) by Dickerson et al. (2016).

The reminder of the paper is organised as follows. In Section 2, we review the existing literature regarding the KEP. In Section 3, we formally introduce the KEP and we present a set packing formulation for the problem. The main components of our Branch-Price-and-Cut algorithm are described in Section 4. In Section 5, we report and analyse the results obtained by the BPC algorithm on three sets of benchmark instances. Finally, Section 6
concludes the paper.

## 2. Literature review

Due to space limitation, in the following we mainly review formulations proposed for the KEP with an exponential number of variables w.r.t. the size of the instance. The interested reader may refer to Mak-Hau (2015) for a survey on formulations for the KEP up to 2015. We report that to the best of our knowledge the best-performing compact formulation for the KEP is the *hybrid position-indexed edge formulation* (HPIEF) proposed by Dickerson et al. (2016).

The first extended formulation, the *cycle formulation*, was introduced by Roth et al. (2007) and Abraham et al. (2007). As a solution method, they considered a column generation approach where the pricing problem is solved by enumeration. Later, Dickerson et al. (2016) introduced the *position-indexed chain-edge formulation* (PICEF) where cycles are modeled with exponentially-many variables and chains with polynomially-many variables and constraints. The authors show experimentally that when the size of the instances allow to enumerate the cycles, PICEF provides good results which are comparable with those of HPIEF.

Recently, Delorme et al. (2023) exploited the idea of representing a cycle by two compatible halves and introduced the *half-cycle formulation* to solve the KEP with cycles only and where the objective is to maximize the number of transplants. Such a formulation has fewer variables than the cycle formulation while keeping the same quality of the linear relaxation bound. The authors proposed to solve the formulation by enumerating all the possible half-cycles and by applying a destructive bound procedure coupled with a reduced cost variable-fixing strategy. Precisely, first, an upper bound on the maximum number of transplants is obtained by solving the linear relaxation of the formulation. By imposing such a bound as a solution value for the integer formulation, variables can be fixed to zero based on their reduced cost value in the linear relaxation. If an integer solution is found the
procedure stops, otherwise the solution value is decreased by one and the procedure repeats.

The motivation relies on the fact that the linear relaxation of such formulation provides tight bounds when maximizing the number of transplants. For the sake of comparison, they applied the same algorithmic framework to the *position-indexed edge formulation* (PIEF) by Dickerson et al. (2016), i.e., HPIEF where no chains are considered. They tested these two algorithms on instances with up to 1000 incompatible pairs and cycles of length up to eight. The results revealed that the half-cycle formulation performs better than the PIEF on instances with up to 600 incompatible pairs and cycles of length up to six, while the contrary happens on the remaining instances. All these formulations can be easily adapted to solve the KEP with altruistic donors and thus with chains. For example, Pansart et al. (2022) extended the cycle formulation to include the chains, as well.

For scalability reasons, several works focus on developing column generation approaches for the KEP. As already mentioned, Abraham et al. (2007) presented the first Branch-and-Price (BP) algorithm to solve the KEP with cycles only. The works of Glorie et al. (2012), Glorie et al. (2014), Klimentova et al. (2014) and Plaut et al. (2016) developed BP algorithms to solve the KEP with both cycles and chains. In addition, Dickerson et al. (2016) proposed a BP algorithm for the PICEF formulation where variables associated with the cycles are dynamically generated. However, from their experiments, solving the PICEF formulation with a commercial solver yielded better results than the BP algorithm. Based on the work of Klimentova et al. (2014), Lam and Mak-Hau (2020) built the first BPC algorithm for the KEP with cycles only. They tested the BPC algorithm on the 80 instances of the PrefLib dataset with 16 to 2048 pairs and without altruistic donors. The length of the cycles was limited to three or four. The BPC algorithm was able to solve all the instances when the length is limited to three and the majority of them when the length is limited to four. Pansart et al. (2022) is the first column generation approach capable of dealing with both cycles and chains. The objective is to maximize the total medical benefit. The authors proposed a restricted master heuristic: first, the linear relaxation of the extended
formulation is solved by column generation, then the formulation is restricted to the subset of variables found so far and solved with a commercial solver. Pansart et al. (2022) presented results on realistic instances with up to 1000 incompatible pairs, 111 altruistic donors, cycles of length up to three and chains with length up to 12. Precisely, their approach solved to optimality the majority of the instances with up to 250 pairs and shows its limits on the larger and most challenging instances which are left with an optimality gap.

The first work proposing a column generation approach which prices both variables associated with cycles and chains is Riascos-Álvarez et al. (2023). Their approach is tested on the instances of the PrefLib dataset with cycles of maximum length equal to three or four and chains of maximum length from three to six. The objective is the maximization of the number of transplants. The large majority of the instances are solved to optimality at the root node. The authors showed that the BP algorithm clearly outperforms both the PICEF and HPIEF formulations when solved with a commercial solver. However, their results are outperformed by the BP algorithm of Arslan et al. (2024). Precisely, the BP algorithm of Arslan et al. (2024) builds on the one of Riascos-Álvarez et al. (2023) by identifying theoretical conditions where also the pricing subproblems associated with the chain variables can be solved in polynomial time. Precisely, if the maximum length of the chains is less than or equal to the maximum length of the cycles plus one, proving that no more positive reduced cost chains exist can be done by relaxing the elementarity constraints. The authors model the pricing of both cycles and non-elementary chains as a LPPLC, that is solvable in polynomial time by a variant of the Bellman-Ford algorithm. However, to ensure the correctness of the algorithm, it might be necessary to solve an ELPPLC to prove that no elementary positive reduced cost chain still exists. Arslan et al. (2024) do so by modelling the ELPPLC as an integer program with an exponential number of constraints and propose to solve it by means of a branch-and-cut algorithm. As Riascos-Álvarez et al. (2023), they tested their approach on the instances of the PrefLib dataset. All the instances are solved to optimality in less than 20 seconds and the integer program to solve the ELPPLC is almost
never required. For the sake of a fair comparison, Arslan et al. (2024) implemented a BP algorithm for the PICEF formulation where the cycle variables are priced with the same strategy as in their BP algorithm. The results again showed that the BP algorithm based on the PICEF formulation is outperformed.

185

The BPC algorithm we propose in this work exploits the preprocessing of Riascos-Álvarez et al. (2023) to reduce the number of the pricing subproblems associated with the cycles and the interesting properties of Arslan et al. (2024) to solve the pricing subproblems associated with the chains in polynomial time under some conditions. The contribution of our method are the inclusion of valid inequalities to strengthen the formulation and the use of a labelling algorithm to efficiently solve the ELPPLC instead of to the integer program used by Arslan et al. (2024).

190

Our approach is then able to solve more difficult instances with long chains and cycles and where the objective is the maximization of the total medical benefit. Thus, it can be considered as a generic approach capable of handling all instances and problem settings presented in the former literature.

195

### 3. Problem formulation

Let $\mathcal{I}$ be the set of incompatible patient-donor pairs and let $\mathcal{D}$ be the set of altruistic donors. The KEP can be defined on a directed weighted graph $\mathcal{G} = (\mathcal{V}, \mathcal{A})$ referred to as *compatibility graph*. Vertex set $\mathcal{V} = \mathcal{I} \cup \mathcal{D}$ contains a vertex for each incompatible patient-donor pair of $\mathcal{I}$ and each altruistic donor of $\mathcal{D}$. The arcs in $\mathcal{A}$ model all the possible transplants between donors and patients. Hence, arc set $\mathcal{A}$ contains an arc $(i, j)$ from vertex $i \in \mathcal{V}$ to patient-donor pair $j \in \mathcal{I}$, if the kidney of the donor associated with $i$ is compatible with the patient of pair $j$. We assign a weight $W_{ij}$ to each arc $(i, j) \in \mathcal{A}$ representing the utility (medical benefit) of the associated transplant. Cycles and chains of kidney exchanges between donors and patients are modelled in graph $\mathcal{G}$ by two types of subgraphs, namely circuits and paths. The length of a cycle or a chain is equal to the number of arcs in the

200

205
circuit or path. In this respect, we call an *exchange circuit* an elementary circuit in graph $\mathcal{G}$ of length at most $L^C > 1$. Similarly, we call an *exchange path* an elementary path in graph $\mathcal{G}$ of length at most $L^P > 1$, starting with a vertex in $\mathcal{D}$. Given that vertices associated with altruistic donors do not have in-going arcs, exchange circuits are composed only of vertices associated with patient-donor pairs. Given an exchange circuit or path $e$, the weight $W_e$ of $e$ is defined as the sum of the weights of the arcs traversed by $e$, i.e., $W_e := \sum_{(i,j) \in \mathcal{A}(e)} W_{ij}$, where $\mathcal{A}(e)$ is the set of arcs traversed by $e$. Finally, we define an *exchange scheme* as a union of pairwise vertex-disjoint exchange circuits and paths. The KEP aims to determine an exchange scheme of maximum weight, where the weight of an exchange scheme is the sum of the weights of the exchange circuits and paths composing it. An exchange scheme may not contain all the vertices of $\mathcal{V}$. We remark that if all weights $W_{ij}$, $(i, j) \in \mathcal{A}$, are set to one, the objective of the KEP is to maximize the number of transplants. The KEP with cycles of length larger than two (and chains of arbitrary length) is proven to be NP-hard (Roth et al., 2007; Abraham et al., 2007). In what follows, with an abuse of language, we refer to an exchange circuit or path with the term “exchange”. Example 1 reports a toy example of the KEP.

**Example 1.** We consider the following toy instance of the KEP. The compatibility graph $\mathcal{G} = (\mathcal{V}, \mathcal{A})$ is shown in Figure 1. Vertex set $\mathcal{V} = \mathcal{I} \cup \mathcal{D}$ is composed of two altruistic donors $\mathcal{D} = \{1, 2\}$ and seven patient-donor pairs $\mathcal{I} = \{3, 4, 5, 6, 7, 8, 9\}$. The weights on the arcs are reported in the figure. The maximal length of the circuits and paths are set to $L^C = 3$ and $L^P = 4$, respectively. The optimal value of the KEP on this toy instance is 335 and is attained with an optimal solution composed of two paths, (1, 3, 5) and (2, 8, 4), and one cycle (6, 7, 6). Note that the maximization of the medical benefit favours quality over quantity, indeed, patient-donor pair 9 is not served.

Conversely, if the weights on the arcs are all set to one, the optimal value is seven and an optimal solution to attain it is: (1, 3), (2, 8, 9, 6) and (4, 5, 7, 4). In this case, all the patient-donor pairs are served.
<figure><img src="image_2.png" /><figcaption>Figure 1: Compatibility graph of the toy instance of the KEP defined in Example 1.</figcaption></figure>

We denote by $\mathcal{E} = \mathcal{E}^C \cup \mathcal{E}^P$ the set of the exchanges in graph $\mathcal{G}$, where $\mathcal{E}^C$ ($\mathcal{E}^P$) denotes the set of the exchange circuits (paths) in graph $\mathcal{G}$. Let $a_i^e$ be a binary parameter equal to one if vertex $i \in \mathcal{V}$ is involved in exchange $e \in \mathcal{E}$ and zero otherwise. For each exchange $e \in \mathcal{E}$, we define a binary variable $\lambda_e$ taking value one if exchange $e$ is part of the exchange scheme and zero otherwise.

The Set Packing formulation [SP] for the KEP reads as follows (Pansart et al. (2022)):

$$ [\text{SP}] \quad \max \sum_{e \in \mathcal{E}} W_e \lambda_e \qquad (1) $$

$$ \text{s.t.} \quad \sum_{e \in \mathcal{E}} a_i^e \lambda_e \le 1 \qquad \forall i \in \mathcal{V} \qquad (2) $$

$$ \sum_{e \in \mathcal{E}} \lambda_e \le \frac{|\mathcal{V}|}{2} \qquad (3) $$

$$ \lambda_e \in \{0, 1\} \qquad \forall e \in \mathcal{E}. \qquad (4) $$

Objective function (1) maximizes the weight of the exchange scheme. Constraints (2) referred to as packing constraints ensure that each incompatible pair and altruistic donor is involved in at most one exchange circuit or path. Constraint (3) imposes an upper bound on the number of the exchanges in an exchange scheme. We remark that such constraint is redundant, indeed, each exchange circuit or path cannot be composed of less than two vertices. We include it in the formulation to compute a valid upper bound in the column generation procedure, namely the Lagrangian bound. Such a bound may be used as a
termination condition in the column generation procedure. Finally, Constraints (4) define
variables $\lambda_e$ as binary.

Valid inequalities to strengthen formulation [SP] are presented in Section 4.4.

## 4. A Branch-Price-and-Cut algorithm

Formulation [SP] is an integer model defined over exponentially-many variables $\lambda_e$, $e \in E$.
We solve [SP] by means of an exact algorithm based on the Branch-Price-and-Cut (BPC)
paradigm (Barnhart et al., 1998). BPC algorithms are variants of the branch-and-bound
algorithm where, at each node of the branch-and-bound tree, the linear relaxation of [SP]
is solved via a column generation procedure. The linear relaxation of [SP] is commonly
referred to as the Master Problem (MP). If the solution of the MP is fractional, a separation
procedure may be called to identify violated valid inequalities (see Section 4.4). If such
inequalities are found, they are included in the MP and the column generation procedure
is repeated. Finally, when no violated valid inequalities are detected, branching rules are
applied to ensure the correctness of the BPC algorithm.

Section 4.1 is devoted to the column generation procedure we employ in our BPC algo-
rithm. In Sections 4.2 and 4.3, we formulate the pricing problem and we present an exact
procedure to solve it. In Section 4.4, we present the family of valid inequalities and the
cut generation strategy. The branching strategies are discussed in Section 4.5. Finally,
in Appendix C, we present the accelerating techniques we embed in the BPC algorithm.

### 4.1. Column generation

The MP is solved by means of a column generation procedure at each node of the branch-and-bound tree. The Restricted Master Problem (RMP) denotes the MP restricted to a subset of the $\lambda$ variables. Then, each iteration of the procedure comprises two consecutive steps: (i) solve the RMP to get the dual values associated with the constraints, and (ii) solve the so-called *pricing problem* to detect the most positive reduced cost variables (columns) that are added to the RMP. Note that the pricing problem searches for positive reduced cost
variables because the RMP is a maximization problem. When the pricing problem proves that no positive reduced cost variables exist, the current solution of the RMP is proven to be optimal for the MP, as well. Note that if the pricing problem reports some positive reduced cost variables without proving they are the most positive, the column generation procedure is still valid.

## 4.2. Pricing problem formulation

Let $\pi_i \ge 0, i \in \mathcal{V}$ and $\beta \ge 0$ be the dual prices associated with Constraints (2) and (3) in the RMP, respectively. The reduced cost of a $\lambda_e$ variable is: $\bar{W}_e = W_e - \sum_{i \in \mathcal{V}} a_i^e \pi_i - \beta$. The pricing problem reads as follows: [PP] $\max\{\bar{W}_e : e \in \mathcal{E}\}$. We observe that exchange set $\mathcal{E}$ can be partitioned as: $\mathcal{E} = \mathcal{E}^C \cup \mathcal{E}^P = \cup_{i \in \mathcal{I}} \mathcal{E}_i^C \cup \mathcal{E}^P$, where $\mathcal{E}_i^C$ is the set of the exchange circuits starting and ending at incompatible pair $i \in \mathcal{I}$. Hence, pricing problem [PP] can be decomposed in $|\mathcal{I}| + 1$ independent subproblems:

$$ [\text{PP-C}](i) \max\{\bar{W}_e : e \in \mathcal{E}_i^C\} \quad i \in \mathcal{I} $$

and

$$ [\text{PP-P}] \max\{\bar{W}_e : e \in \mathcal{E}^P\}. $$

The aim of problem [PP-C](i) is to determine the most positive reduced cost variable $\lambda_e$, $e \in \mathcal{E}_i^C$, associated with exchange circuits starting and ending in $i \in \mathcal{I}$ or state that no positive reduced cost variable exists. Similarly, the aim of problem [PP-P] is to determine the most positive reduced cost exchange path variable $\lambda_e$, $e \in \mathcal{E}^P$ or state that no positive reduced cost variable exists.

In the following, we show that problems [PP-C](i), $i \in \mathcal{I}$, and [PP-P] share the same structure: they can be formulated as an *Elementary Longest Path Problem with Length Constraint* (ELPPLC).

First, we formally define the ELPPLC having as a reference Pansart et al. (2022). Let $\mathcal{H} = (\mathcal{N}, \mathcal{F})$ be a directed weighted graph, where the weights associated with the arcs
(i, j) ∈ 𝒯 are denoted by $\bar{W}_{ij}$. The objective of the ELPPLC is to find the longest elementary path $e^*$ in graph $\mathcal{H}$ starting at a given vertex $s \in \mathcal{N}$, ending at a given vertex $t \in \mathcal{N}$ and such that its length is less than or equal to $\bar{L} > 0$ and where *longest* means that its weight $\bar{W}_{e^*} = \sum_{(i,j) \in \mathcal{A}(e^*)} \bar{W}_{ij}$ is maximum. The ELPPLC is a variant of the *Elementary Shortest Path Problem with Resource Constraints* (ESPPRC). Indeed, it suffices to consider the length of a path as a resource and to convert the ELPPLC as a minimization problem by assigning to each arc (i, j) of the graph the weight $-\bar{W}_{ij}$. By doing so, the ELPPLC corresponds to the ESPPRC where *shortest* has to be intended in terms of arc weights. Such a correspondence implies that the ELPPLC is NP-hard in the strong sense (see Dror (1994)).

Now, we describe the topology of the graph $\mathcal{H}$ arising when pricing circuits and paths.

Let $i \in \mathcal{I}$ be an incompatible patient-donor pair. To model [PP-C](i) as an ELPPLC, we define a directed weighted graph $\mathcal{H}_i^C = (\mathcal{N}_i^C, \mathcal{F}_i^C)$ as follows. The vertices of $\mathcal{H}_i^C$ are the incompatible pairs of $\mathcal{I}$ plus a copy $i'$ of pair $i$, i.e., $\mathcal{N}_i^C := \mathcal{I} \cup \{i'\}$. The arcs set of $\mathcal{H}_i^C$ is $\mathcal{F}_i^C = \{(h, j) \in \mathcal{A} : h, j \in \mathcal{I}, j \neq i\} \cup \{(j, i') : (j, i) \in \mathcal{A}\}$ that is $\mathcal{F}_i^C$ contains the arcs of compatibility graph $\mathcal{G}$ between the incompatible pairs, except those entering in pair $i$ and for all arcs $(j, i) \in \mathcal{A}$ entering in $i$, we add an arc $(j, i')$ entering in the copy $i'$ of $i$.

We remark that circuits in graph $\mathcal{G}$ starting and ending in $i$ correspond to paths in graph $\mathcal{H}_i^C$ starting in $i$ and ending in $i'$. Weights $\bar{W}_{hj}$ assigned to arcs $(h, j) \in \mathcal{F}$ are defined as follows

$$ \bar{W}_{hj} = \begin{cases} W_{ij} - \pi_j - \beta, & \text{if } h = i; \\ W_{hi} - \pi_i, & \text{if } j = i'; \\ W_{hj} - \pi_j, & \text{otherwise.} \end{cases} \qquad (5) $$

To consider the path length, we define a resource consumption $L_{hj} = 1$ for each arc $(h, j) \in \mathcal{F}$. Then, problem [PP-C](i) is equivalent to finding the longest elementary path starting at $i$ and ending at $i'$ in graph $\mathcal{H}_i^C$ such that the length of the path is less than or equal to $L^C$.

We model [PP-P] as an ELPPLC on graph $\mathcal{H}^P = (\mathcal{N}^P, \mathcal{F}^P)$ defined as compatibility graph $\mathcal{G}$ augmented with source vertex $s$ and an arc from $s$ to each altruistic donor of $\mathcal{D}$.
Precisely, we set $\mathcal{N}^P := \{s\} \cup \mathcal{V}$ and $\mathcal{F}^P = \mathcal{A} \cup \{(s, i) : i \in \mathcal{D}\}$. Given an arc $(i, j) \in \mathcal{F}^P$, its weight $\bar{W}_{ij}$ is defined as follows

$$ \bar{W}_{ij} = \begin{cases} W_{ij} - \pi_j - \beta, & \text{if } i = s; \\ W_{ij} - \pi_j, & \text{otherwise.} \end{cases} \qquad (6) $$

Resource consumption $L_{ij}$ is set to be one on all arcs $(i, j) \in \mathcal{F}^P$. Then, problem [PP-P] is equivalent to finding the longest elementary path starting at $s \in \mathcal{N}$ and ending in any vertex $j \in \mathcal{N}^P \setminus \{s\}$ in graph $\mathcal{H}^P$ such that the length of the path is less than or equal to $L^P + 1$. We remark that to be consistent with the definition of exchange paths given in Section 3, here, [PP-P] looks for paths of length at most $L^P + 1$. Indeed, in the underlying graph $\mathcal{H}^P$ used to solve [PP-P], we add a source vertex $s$ which is not included in the compatibility graph $\mathcal{G}$.

In Appendix A, we report two theoretical results which identify conditions under which subproblems [PP-C](i), $i \in \mathcal{I}$, and [PP-P] can be formulated as *Longest Path Problems with Length Constraint* (LPPLC), i.e., the elementarity constraint can be removed (see, e.g., Arslan et al., 2024). The interest of these two results stems from the following remark. The LPPLC is a variant of the *Shortest Path Problem with Resource Constraints* (SPPRC) where the unique resource is the length. The SPPRC is NP-hard (Di Puglia Pugliese and Guerriero, 2013) for a generic resource constraint and it can be solved on a graph $\mathcal{H} = (\mathcal{N}, \mathcal{F})$ by pseudo-polynomial algorithms with a temporal complexity of $O(\bar{R}|\mathcal{F}|)$ where $\bar{R}$ is the maximal amount of resource. Conversely, the LPPLC can be solved in polynomial time with a temporal complexity of $O(|\mathcal{N}||\mathcal{F}|)$. Indeed, in the LPPLC, the maximal amount of resource $\bar{R}$ is the maximum length of the path $\bar{L}$, which is bounded from above by the number of vertices in the graph $|\mathcal{N}|$. In addition, being the LPPLC a relaxation of the ELPPLC, the correctness of the column generation procedure is ensured.
### 4.3. Pricing problem solution

In this section, we present the strategy we use to solve the pricing problem in the column generation procedure. The procedure is based on the one of Arslan et al. (2024) that makes use of the theoretical results presented in Section 4.2.

The pseudocode of such a procedure is presented in Algorithm 1. It can be noticed that an ELPPLC needs to be solved for [PP-P] only if: (i) no positive reduced cost circuits is detected, i.e, [PP-C](i) $W_i^* = \max\{\bar{W}_e : e \in \mathcal{E}_i^C\} \le 0$, for all $i \in \mathcal{I}$; (ii) the LPPLC version of the [PP-P] provides no positive reduced cost elementary path, but provides a positive reduced cost non-elementary path; (iii) either the maximum length of the chains is strictly larger than the maximum length of the cycles plus one, i.e., $L^P > L^C + 1$, or no reduced cost circuit has a value greater than $-\beta$. Indeed, if the LPPLC do not find any positive reduced cost non-elementary path, then [PP-P] does not admit any positive reduced cost elementary path, as well. In addition, if some positive reduced cost elementary paths are found when solving the LPPLC, these can be included in the RMP without the need to solve [PP-P] with an ELPPLC. Finally, in the case where $L^P \le L^C + 1$, as mentioned in Section 4.2, if the solution of the LPPLC did not report any circuit with a reduced cost larger than $-\beta$, then [PP-P] will not provide any positive reduced cost path that is non-elementary.

Algorithm 1 solves the MP to optimality at each node of the branch-and-bound tree.

<table><caption>**Algorithm 1:** Column generation procedure.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>do</td></tr><tr><td>2</td><td>solve the RMP;</td></tr><tr><td>3</td><td>get the optimal solution of the dual of the RMP;</td></tr><tr><td>4</td><td>build pricing subproblems [PP-C](i), i ∈ I and [PP-P];</td></tr><tr><td>5</td><td>solve [PP-C](i) and let W&#773;<sub>i</sub><sup>*</sup> be its optimal value, for all i ∈ I;</td></tr><tr><td>6</td><td>let W&#773;<sup>*C</sup> = max{W&#773;<sub>i</sub><sup>*</sup> : i ∈ I};</td></tr><tr><td>7</td><td>if W&#773;<sup>*C</sup> ≤ 0 then</td></tr><tr><td>8</td><td>Solve the LPPLC on graph H<sup>P</sup> and let W&#773;<sup>*P</sup> be its optimal value;</td></tr><tr><td>9</td><td>if W&#773;<sup>*P</sup> > 0 and all the positive reduced cost paths returned by solving the LPPLC are non-elementary then</td></tr><tr><td>10</td><td>if (L<sup>P</sup> ≤ L<sup>C</sup> + 1 and W&#773;<sup>*C</sup> > -β) or (L<sup>P</sup> > L<sup>C</sup> + 1) then</td></tr><tr><td>11</td><td>solve the ELPPLC on graph H<sup>P</sup> and let W&#773;<sup>*P</sup> be its optimal value;</td></tr><tr><td>12</td><td>end</td></tr><tr><td>13</td><td>end</td></tr><tr><td>14</td><td>end</td></tr><tr><td>15</td><td>add positive reduced cost elementary circuits and paths to the RMP, if any is detected;</td></tr><tr><td>16</td><td>while max{W&#773;<sup>*C</sup>, W&#773;<sup>*P</sup>} > 0;</td></tr></tbody></table>
We refer to Arslan et al. (2024) for the polynomial time procedure based on the Bellman-Ford algorithm to solve the LPPLC. In the following, we describe the label correcting dynamic programming algorithm (Feillet et al., 2004) we propose to solve the ELPPLC.

In the work of Arslan et al. (2024), the ELPPLC is tackled by a mixed integer programming formulation with an exponential number of constraints. Here, we chose a label correcting dynamic programming algorithm because of its efficiency and its flexibility when it comes to incorporate non-robust valid inequalities to strengthen the formulation (see Section 4.4).

In a label correcting algorithm, vertices $i \in \mathcal{N}$ are repeatedly processed and their associated labels (set $\mathcal{L}_i$), which identify paths in the graph, are extended. Precisely, a label $l = (L, \bar{W}, \mathcal{U}, i) \in \mathcal{L}_i$ represents a path in graph $\mathcal{H}$ starting at vertex $s$ and ending at vertex $i \in \mathcal{N}$ characterised by its accumulated weight $\bar{W}$, its length $L$ and the subset of visited vertices $\mathcal{U} \subseteq \mathcal{N}$. A label $l = (L, \bar{W}, \mathcal{U}, i)$ associated with vertex $i$ can be extended along arc $(i, j) \in \mathcal{F}$ if the length constraint $(L < \bar{L})$ and the elementarity constraint $(j \notin \mathcal{U})$ are respected. If this is the case, a new label $l' = (L + 1, \bar{W} + W_{ij}, \mathcal{U} \cup \{j\}, j)$ associated with vertex $j \in \mathcal{V}$ is obtained. Dominance rules are commonly applied in labelling algorithms to prune labels which would not lead to any optimal solution. Given two labels $l = (L, \bar{W}, \mathcal{U}, i)$ and $l' = (L', \bar{W}', \mathcal{U}', i)$ associated with the same vertex $i$, we say that $l$ dominates $l'$ if:

$$L \leq L', \quad \bar{W} \geq \bar{W}', \quad \mathcal{U} \subseteq \mathcal{U}', \qquad (7)$$

and one of the inequalities (inclusion) is strict.

The elementarity constraint makes the ELPPLC strongly NP-hard and slows down the solution algorithm. Thus we adopt the ng-path relaxation (Baldacci et al., 2011), which partially relaxes the elementarity constraint of the paths, to accelerate the solution of the ELPPLC.
### 4.4. Cut generation

In order to improve the linear relaxation bound at each node of the branch-and-bound tree, we strengthen the formulation of the MP via the inclusion of subset-row (SR) inequalities (Jepsen et al., 2008). Given a subset $S \subseteq V$ and a multiplier $p_i$ for each $i \in S$, SR inequalities are obtained as a Chvátal-Gomory rounding of the Constraints (2) associated with elements in $S$:

$$ \sum_{e \in E} \left[ \sum_{i \in S} p_i a_i^e \right] \lambda_e \leq \left[ \sum_{i \in S} p_i \right], \quad S \subseteq V. \qquad (8) $$

A common practice from the literature is to separate such inequalities by enumeration of small subsets of $V$ (see, e.g., Pecin et al., 2017). However, the characteristics of the KEP instances make this procedure prohibitive in terms of computational time. To overcome this computational burden, instead of separating the SR inequalities directly, we propose two fast heuristics to separate them. Each heuristic is based on the separation of a different family of inequalities, namely the *clique* (Cl) and *odd-hole* (OH) inequalities, respectively. Fast procedures from the literature permit the detection of violated Cl and OH inequalities, which are then translated into SR inequalities. We show that each violated OH inequality leads to a SR inequality with the same violation. Finally, the obtained SR inequalities are inserted in the RMP. However, these inequalities are *non-robust*, that is, considering their dual variables in the pricing problem solution modifies the structure of the pricing problem itself. This generally increases the difficulty of solving the pricing problem. The interested reader may refer to Pecin et al. (2017) for a description regarding the management of the SR inequalities in the pricing problem. On the other side, such non-robust inequalities are worthy of use because of their great potential to reduce the integrality gaps.

Cl and OH inequalities are identified thanks to the so-called conflict graph. In the following, we introduce the notion of a conflict graph in the context of our problem. Given an exchange $e \in E$, we denote by $V(e)$ the set of vertices in exchange $e$. We say that two exchanges $e, e' \in E$ are *in conflict* if they share common vertices, i.e., if $V(e) \cap V(e') \neq \emptyset$. Variables associated with exchanges in conflict cannot both take value one in a feasible
solution of formulation [SP], because of Constraints (2). Given a fractional solution $\tilde{\lambda}$ of the MP, we define the so-called conflict graph $\mathcal{C} = (\mathcal{Q}, \mathcal{T})$ as follows. Node set $\mathcal{Q}$ contains nodes associated with the exchanges $e \in \mathcal{E}$ whose corresponding variable has a fractional value, i.e., $\tilde{\lambda}_e \in ]0, 1[$. Edge set $\mathcal{T}$ contains an edge $(e, e')$ if exchanges $e \in \mathcal{Q}$ and $e' \in \mathcal{Q}$ are in conflict. In the following, we say that an edge $(e, e') \in \mathcal{T}$ is covered by a vertex $v \in \mathcal{V}$ if $v \in \mathcal{V}(e) \cap \mathcal{V}(e')$.

### 4.4.1. Clique inequalities

Clique inequalities (Cl) correspond to cliques in conflict graph $\mathcal{C}$. A clique is a set of nodes $\mathcal{W} \subseteq \mathcal{Q}$ that induces a complete subgraph, i.e., such that $(e, e') \in \mathcal{T}$, for each $e, e' \in \mathcal{W}$, $e \neq e'$. The clique inequality associated with $\mathcal{W}$ is:

$$ \sum_{e \in \mathcal{W}} \lambda_e \leq 1. \qquad (9) $$

The separation of these inequalities is performed via the iterative heuristic algorithm proposed by Marzi et al. (2019). First, each node $e \in \mathcal{Q}$ is assigned with a weight equal to the number of its incident edges times $\tilde{\lambda}_e$. At each iteration, the algorithm selects a node $e \in \mathcal{Q}$ with the highest weight and builds a maximal weighted clique containing that node according to a greedy criterion. When the clique is maximal, its nodes are removed from the conflict graph and a new iteration starts. Finally, if such a clique has at least cardinality three it may give rise to a clique inequality.

Cl inequalities are defined over a subset of variables $\mathcal{W}$, hence, the management of the associated dual variable $\gamma_{\mathcal{W}} \geq 0$ when solving the pricing problem is not tractable. Indeed, when solving the pricing problem, the dual variable $\gamma_{\mathcal{W}}$ has to be discounted if the associated exchange is the same as one of the exchanges in set $\mathcal{W}$. When solving the ELPPRC with a labelling algorithm, it would require to compare, for each label, the associated partial path with the elements in set $\mathcal{W}$, which would be computationally very costly.

Thus, we propose a heuristic procedure to retrieve a violated SR inequality (8) given a
435 violated Cl inequality defined on a clique $\mathcal{W}$. We denote by $\mathcal{T}(\mathcal{W}) = \{(e, e') \in \mathcal{T} : e, e' \in \mathcal{W}, e \neq e'\}$ the subset of the edges whose incident nodes are in clique $\mathcal{W}$. The procedure first determines a subset of vertices $S \subseteq \mathcal{V}$ such all the edges $(e, e') \in \mathcal{T}(\mathcal{W})$ are covered with at least one vertex $v \in S$. Then, it defines multipliers $p_i, i \in S$ to obtain a violated SR inequality.

440 Subset $S$ is defined as follows. First, we determine the subset of candidate vertices $\mathcal{V}(\mathcal{W}) \subseteq \mathcal{V}$ that can cover the edges in $\mathcal{T}(\mathcal{W})$, i.e., $\mathcal{V}(\mathcal{W}) = \bigcup_{e,e' \in \mathcal{W}, e \neq e'} \mathcal{V}(e) \cap \mathcal{V}(e')$. The vertices of $v \in \mathcal{V}(\mathcal{W})$ are ordered by decreasing number of nodes $e \in \mathcal{W}$ such that $v \in \mathcal{V}(e)$, i.e., of exchanges in the clique which visit vertices $v$. Ties are broken by lexicographically ordering the vertices of $\mathcal{V}(\mathcal{W})$ associated with the same number of exchanges in the clique, i.e., by increasing vertex index. Then, each vertex $v \in \mathcal{V}(\mathcal{W})$ is processed in such order and inserted in $S$ if there exists an edge $(e, e') \in \mathcal{T}(\mathcal{W})$ that can be covered with $v$ and has not been covered with any of the vertices already in $S$. Such edges are then covered with vertex $v$.

445 Finally, the procedure determines multipliers $p_i, i \in S$. First, if the cardinality of $S$ is less or equal to five, we assign the multipliers proposed in Pecin et al. (2017). If with this choice of multipliers the subset-row is violated we stop. Otherwise, if it is not violated or the cardinality of $S$ is strictly larger than five we determine the multipliers by solving a dedicated mixed-integer program. The multipliers proposed by Pecin et al. (2017) and details regarding the program are reported in Appendix B.

455 We report an example of the procedure to transform a Cl inequality into a SR inequality.

**Example 2.** We make use of the toy instance of the KEP presented in Example 1. We consider fractional solution $\tilde{\lambda}$ with five exchanges $e_1, e_2, e_3, e_4$ and $e_5$ defined as in Table 1. The associated conflict graph $C = (\mathcal{Q}, \mathcal{T})$ is shown in Figure 2 where on each edge we report the set of vertices of the compatibility graph $\mathcal{G} = (\mathcal{V}, \mathcal{A})$ that can cover that edge. It is easy to see that set of nodes $\mathcal{W} = \{e_1, e_2, e_3, e_4\}$ forms a clique in the conflict graph which gives rise to a violated clique inequality. Indeed, by looking at Table 1, we have $\tilde{\lambda}_{e_1} + \tilde{\lambda}_{e_2} + \tilde{\lambda}_{e_3} + \tilde{\lambda}_{e_4} =$

460
1.33 > 1, thus the violation of the Cl inequality is equal to 0.33.

Now, we retrieve the associated SR inequality, i.e., we need to define set $S$ and multipliers $p_i$, $i \in S$. We first determine $V(W) = \{1, 6, 7, 8, 9\}$ such that the edges of $T(W) = \{(e_1, e_2), (e_1, e_3), (e_1, e_4), (e_2, e_3), (e_2, e_4), (e_3, e_4)\}$ can be covered.

465

In Table 3, we propose an ordering of the vertices of $V(W)$ by decreasing number of exchanges of the clique that visit them. In order to define set $S$, the first vertex to be processed is 7 and the edges of $T(W)$ covered by it are $(e_2, e_3)$, $(e_2, e_4)$ and $(e_3, e_4)$. We insert 7 in $S$. The next vertex is 8 and the edges of $T(W)$ covered by it are $(e_1, e_2)$, $(e_1, e_4)$ and $(e_2, e_3)$. The first two were not covered previously, hence, we insert 8 in $S$. The next vertex is 1, it covers only edge $(e_1, e_4)$ which is already covered by $8 \in S$, hence, it is not inserted in $S$. The next vertex is 6 and the edge of $T(W)$ covered by it is $(e_1, e_3)$ which was not covered previously, hence, we insert 6 in $S$. All the edges of $T(W)$ are now covered, thus, there is no need to process other vertices of $V(W)$. Then, we obtain set $S = \{7, 8, 6\}$.

470

It is easy to see that by assigning multipliers $p_1 = 1/2$, for each $i \in S$, we obtain a violated SR inequality with the same violation of the Cl inequality.

475

<table><caption>Table 1: Fractional solution $\tilde{\lambda}$.</caption><thead><tr><th>exchange</th><th>value in $\tilde{\lambda}$</th></tr></thead><tbody><tr><td>$e_1 = (1, 8, 9, 6)$</td><td>0.33</td></tr><tr><td>$e_2 = (2, 8, 9, 7)$</td><td>0.33</td></tr><tr><td>$e_3 = (6, 7, 6)$</td><td>0.33</td></tr><tr><td>$e_4 = (1, 8, 4, 5, 7)$</td><td>0.33</td></tr><tr><td>$e_5 = (2, 3, 4, 5)$</td><td>0.66</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Table 3: Ordering of the elements of $V(W)$.</figcaption></figure>

<table><thead><tr><th>$V(W)$</th><th>exchanges of $W$</th></tr></thead><tbody><tr><td>7</td><td>$e_2, e_3, e_4$</td></tr><tr><td>8</td><td>$e_1, e_2, e_4$</td></tr><tr><td>1</td><td>$e_1, e_4$</td></tr><tr><td>6</td><td>$e_1, e_3$</td></tr><tr><td>9</td><td>$e_1, e_2$</td></tr></tbody></table>

### 4.4.2. Odd-hole inequalities

Odd-hole inequalities (OH) correspond to particular subgraphs in conflict graph $C$, namely to odd cycles without chords. An odd cycle without chords is a set of nodes $P = \{e_1, e_2, \dots, e_{2k+1}\}$, $k \ge 2$, such that edge set $T$ contains edges $t_i = (e_i, e_{i+1})$, $i = 1, \dots, 2k$, and $t_{2k+1} = (e_{2k+1}, e_1)$

480
and no other edge incident on two nodes of $\mathcal{P}$. The odd-hole inequality associated with $\mathcal{P}$ is:

$$ \sum_{e \in \mathcal{P}} \lambda_e \leq \frac{|\mathcal{P}| - 1}{2}. \qquad (10) $$

The separation of these inequalities is done based on the exact procedure of Hoffman and Padberg (1993). Such a procedure considers each vertex of conflict graph $\mathcal{C}$ and determines all the odd-hole inequalities associated with odd cycles without chords starting at the considered vertex. This procedure is rather time consuming. Therefore, as suggested by Hoffman and Padberg (1993), when determining the inequalities, we randomly consider only the 30% of the vertices of the conflict graph as starting vertex.

OH inequalities are defined over a subset of variables $\mathcal{P}$, hence, the management of the associated dual variable $\theta_{\mathcal{P}} \geq 0$ when solving the pricing problem is not tractable. The explanation is the same as the one for the Cl inequalities (see Section 4.4.1).

For this reason, we propose a procedure to retrieve a SR inequality from an OH inequality defined on cycle $\mathcal{P}$. Moreover such an SR inequality is a lifted version of the associated OH inequality. For each edge $t$ of the odd cycle $\mathcal{P}$, we select in the compatibility graph $\mathcal{G} = (\mathcal{V}, \mathcal{A})$ a vertex $v \in \mathcal{V}$ such that $t$ is covered by $v$. Precisely, for each edge $t_i = (e_i, e_{i+1}) \in \mathcal{T}$, $i = 1, \dots, 2k$, we select a vertex $v_i$ in the set $\mathcal{V}(e_i) \cap \mathcal{V}(e_{i+1})$; and for edge $t_{2k+1} = (e_{2k+1}, e_1) \in \mathcal{T}$, we select a vertex $v_{2k+1}$ in the set $\mathcal{V}(e_{2k+1}) \cap \mathcal{V}(e_1)$.

We remark that in the odd cycle there are no chords, hence, all the $v_i$ are different from each other. The associated SR inequality is defined over $\mathcal{S} = \{v_1, \dots, v_{2k+1}\}$ and multipliers $p_i = 1/2$ for each $i \in \mathcal{S}$:

$$ \sum_{e \in \mathcal{E}} \left\lfloor \frac{1}{2} \sum_{i \in \mathcal{S}} a_i^e \right\rfloor \lambda_e \leq \left\lfloor \frac{|\mathcal{S}|}{2} \right\rfloor. \qquad (11) $$

**Lemma 1.** If a fractional solution $\tilde{\lambda}$ violates OH inequality (10) then it violates also SR inequality (11) associated with inequality (10).

*Proof.* First, we observe that the right hand-side of inequality (11) coincides with the one of inequality (10), indeed, it holds $|\mathcal{S}| = |\mathcal{P}|$ by construction and $|\mathcal{P}|$ is odd. Then, in the left
505 hand-side of inequality (11), at least the variables associated with exchanges in $\mathcal{P}$ appear with coefficient one. Indeed, such exchanges visit exactly two vertices in $\mathcal{S}$. Finally, it holds

$$ \sum_{e \in \mathcal{E}} \left[ \frac{1}{2} \sum_{i \in \mathcal{S}} a_i^e \right] \tilde{\lambda}_e \geq \sum_{e \in \mathcal{P}} \left[ \frac{1}{2} \sum_{i \in \mathcal{S}} a_i^e \right] \tilde{\lambda}_e = \sum_{e \in \mathcal{P}} \tilde{\lambda}_e > \frac{|\mathcal{P}| - 1}{2} = \left\lfloor \frac{|\mathcal{S}|}{2} \right\rfloor \quad (12) $$

and $\tilde{\lambda}$ violates inequality (11). □

510 The impact on the pricing problem is the same as the one of the SR inequalities.

We report an example of the procedure to transform a OH inequality into a SR inequality.

**Example 3.** We make use of the toy instance of the KEP presented in Example 1. We consider fractional solution $\tilde{\lambda}$ defined as in Table 4. The associated conflict graph $\mathcal{C} = (\mathcal{Q}, \mathcal{T})$ is shown in Figure 2 where on each edge we report the set of vertices of the compatibility graph $\mathcal{G} = (\mathcal{V}, \mathcal{A})$ that can cover that edge. It is easy to see that the set of nodes $\mathcal{P} = \{e_1, e_2, e_3, e_4, e_5\}$ forms an odd cycle without chords in the conflict graph which give rise to a violated OH inequality. Indeed, by looking at Table 4, we have $\tilde{\lambda}_{e_1} + \tilde{\lambda}_{e_2} + \tilde{\lambda}_{e_3} + \tilde{\lambda}_{e_4} + \tilde{\lambda}_{e_5} = 2.5 > (|\mathcal{P}| - 1)/2 = 2$, thus the violation of the OH inequality is equal to 0.5.

515

Now, we retrieve the associated SR inequality. In this case, we just need to define set $\mathcal{S}$. For each edge in the odd cycle, we select one of the vertices reported in Figure 2 on that edge. By defining $\mathcal{S} = \{1, 4, 6, 7, 8\}$, and multipliers $p_i = 1/2, i \in \mathcal{S}$, we obtain a violated SR inequality with the same violation of the OH inequality.

520

**4.4.3. Cut generation strategy**

Preliminary results reveal that the best strategy is to add at most 100 inequalities to the MP in the branch-and-bound tree; after reaching this threshold, their separation is stopped. We allow ten minutes (out of the one-hour global time limit of the BPC algorithm) for the total time spent in the separation procedures; beyond this threshold, such a procedure is

525

We allow ten minutes (out of the one-hour global time limit of the BPC algorithm) for the total time spent in the separation procedures; beyond this threshold, such a procedure is
<table><caption>Table 4: Fractional solution $\tilde{\lambda}$.</caption><thead><tr><td>exchange</td><td>value in $\tilde{\lambda}$</td></tr></thead><tbody><tr><td>$e_1 = (1, 3, 4)$</td><td>0.5</td></tr><tr><td>$e_2 = (4, 5, 7, 4)$</td><td>0.5</td></tr><tr><td>$e_3 = (6, 7, 6)$</td><td>0.5</td></tr><tr><td>$e_4 = (2, 8, 9, 6)$</td><td>0.5</td></tr><tr><td>$e_5 = (1, 8, 9)$</td><td>0.5</td></tr><tr><td>$e_6 = (2, 3, 5)$</td><td>0.5</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 2: Conflict graph arising from the fractional solution of Table 4, where odd cycle without cords $\mathcal{P} = \{e_1, e_2, e_3, e_4, e_5\}$ is marked in blue.</figcaption></figure>

not performed. We insert a violated inequality in the RMP if its violation is greater than or equal to 0.1. At each separation round, we separate Cl and OH inequalities in this order. When 20 violated inequalities have been detected, we stop looking for other inequalities in that round. Separating the OH inequalities is rather time consuming and preliminary tests showed that the best strategy is to separate them only at the root node of the branch-and-bound tree. Hence, only Cl inequalities are separated at the other nodes of the tree. A time limit of one minute is imposed for the separation of each of the two families of inequalities at each round. In addition, if during one round no Cl inequalities are detected, we keep separating OH inequalities only at that node.

Note that if non-robust valid inequalities are active in the RMP, the circuits are priced by a labelling algorithm instead of the variant of the Bellman-Ford algorithm presented in Section 4.3. Indeed, dealing with non-robust inequalities makes the pricing problem more complicated as it requires more resources, one per each non-robust inequality. In that context, labelling algorithms are well-suited for the management of these additional resources.

Finally, we recall that if non-robust valid inequalities are active in the RMP, the pricing of circuits and paths can no longer be modelled as a LPPLC, but must be modelled as an ELPPRC. In this case, all pricing problems are NP-hard.
### 4.5. Branching scheme

To ensure the integrality of the solution returned by the BPC algorithm, we branch on the use of the arcs in $\mathcal{A}$. Let $\tilde{\lambda}$ be an optimal fractional solution of the MP at a node of the branch-and-bound tree. We branch on values $f_{ij} = \sum_{e \in \mathcal{E}} b_{ij}^e \tilde{\lambda}_e$, $(i, j) \in \mathcal{A}$, where parameter $b_{ij}^e$ takes value one if arc $(i, j) \in \mathcal{A}$ belongs to exchange $e \in \mathcal{E}$ and zero otherwise. Precisely, we select the branching candidate whose value is the closest to 0.5. We remark that value $f_{ij} \in ]0, 1[$, hence, in one branch we force arc $(i, j)$ to be used $(\sum_{e \in \mathcal{E}} b_{ij}^e \lambda_e \ge 1)$ while in the other branch, we forbid its use $(\sum_{e \in \mathcal{E}} b_{ij}^e \lambda_e = 0)$. In the former case, dual variable $\phi_{ij} \le 0$ associated with the branching constraint is considered when solving the pricing problem. Precisely, it is discounted from arc weight $\bar{W}_{ij}$ in Equation (5) or and (6). In the latter case, arc $(i, j)$ is removed from graph $\mathcal{H}$ when we solve the pricing problem. Last, the branch-and-bound tree is explored according to the best-first strategy.

## 5. Computational experiments

Our BPC algorithm is implemented in C++ and compiled in release mode under a 64-bit version of MS Visual Studio 2019. The linear programming models in the column generation procedure, the mixed-integer programming models in the separation heuristic based on the Cl inequalities and the integer programming models in the restricted master heuristic are solved by GUROBI 9.5.2 (64-bit version). All the experiments are run on a 64-bit Windows machine equipped with a Intel(R) Xeon(R) Silver 4214 processor with 24 cores hyper-threaded to 48 virtual cores, with a base clock frequency of 2.2 GHz, and 96 GB of RAM. For each run of the algorithm, we impose one hour time limit and allow a single thread. If such time limit is reached, the primal heuristic is called to seek for lower bound improvements. All the integer programming models have a maximum of 16 GB of memory, i.e., we set parameter `GRB_DoubleParam_MemLimit` to 16. When the memory limit is reached the solver stops and the solution statistics are collected.

We assess the impact of the valid inequalities to select the best configuration for the BPC
algorithm. The detailed analysis of the results is in Appendix D. Based on those results, we choose the configuration of the BPC algorithm where both CI and OH inequalities are separated because: (i) it provides the best results on the instances solved to optimality; (ii) it provides the best upper bound improvements on the instances not solved to optimality. Hereafter, we will simply refer to this configuration as the BPC algorithm.

In this section, first, we present the characteristics of the three benchmark instances from the literature we consider and those of the newly generated instances. Then, we compare the results obtained with the BPC algorithm on the benchmark instances from the literature with those reported in Pansart et al. (2022), Arslan et al. (2024) and Delorme et al. (2023). Note that these authors reported computational results on different datasets. In addition, we further compare the BPC algorithm against the HPIEF formulation by Dickerson et al. (2016) on the new challenging instances. For the sake of a fair comparison, when the machine used in a previous work from the literature has worse performance than ours and their code is available online, we rerun it on our machine.

The instances and detailed results of all the tested approaches can be found at this link: https://doi.org/10.57745/IHQAPY.

In the following, we describe the columns' headings which are common to several tables in this section; the ones used only in one table are described above the table itself. The headings referring to the characteristics of the different sets of instances make use of the notation introduced in Section 3. Other than those, we use # to refer to the number of instances in a set. The headings referring to the results of a solution method are: #opt.: number of instances solved to optimality; avg.#nodes: the average number of nodes of the branch-and-bound tree; avg.t[s]: computational time in seconds; avg.gap[%]: optimality gap expressed as a percentage, i.e., $100(UB-LB)/LB$ where UB and LB are the upper and lower bounds returned by the solution method; avg.gap[%] noOpt.: optimality gap expressed as a percentage for the instances not solved to optimality; avg.#Cl: number of SR inequalities arising from the CI inequalities; avg.#OH: number of SR inequalities arising from the OH inequal-
ities; avg.t[s] sep.: the separation time in seconds. We use symbol '-' in a table entry, if the associated datum is not available or cannot be computed.

## 5.1. Benchmark instances

We assess the efficiency of the BPC algorithm on three different sets of instances considered in the literature: the “Kidney Data (00036)” set from the PrefLib dataset (Mattei and Walsh, 2013), the set proposed by Pansart et al. (2022) and the one considered by Delorme et al. (2023). The instances belonging to the first two sets are produced by the so-called *Saidman generator* (Saidman et al., 2006), while the ones belonging to the third set are produced by the generator introduced by Delorme et al. (2022). In addition, we build a fourth set of instances, the *KEP\_hard*, via the generator by Delorme et al. (2022) with all the challenging characteristics, i.e., long cycles and chains and the maximization of the medical benefit. The literature lacked of such a set of instances.

Table 5 summarises the characteristics of the instances in the three sets. The rows of the tables are associated with the sets of instances. The additional column headings used in this table are: set: name of the set; $|\mathcal{D}|[\%:]$ percentage of altruistic donors w.r.t. the number of pairs $|\mathcal{I}|$; avg. dens. $\mathcal{G}$: average density of compatibility graph $\mathcal{G}$ expressed as a percentage of arcs w.r.t. the number of arcs in a complete graph with the same number of vertices as $\mathcal{G}$; obj.: type of objective function, either maximization of the number of transplants (#TR) or of the medical benefit (MB). Note that the total number of vertices in the compatibility graph is $(1 + |\mathcal{D}|[\%])|\mathcal{I}|$.

<table><caption>Table 5: Characteristics of the sets of instances.</caption><thead><tr><th>set</th><th>#</th><th>|<i>I</i>|</th><th>|<i>D</i>|[%]</th><th>avg. dens.</th><th><i>L</i><sup>C</sup></th><th><i>L</i><sup>P</sup></th><th>obj.</th></tr></thead><tbody><tr><td>PrefLib</td><td>2000</td><td>16, 32, 64, 128,<br>256, 512, 1024, 2048</td><td>0%, 5%,<br>10%, 15%</td><td>25%</td><td>3, 4</td><td>0, 3, 4,<br>5, 6</td><td>#TR</td></tr><tr><td>Pansart et al. (2022)</td><td>270</td><td>50, 100, 250,<br>500, 750, 1000</td><td>1%, 5%, 10%<br>15%, 25%</td><td>5%</td><td>3</td><td>3, 6, 12</td><td>MB</td></tr><tr><td>Delorme et al. (2023)</td><td>840</td><td>50, 100, 200, 400,<br>600, 800, 1000</td><td>0%</td><td>10%</td><td>3, 4, 5,<br>6, 7, 8</td><td>0</td><td>#TR, MB</td></tr><tr><td>KEP\_hard</td><td>405</td><td>500, 750, 1000</td><td>5%, 10%, 15%</td><td>10%</td><td>3, 4, 5,</td><td>3, 6, 12</td><td>MB</td></tr></tbody></table>
## 5.2. Results on the whole testbed

In this section, we present the aggregated results obtained by the BPC algorithm on the three sets of instances. We compare our results with those reported in the literature.

### 5.2.1. Results on the PrefLib dataset

In this section, we compare the results obtained by the BPC algorithm on the instances of the PrefLib dataset with those obtained by the BP algorithm of Arslan et al. (2024). In addition, Arslan et al. (2024) compare their BP algorithm against a BP algorithm based on the PICEF formulation by Dickerson et al. (2016) (BP-PICEF). For the sake of completeness, we report those results here, as well. The authors implemented both BP algorithms using Julia language and ran the experiments on a 2 Dodeca-core Haswell Intel Xeon E5-2680 v3 2.5 GHz machine with 128 GB RAM running Linux OS. As in our experiments, the authors allow a single thread and, with such a restriction, the CPU of their machine is comparable with ours (PassMark Software, 2024).

Table 6 reports the results on the PrefLib dataset. The rows of the table group instances with given maximum path lengths and given numbers of incompatible pairs. Note that the first row groups all small size instances with a maximum of 512 pairs, while the results for large instances with 1024 or 2048 pairs are reported in the other rows. In the column regarding the BP algorithm of Arslan et al. (2024), we report only the average solution time since it manages to solve to optimality all the instances at the root node. We make use of `-` when no result is available: Arslan et al. (2024) do not test the BP algorithm on instances where only circuits are to be priced, i.e., those with $L^P = 0$.

From the results of Table 6, it can be observed that both approaches yield comparable results on instances with up to 512 pairs, regardless of the maximum length of the paths. Indeed, both algorithms solve those instances to optimality at the root node (before the first separation round). The computational times are of the same order of magnitude. Even though all the instances characterised by a number of pairs equal to 1024 or 2048 are solved to optimality by both approaches, the BP algorithm of Arslan et al. (2024) is faster than
<table><caption>Table 6: Results on the PrefLib dataset.</caption><thead><tr><th rowspan="2">L<sup>P</sup></th><th colspan="2">Instances</th><th colspan="3">BPC</th><th>Arslan et al. (2024)</th><th colspan="3">BP-PICEF</th></tr><tr><th>|I|</th><th>#</th><th>#opt.</th><th>avg.#nodes</th><th>avg.t[s]</th><th>avg.t[s]</th><th>#opt.</th><th>avg.t[s]</th><th>avg.gap[%] noOpt.</th></tr></thead><tbody><tr><td>0,3,4, 5,6</td><td>16,32,64, 128,256,512</td><td>1480</td><td>1480</td><td>1.00</td><td>1.24</td><td>0.99</td><td>1480</td><td>11.13</td><td>-</td></tr><tr><td rowspan="2">0</td><td>1024</td><td>20</td><td>20</td><td>1.00</td><td>16.26</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>2048</td><td>20</td><td>20</td><td>1.00</td><td>159.60</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">3</td><td>1024</td><td>60</td><td>60</td><td>1.00</td><td>23.18</td><td>3.75</td><td>60</td><td>66.41</td><td>-</td></tr><tr><td>2048</td><td>60</td><td>60</td><td>1.00</td><td>281.26</td><td>11.93</td><td>60</td><td>419.38</td><td>-</td></tr><tr><td rowspan="2">4</td><td>1024</td><td>60</td><td>60</td><td>4.60</td><td>26.19</td><td>3.70</td><td>60</td><td>197.22</td><td>-</td></tr><tr><td>2048</td><td>60</td><td>60</td><td>1.00</td><td>278.35</td><td>12.46</td><td>60</td><td>1955.81</td><td>-</td></tr><tr><td rowspan="2">5</td><td>1024</td><td>60</td><td>60</td><td>1.00</td><td>23.20</td><td>3.72</td><td>60</td><td>431.68</td><td>-</td></tr><tr><td>2048</td><td>60</td><td>60</td><td>1.00</td><td>279.80</td><td>12.56</td><td>53</td><td>5487.63</td><td>0.36</td></tr><tr><td rowspan="2">6</td><td>1024</td><td>60</td><td>60</td><td>60.13</td><td>70.31</td><td>3.72</td><td>60</td><td>818.91</td><td>-</td></tr><tr><td>2048</td><td>60</td><td>60</td><td>1.00</td><td>277.11</td><td>12.46</td><td>13</td><td>13082.02</td><td>2.51</td></tr></tbody></table>

the BPC algorithm by an order of magnitude. The majority of the computational time of the BPC algorithm is spent in the column generation procedure. With our BPC algorithm, valid inequalities are inserted into the RMP for four instances only, and in such a cases the pricing problem is then solved with a labelling algorithm for the ELPPRC. For all other instances of the PrefLib dataset, solving the LPPLC is sufficient to solve the pricing problem, the conditions to necessarily solve an ELPPLC are never reached. Hence, the BP and BPC algorithms make use of the same pricing strategy and the difference in computation times are probably due to a more efficient implementation of the algorithms by Arslan et al. (2024). The comparison against BP-PICEF shows that our approach is clearly better.

It can be noticed that no instances of this set are difficult. With the BPC algorithm all instances are solved in on average 40.46 seconds.

### 5.2.2. Results on the set of instances of Pansart et al. (2022)

In this section, we discuss the results obtained by the BPC algorithm on the instances introduced by Pansart et al. (2022). We compare the BPC algorithm performances with the restricted master heuristic of Pansart et al. (2022) on the subset of small instances characterised by a number of pairs up to 250. We recall that the approach of Pansart et al.
(2022) is a heuristic with a performance guarantee, that is, it provides valid lower and upper bounds on the optimal value of formulation [SP]. The restricted master heuristic is run on a machine equipped with an Intel Xeon E5-2440 v2 @ 1.9 GHz processor and 32 GB of RAM. According to PassMark Software (2024), the CPU of such a machine is 36% slower than ours under single-threading. As we shall see, this difference does not invalidate the conclusions. Note that Pansart et al. (2022) do not test their procedure on all these instances with more than 500 pairs.

Table 7 summarises the results of the comparison between the BPC algorithm and the restricted master heuristic of Pansart et al. (2022). The rows of the table group instances with the same maximum path length and the same number of incompatible pairs.

<table><caption>Table 7: Results on the set of instances of Pansart et al. (2022) with up to 250 pairs.</caption><thead><tr><th colspan="3">Instances</th><th colspan="3">BPC</th><th colspan="3">Pansart et al. (2022)</th></tr><tr><th>L<sup>P</sup></th><th>|I|</th><th>#</th><th>#opt.</th><th>avg.#nodes</th><th>avg.t[s]</th><th>#opt.</th><th>avg.t[s]</th><th>avg.gap[%]</th><th>noOpt.</th></tr></thead><tbody><tr><td rowspan="3">3</td><td>50</td><td>15</td><td>15</td><td>1.00</td><td>0.04</td><td>15</td><td>1.07</td><td>-</td><td></td></tr><tr><td>100</td><td>15</td><td>15</td><td>1.00</td><td>0.14</td><td>9</td><td>1.21</td><td>0.33</td><td></td></tr><tr><td>250</td><td>15</td><td>15</td><td>1.00</td><td>0.93</td><td>7</td><td>3.45</td><td>0.07</td><td></td></tr><tr><td rowspan="3">6</td><td>50</td><td>15</td><td>15</td><td>1.40</td><td>0.04</td><td>14</td><td>1.20</td><td>0.05</td><td></td></tr><tr><td>100</td><td>15</td><td>15</td><td>2.07</td><td>0.34</td><td>8</td><td>2.17</td><td>0.64</td><td></td></tr><tr><td>250</td><td>15</td><td>15</td><td>42.87</td><td>15.30</td><td>2</td><td>27.74</td><td>0.32</td><td></td></tr><tr><td rowspan="3">12</td><td>50</td><td>15</td><td>15</td><td>1.27</td><td>0.05</td><td>15</td><td>2.52</td><td>-</td><td></td></tr><tr><td>100</td><td>15</td><td>15</td><td>2.20</td><td>0.30</td><td>14</td><td>26.59</td><td>0.19</td><td></td></tr><tr><td>250</td><td>15</td><td>15</td><td>44.33</td><td>51.39</td><td>8</td><td>1420.20</td><td>1.26</td><td></td></tr></tbody></table>

From the results in Table 7, the BPC algorithm solves all the 135 instances to optimality. Optimality is proven at the root node for 105 instances in on average 0.45 seconds. For the remaining ones, the BPC algorithm explores a few tens of nodes on 28 instances and a few hundreds on the remaining two. For these instances, the computational time increases. On average, it is equal to 32.68 seconds, however it is always less than 400 seconds. Conversely, the heuristic with a performance guarantee of Pansart et al. (2022) proves the optimality of 92 instances, leaving the remaining ones with a positive optimality gap equal to 0.47%, on average. In terms of computational time, the BPC algorithm is faster than the algorithm of Pansart et al. (2022) on 132 instances. The three instances where the BPC algorithm
is slower correspond to those where the optimality is not proved at the root node. Hence the BPC algorithm branches, while the heuristic of Pansart et al. (2022) stops at the root node. Moreover, it is interesting to note that on the most difficult instances, that is with $L^P = 12$ and 250 pairs, the BPC algorithm is faster by at least an order of magnitude w.r.t. the algorithm of Pansart et al. (2022).

In Table 8, we report the results obtained by the BPC algorithm on the instances of Pansart et al. (2022) with $|\mathcal{I}| = 500,750,1000$. The rows of the table correspond to instances with the same maximum path length and the same number of incompatible pairs. We write '-' in columns `avg.#nodes` and `avg.t[s]` if there are no instances solved/unsolved in a row by the BPC algorithm and in the columns concerning the results of Pansart et al. (2022) when they are not available. Indeed, we recall that Pansart et al. (2022) only provide results for three subset of instances with at least 500 pairs.

<table><caption>Table 8: Results on the set of instances of Pansart et al. (2022) with at least 500 pairs.</caption><thead><tr><th colspan="3">Instances</th><th colspan="6">BPC results</th><th colspan="3">Pansart et al. (2022)</th></tr><tr><th>L<sup>P</sup></th><th>|I|</th><th>#</th><th>#</th><th>solved instances<br>avg.#nodes</th><th>avg.t[s]</th><th>#</th><th>unsolved instances<br>avg.#nodes</th><th>avg.gap[%]</th><th>#opt.</th><th>avg.t[s]</th><th>avg.gap[%]<br>noOpt.</th></tr></thead><tbody><tr><td rowspan="3">3</td><td>500</td><td>15</td><td>15</td><td>154.47</td><td>66.50</td><td>0</td><td>-</td><td>-</td><td>1</td><td>14.23</td><td>0.13</td></tr><tr><td>750</td><td>15</td><td>13</td><td>668.69</td><td>440.73</td><td>2</td><td>3636.50</td><td>0.03</td><td>0</td><td>85.51</td><td>0.15</td></tr><tr><td>1000</td><td>15</td><td>5</td><td>147.80</td><td>96.52</td><td>10</td><td>2667.40</td><td>0.04</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="3">6</td><td>500</td><td>15</td><td>6</td><td>551.33</td><td>516.74</td><td>9</td><td>2365.00</td><td>0.09</td><td>0</td><td>1011.70</td><td>0.44</td></tr><tr><td>750</td><td>15</td><td>5</td><td>255.40</td><td>365.84</td><td>10</td><td>993.20</td><td>0.25</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1000</td><td>15</td><td>1</td><td>661.00</td><td>1358.79</td><td>14</td><td>927.00</td><td>0.23</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="3">12</td><td>500</td><td>15</td><td>7</td><td>71.14</td><td>548.42</td><td>8</td><td>538.25</td><td>0.40</td><td>-</td><td>-</td><td>-</td></tr><tr><td>750</td><td>15</td><td>3</td><td>93.33</td><td>1556.86</td><td>12</td><td>237.08</td><td>0.54</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1000</td><td>15</td><td>0</td><td>-</td><td>-</td><td>15</td><td>133.53</td><td>0.87</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

Table 8 shows that the performance of the BPC algorithm diminishes as the size of the instances increases, both in terms of maximum path length and number of pairs. The BPC algorithm identifies 55 optima out of the 135 instances: their distribution among the instances with $L^P = 3, L^P = 6$ and $L^P = 12$ is 33, 12 and 10, respectively. Detailed results show that the time required to prove the optimality varies heavily even within instances characterised by the same values of $L^P$ and $|\mathcal{I}|$. Precisely, it increases with the number of
700

nodes of the branch-and-bound tree explored by the BPC algorithm. As an example, in the 13 instances solved to optimality with $L^P = 3$ and $|\mathcal{I}| = 750$, the computational time is less than five seconds when the instances are solved to optimality at the root node while it is larger than 100 seconds when more than 100 nodes are explored.

705

The BPC algorithm is not able to prove the optimality of 80 instances. However, they are left with a small optimality gap, on average, equal to 0.04%, 0.20% and 0.65% for the instances with $L^P = 3$, $L^P = 6$ and $L^P = 12$, respectively. We observe that exploring the branch-and-bound tree is rather inefficient in improving the upper bound. Indeed, the improvement of the upper bound w.r.t. the one obtained at the root node is on average equal to 0.07%.

710

The comparison with the results of Pansart et al. (2022) considers the subset of 45 instances with at most 750 incompatible pairs and path length up to six where their restricted master heuristic is tested. The results provided on those instances are worse than ours. Only one instance is solved to optimality, the remaining ones are left with an average optimality gap of 0.24% (see last three columns of the table).

715

Finally, we tested the code of the BP algorithm of Arslan et al. (2024) (the code is available online at https://github.com/jeremyomer/KidneyExchange.jl) on the instances of Pansart et al. (2022) characterised by values of the maximum length of the paths larger or equal to six. Our tests show that the algorithm does not scale on such large instances and we have not been able to get results within a time limit of one hour. We suppose this is due to the necessity of solving the ELPPLC to price out paths on such instances, while it was never the case when solving the PrefLib instances. In the BP algorithm of Arslan et al. (2024), the ELPPLC is solved with a mixed integer program with exponentially-many constraints. It turns out to be very time consuming to employ such an algorithm to solve the ELPPLC. Hence, we do not report any detailed results for the BP on these instances.

720
### 5.2.3. Results on the set of instances of Delorme et al. (2023)

Table 9 reports the results obtained on the instances of Delorme et al. (2023) when the objective function is the maximization of the number of transplants. A comparison with the results of Delorme et al. (2023) is also conducted. Precisely, Delorme et al. (2023) introduced the half-cycle formulation. To solve it, they devised an iterative procedure that allow for removal of variables by applying reduced cost variable fixing. They applied the same algorithmic scheme to solve PIEF with the objective to assess the performance of their formulation. Their experiments showed mixed results: they could not conclude whether one formulation was better than the other. The machine used by Delorme et al. (2023) has worse performance than ours. Hence, we ran the code of the two algorithms based on the half-cycle and PIEF formulations (the code of Delorme et al. (2023) is available at https://github.com/mdelorme2/Half_Cycle_Codes) on the instances we consider in this section. For each instance, we consider the best between the results obtained by the two algorithms and build the statistics in the columns of the table with heading Delorme et al. (2023) accordingly. Each row of the table corresponds to a subset of instances characterised by the same number of pairs and the same maximum length of the cycles. Columns are doubled to include all the instances in the table. The average time is computed considering only the instances solve to optimality. Observe that the iterative procedure of Delorme et al. (2023) either provides an optimal solution or may only return an upper bound.

The results of Table 9 clearly highlight the superiority of the BPC algorithm with respect to the destructive bound procedures of Delorme et al. (2023) for both the half-cycle and PIEF formulations. Indeed, the BPC algorithm solves to optimality each of the 840 instances in less than 600 seconds. More precisely, the computational time is less than 10 seconds for 838 instances. 813 instances are solved at the root node, the remaining ones by exploring 350 nodes of the branch-and-bound tree, on average. Conversely, the procedures of Delorme et al. (2023) suffers from lack of scalability. Indeed, the procedure based on the half-cycle formulation entails enumerating all the half-cycles of length up to $\lceil L^C \rceil + 1$ and the one based
<table><caption>Table 9: Results on the set of instances of Delorme et al. (2023) where the objective is the maximization of the number of transplants.</caption><thead><tr><th colspan="3">Instances</th><th colspan="2">BPC</th><th colspan="2">Delorme et al. (2023)</th><th colspan="3">Instances</th><th colspan="2">BPC</th><th colspan="2">Delorme et al. (2023)</th></tr><tr><th>L<sup>C</sup></th><th>|I|</th><th>#</th><th>#opt.</th><th>avg.t[s]</th><th>#opt.</th><th>avg.t[s]</th><th>L<sup>C</sup></th><th>|I|</th><th>#</th><th>#opt.</th><th>avg.t[s]</th><th>#opt.</th><th>avg.t[s]</th></tr></thead><tbody><tr><td rowspan="6">3</td><td>50</td><td>20</td><td>20</td><td>0.04</td><td>20</td><td>0.03</td><td rowspan="6">6</td><td>50</td><td>20</td><td>20</td><td>0.02</td><td>20</td><td>0.03</td></tr><tr><td>100</td><td>20</td><td>20</td><td>0.02</td><td>20</td><td>0.05</td><td>100</td><td>20</td><td>20</td><td>0.10</td><td>20</td><td>0.36</td></tr><tr><td>200</td><td>20</td><td>20</td><td>0.08</td><td>20</td><td>0.19</td><td>200</td><td>20</td><td>20</td><td>32.90</td><td>20</td><td>31.18</td></tr><tr><td>400</td><td>20</td><td>20</td><td>0.52</td><td>20</td><td>1.11</td><td>400</td><td>20</td><td>20</td><td>0.81</td><td>20</td><td>1059.71</td></tr><tr><td>600</td><td>20</td><td>20</td><td>1.72</td><td>20</td><td>3.94</td><td>600</td><td>20</td><td>20</td><td>2.15</td><td>0</td><td>902.63</td></tr><tr><td>800</td><td>20</td><td>20</td><td>2.70</td><td>20</td><td>10.01</td><td>800</td><td>20</td><td>20</td><td>3.48</td><td>0</td><td>-</td></tr><tr><td>1000</td><td>20</td><td>20</td><td>3.54</td><td>20</td><td>20.00</td><td>1000</td><td>20</td><td>20</td><td>5.69</td><td>0</td><td>-</td></tr><tr><td rowspan="6">4</td><td>50</td><td>20</td><td>20</td><td>0.04</td><td>20</td><td>0.02</td><td rowspan="6">7</td><td>50</td><td>20</td><td>20</td><td>0.02</td><td>20</td><td>0.04</td></tr><tr><td>100</td><td>20</td><td>20</td><td>0.04</td><td>20</td><td>0.06</td><td>100</td><td>20</td><td>20</td><td>0.17</td><td>20</td><td>0.88</td></tr><tr><td>200</td><td>20</td><td>20</td><td>0.62</td><td>20</td><td>0.55</td><td>200</td><td>20</td><td>20</td><td>0.31</td><td>20</td><td>92.09</td></tr><tr><td>400</td><td>20</td><td>20</td><td>0.67</td><td>20</td><td>13.15</td><td>400</td><td>20</td><td>20</td><td>0.90</td><td>15</td><td>1650.43</td></tr><tr><td>600</td><td>20</td><td>20</td><td>1.84</td><td>20</td><td>79.32</td><td>600</td><td>20</td><td>20</td><td>2.25</td><td>0</td><td>-</td></tr><tr><td>800</td><td>20</td><td>20</td><td>2.93</td><td>20</td><td>213.02</td><td>800</td><td>20</td><td>20</td><td>3.80</td><td>0</td><td>-</td></tr><tr><td>1000</td><td>20</td><td>20</td><td>4.20</td><td>20</td><td>676.85</td><td>1000</td><td>20</td><td>20</td><td>6.29</td><td>0</td><td>-</td></tr><tr><td rowspan="6">5</td><td>50</td><td>20</td><td>20</td><td>0.03</td><td>20</td><td>0.03</td><td rowspan="6">8</td><td>50</td><td>20</td><td>20</td><td>0.02</td><td>20</td><td>0.05</td></tr><tr><td>100</td><td>20</td><td>20</td><td>0.08</td><td>20</td><td>0.15</td><td>100</td><td>20</td><td>20</td><td>0.17</td><td>20</td><td>2.31</td></tr><tr><td>200</td><td>20</td><td>20</td><td>0.54</td><td>20</td><td>4.54</td><td>200</td><td>20</td><td>20</td><td>1.28</td><td>20</td><td>275.23</td></tr><tr><td>400</td><td>20</td><td>20</td><td>0.71</td><td>20</td><td>126.82</td><td>400</td><td>20</td><td>20</td><td>0.94</td><td>0</td><td>-</td></tr><tr><td>600</td><td>20</td><td>20</td><td>2.06</td><td>20</td><td>1434.90</td><td>600</td><td>20</td><td>20</td><td>2.25</td><td>0</td><td>-</td></tr><tr><td>800</td><td>20</td><td>20</td><td>3.46</td><td>1</td><td>3576.63</td><td>800</td><td>20</td><td>20</td><td>3.87</td><td>0</td><td>-</td></tr><tr><td>1000</td><td>20</td><td>20</td><td>4.69</td><td>0</td><td>-</td><td>1000</td><td>20</td><td>20</td><td>6.56</td><td>0</td><td>-</td></tr></tbody></table>

on PIEF needs to solve models of very large size. These operations become intractable when the size of the instance grows.

In Appendix E, we present the results obtained by the BPC algorithm where the objective function is the maximization of the medical benefit. We mention that these instances are much harder to solve, hence, in this experiments we consider only those with up to 400 incompatible pairs. Precisely, the BPC algorithm is able to solve 80% of those instances to optimality, leaving the remaining 20% with an acceptable optimality gap, 0.42%, on average.

### 5.2.4. Results on the KEP\_hard instances

Table 10 presents the comparison between the BPC algorithm and the HPIEF formulation by Dickerson et al. (2016) on the challenging instances of the set KEP\_hard. We implemented the formulation with the reductions proposed by Dickerson et al. (2016) and the preprocessing
<table><caption>Table 10: Results on the KEP \_hard set of instances.</caption><thead><tr><th rowspan="2">Instances</th><th colspan="3">solved instances</th><th colspan="6">unsolved instances</th></tr><tr><th>#opt.</th><th colspan="2">avg.t[s]</th><th>#</th><th>#gap</th><th>#</th><th>#gap</th><th colspan="2">avg.gap[%]</th></tr><tr><th>L<sup>C</sup></th><th>L<sup>P</sup></th><th>#</th><th>BPC</th><th>HPIEF</th><th>BPC</th><th>HPIEF</th><th>BPC</th><th>HPIEF</th><th>all res.</th><th>res.</th></tr></thead><tbody><tr><td rowspan="3">3</td><td>3</td><td>45</td><td>6</td><td>28</td><td>1748.81</td><td>586.26</td><td>39</td><td>39</td><td>17</td><td>17</td><td>0.09</td><td>0.15</td><td>0.14</td></tr><tr><td>6</td><td>45</td><td>2</td><td>10</td><td>2556.45</td><td>644.59</td><td>43</td><td>43</td><td>35</td><td>35</td><td>0.34</td><td>0.41</td><td>0.48</td></tr><tr><td>12</td><td>45</td><td>14</td><td>23</td><td>300.00</td><td>456.62</td><td>31</td><td>31</td><td>22</td><td>22</td><td>1.35</td><td>1.90</td><td>1.39</td></tr><tr><td rowspan="3">4</td><td>3</td><td>45</td><td>1</td><td>11</td><td>445.08</td><td>852.06</td><td>44</td><td>44</td><td>34</td><td>30</td><td>0.24</td><td>0.28</td><td>3.12</td></tr><tr><td>6</td><td>45</td><td>1</td><td>10</td><td>1456.29</td><td>900.03</td><td>44</td><td>44</td><td>35</td><td>29</td><td>0.32</td><td>0.33</td><td>0.92</td></tr><tr><td>12</td><td>45</td><td>14</td><td>17</td><td>232.60</td><td>937.42</td><td>31</td><td>31</td><td>28</td><td>17</td><td>1.04</td><td>0.77</td><td>1.58</td></tr><tr><td rowspan="3">5</td><td>3</td><td>45</td><td>0</td><td>6</td><td>-</td><td>2020.40</td><td>45</td><td>45</td><td>39</td><td>9</td><td>0.36</td><td>0.34</td><td>0.70</td></tr><tr><td>6</td><td>45</td><td>1</td><td>6</td><td>956.13</td><td>1155.20</td><td>44</td><td>44</td><td>39</td><td>9</td><td>0.40</td><td>0.46</td><td>0.73</td></tr><tr><td>12</td><td>45</td><td>14</td><td>11</td><td>324.60</td><td>1428.50</td><td>31</td><td>31</td><td>34</td><td>5</td><td>0.72</td><td>0.88</td><td>2.42</td></tr></tbody></table>

is unable to return an upper bound, as the optimisation process is barely started. However, it is able to return lower bounds even if their quality is poor. Such trend starts already on instances characterised by a maximal length of the cycles equal to four. In addition, the optimality gaps provided by the BPC algorithm are of very good quality, less than 1.4% on average for all the subset of instances. We stress that 307 out of the 352 instances not solved by the BPC algorithm have an optimality gap less than 1%. This means that even if the instances are not solved to optimality, the solutions are of high quality. Even the comparison of the quality of the gaps restricted to the instances where both approaches provide one, favors the BPC algorithm. Indeed, from the last two columns, we can see that the quality of such gaps are comparable on average on instances with $L^C = 3$. On larger instances, the BPC algorithm provides gaps which are around half of those provided by HPIEF, on average.

## 6. Conclusions

In this paper, we introduced an exact approach which is able to solve the Kidney Exchange Problem (KEP), especially for the most difficult instances where long chains of donations and maximization of the medical benefit are considered. Our approach is based on a Branch-Price-and-Cut (BPC) algorithm where the pricing problem is decomposed in subproblems to
price out variables associated with cycles and chains, respectively. We consider the subset-row inequalities to strengthen the relaxation, which are separated heuristically.

We test the BPC algorithm against the three algorithms recently proposed in the literature, namely, the restricted master heuristic of Pansart et al. (2022), the destructive bound procedure of Delorme et al. (2023) and the Branch-and-Price algorithm of Arslan et al. (2024) and against the well-known HPIEF formulation of Dickerson et al. (2016). The results reveal that the BPC algorithm positions itself in the literature as the only exact algorithm capable of solving efficiently instances with various characteristics and with different degrees of difficulty.

In addition, the impact of the valid inequalities is assessed: they reduce both the time and the exploration of the branch-and-bound tree when the instances are solved to optimality and they slightly improve the upper bound on the instances not solved to optimality.

From our results, there are still some instances difficult to solve, the ones with a large number of incompatible pairs, and long chains of donations where the objective is the maximization of the medical benefit. For such instances, the bottleneck seems to be the quality of the lower bound. Hence, an interesting future work would be to design a fast and efficient heuristic for the KEP instances with such characteristics. Having a very good lower bound would help to cut unpromising nodes in the branch-and-bound tree. Another interesting research direction may consider the development of a BPC algorithm based on the formulation introduced by Delorme et al. (2023), where the exponentially-many variables are the *half-cycles*.

## Acknowledgments

We thank Ayse Nur Arslan for having shared with us the detailed results of Arslan et al. (2024) with which we built Table 6.
References

Abraham, D.J., Blum, A., Sandholm, T., 2007. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges, in: Proceedings of the 8th ACM conference on Electronic commerce, pp. 295–304.

Arslan, A.N., Omer, J., Yan, F., 2024. Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price. Mathematical Programming Computation, 1–34.

Baldacci, R., Mingozzi, A., Roberti, R., 2011. New route relaxation and pricing strategies for the vehicle routing problem. Operations Research 59, 1269–1283. doi:10.1287/opre.1110.0975.

Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., Vance, P.H., 1998. Branch-and-price: Column generation for solving huge integer programs. Operations Research 46, 316–329. doi:10.1287/opre.46.3.316.

Biró, P., Haase-Kromwijk, B., Andersson, T., Ásgeirsson, E.I., Baltesová, T., Boletis, I., Bolotinha, C., Bond, G., Böhmig, G., Burnapp, L., et al., 2019. Building kidney exchange programmes in europe—an overview of exchange practice and activities. Transplantation 103, 1514.

Biró, P., van de Klundert, J., Manlove, D., Pettersson, W., Andersson, T., Burnapp, L., Chromy, P., Delgado, P., Dworczak, P., Haase, B., Hemke, A., Johnson, R., Klimentova, X., Kuypers, D., Costa, A.N., Smeulders, B., Spieksma, F., Valentín, M.O., Viana, A., 2021. Modelling and optimisation in european kidney exchange programmes. European Journal of Operational Research 291, 447–456. doi:10.1016/j.ejor.2019.09.006.

Delorme, M., García, S., Gondzio, J., Kalcsics, J., Manlove, D., Pettersson, W., Trimble, J., 2022. Improved instance generation for kidney exchange programmes. Computers & Operations Research 141, 105707. doi:10.1016/j.cor.2022.105707.
Delorme, M., Manlove, D., Smeets, T., 2023. Half-cycle: A new formulation for modelling kidney exchange problems. Operations Research Letters 51, 234-241.

Di Puglia Pugliese, L., Guerriero, F., 2013. A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62, 183-200. doi:10.1002/net.21511.

860

Dickerson, J.P., Manlove, D.F., Plaut, B., Sandholm, T., Trimble, J., 2016. Position-indexed formulations for kidney exchange, in: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 25-42.

Dror, M., 1994. Note on the complexity of the shortest path models for column generation in vrptw. Operations Research 42, 977-978.

865

Feillet, D., Dejax, P., Gendreau, M., Gueguen, C., 2004. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44, 216-229. doi:10.1002/net.20033.

Glorie, K., Wagelmans, A., van de Klundert, J., et al., 2012. Iterative branch-and-price for large multi-criteria kidney exchange. Econometric institute report 11, 2012.

870

Glorie, K.M., van de Klundert, J.J., Wagelmans, A.P., 2014. Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price. Manufacturing & Service Operations Management 16, 498-512.

Hoffman, K.L., Padberg, M., 1993. Solving airline crew scheduling problems by branch-and-cut. Management science 39, 657-682.

875

Jepsen, M., Petersen, B., Spoorendonk, S., Pisinger, D., 2008. Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations Research 56, 497-511. doi:10.1287/opre.1070.0449.

Kälble, T., Lucan, M., Nicita, G., Sells, R., Revilla, F.B., Wiesel, M., 2005. Eau guidelines on renal transplantation. European urology 47, 156-166.
Klimentova, X., Alvelos, F., Viana, A., 2014. A new branch-and-price approach for the kidney exchange problem, in: Computational Science and Its Applications–ICCSA 2014: 14th International Conference, Guimarães, Portugal, June 30–July 3, 2014, Proceedings, Part II 14, Springer. pp. 237–252.

Lam, E., Mak-Hau, V., 2020. Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange. Computers & Operations Research 115, 104852.

Lusby, R., Larsen, J., Ryan, D., Ehrgott, M., 2011. Routing trains through railway junctions: a new set-packing approach. Transportation Science 45, 228–245.

Mak-Hau, V., 2015. On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches. Journal of Combinatorial Optimization 33, 35–59. doi:10.1007/s10878-015-9932-4.

Marzi, F., Rossi, F., Smriglio, S., 2019. Computational study of separation algorithms for clique inequalities. Soft Computing 23, 3013–3027.

Mattei, N., Walsh, T., 2013. Preflib: A library for preferences http://www.preflib.org, in: Algorithmic Decision Theory: Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings 3, Springer. pp. 259–270.

Pansart, L., Cambazard, H., Catusse, N., 2022. Dealing with elementary paths in the kidney exchange problem. arXiv preprint arXiv:2201.08446.

PassMark Software, 2024. Cpu benchmarks. https://www.cpubenchmark.net/singleCompare.php. Accessed: 2024-12-29.

Pecin, D., Pessoa, A., Poggi, M., Uchoa, E., 2017. Improved branch-cut-and-price for capacitated vehicle routing. Mathematical Programming Computation 9, 61–100.

Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F., 2020. A generic exact solver for vehicle routing and related problems. Mathematical Programming 183, 483–523.
905

Plaut, B., Dickerson, J., Sandholm, T., 2016. Fast optimal clearing of capped-chain barter exchanges, in: Proceedings of the AAAI Conference on Artificial Intelligence.

Riascos-Álvarez, L.C., Bodur, M., Aleman, D.M., 2023. A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem. Manufacturing & Service Operations Management.

910

Roodnat, J., Zuidema, W., van de Wetering, J., de Klerk, M., Erdman, R., Massey, E., Hilhorst, M., IJzermans, J., Weimar, W., 2010. Altruistic donor triggered domino-paired kidney donation for unsuccessful couples from the kidney-exchange program. American Journal of Transplantation 10, 821-827.

Roth, A.E., Sönmez, T., Ünver, M.U., 2004. Kidney exchange. The Quarterly journal of economics 119, 457-488.

915

Roth, A.E., Sönmez, T., Ünver, M.U., 2007. Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. American Economic Review 97, 828-851.

Saidman, S.L., Roth, A.E., Sönmez, T., Ünver, M.U., Delmonico, F.L., 2006. Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges. Transplantation 81, 773-782.

920

Yoo, K.D., Kim, C.T., Kim, M.H., Noh, J., Kim, G., Kim, H., An, J.N., Park, J.Y., Cho, H., Kim, K.H., et al., 2016. Superior outcomes of kidney transplantation compared with dialysis: an optimal matched analysis of a national population-based cohort study between 2005 and 2008 in korea. Medicine 95.
# Appendix A. Theoretical results of Arslan et al. (2024)

The first result states that the subproblems to price the circuits reduce to an LPPLC. We remark that a non-elementary circuit is composed of at least two elementary circuits. Hence, if the solution of the LPPLC returns a positive reduced cost non-elementary circuit when solving problem [PP-C](i), $i \in \mathcal{I}$, then at least one of the elementary circuits composing it must have a positive reduced cost. We remark that such circuit might not be a solution of [PP-C](i), but of a different subproblem to price circuits starting with another incompatible pair. Hence, formulating the pricing problems for the circuits as a LPPLC is enough to detect positive reduced cost elementary circuits, even if it may not be the most positive one.

The second result is an original result of Arslan et al. (2024) and it identifies a subclass of the problem instances where it is possible to solve problem [PP-P] by dropping the elementarity requirement of the paths, i.e., [PP-P] reduces to a LPPLC, as well. Precisely, if $L^P \le L^C + 1$ and problems [PP-C](i), $i \in \mathcal{I}$, do not identify any circuit with a reduced cost larger than $-\beta$, then problem [PP-P] reduces to a LPPLC. Indeed, a non-elementary path of length $l$ contains a sub-tour of length at most $l-1$ which is composed of pairs only. Hence, if problems [PP-C](i), $i \in \mathcal{I}$, do not identify any circuit (of length at most $L^C$) with a reduced cost larger than $-\beta$, then [PP-P] will not provide any positive reduced cost path which is non-elementary. Note that the comparison is done with $-\beta$ and not zero since for the chains the $\beta$ term is subtracted from the weight of the outgoing arcs from altruistic donors.

We remark that if $L^P > L^C + 1$, solving the LPPLC on graph $\mathcal{H}^P$ provides an upper bound on the value of [PP-P] since the LPPLC is a relaxation of the ELPPLC.

# Appendix B. Multipliers of a SR inequality from a Cl inequality

If $|S| \le 5$, we assign the multipliers reported by Pecin et al. (2017) which are equal for all vertices in $S$, i.e., $p_i = p$ for all $i \in S$. Precisely, if $|S| \in \{3; 5\}$, we set $p = 1/2$ and if $|S| = 4$, we set $p = 2/3$.
In the following, we report the mixed-integer program we devise to determine the multipliers in case $|S| > 5$ or in case assigning those of Pecin et al. (2017) does not yield a violated SR inequality. For each $e \in W$, we introduce an integer non-negative variable $y_e^{int}$ and a continuous variable $y_e^{frac} \in [0, 0.99]$ to model the integer and fractional parts of coefficients of the $\lambda$ variables in SR inequality (8). Similarly, we introduce an integer non-negative variable $r^{int}$ and a continuous variable $r^{frac} \in [0, 0.99]$ to model the integer and fractional parts of the right hand-side of SR inequality (8). With an abuse of notation, we denote the continuous non-negative variables modelling the multipliers by $p_i$, $i \in S$. In addition, we denote by $\underline{m}$ and $\bar{m}$ two continuous non-negative variables to model the minimal and maximal values of the multipliers. Finally, we denote by $\alpha_1, \alpha_2 \in \mathbb{R}_{>0}$ two weights.

Given a fractional solution $\tilde{\lambda}$ and subset $S$, we propose the following mixed-integer program to determine the multipliers:

$$ [M(\tilde{\lambda}, S)] \min \alpha_1 \left( r^{int} - \sum_{e \in W} \tilde{\lambda}_e y_e^{int} \right) + \alpha_2 (\bar{m} - \underline{m}) \quad (B.1) $$

$$ \text{s.t.} \quad y_e^{int} = \sum_{i \in S} a_i^e p_i - y_e^{frac} \quad \forall e \in W \quad (B.2) $$

$$ r^{int} = \sum_{i \in S} p_i - r^{frac} \quad (B.3) $$

$$ \underline{m} \le p_i \le \bar{m} \quad \forall i \in S \quad (B.4) $$

$$ r^{int} \in \mathbb{Z}_{\ge 0}, \quad 0 \le r^{frac} \le 0.99 \quad (B.5) $$

$$ y_e^{int} \in \mathbb{Z}_{\ge 0}, \quad 0 \le y_e^{frac} \le 0.99 \quad \forall e \in W \quad (B.6) $$

$$ 0 \le p_i \le 1 \quad \forall i \in S \quad (B.7) $$

$$ \underline{m}, \bar{m} \in \mathbb{R}_{\ge 0}. \quad (B.8) $$

Objective (B.1) minimises two terms: the first one is the negative of the violation of the SR inequality w.r.t. solution $\tilde{\lambda}$ and the second one is the distance between the minimal and the maximal value of the multipliers to avoid them receiving extreme values. We set weights $\alpha_1$
and $\alpha_2$ so that the two objectives are managed hierarchically: among the solutions which maximize the violation, we look for the one that minimises the distance between the minimal and maximal multiplier. Constraints (B.2) model the value of variable $y_e^{int}$ for each $e \in W$. Similarly, Constraint (B.3) models the value of variable $r^{int}$. Constraints (B.4) compute the minimal and maximal values of the multipliers, respectively. Finally, Constraints (B.5), (B.6), (B.7) and (B.8) define the domains of the variables of the model.

Such model is solved by a commercial solver, its solution time is negligible in practice. If the value of the first objective is positive, a violated SR inequality is found for set $S$ with the values of multipliers variables $p_i$, $i \in S$.

# Appendix C. Accelerating techniques

**Preprocessing** Imposing length constraints on cycles and chains allows us to perform a preprocessing procedure to reduce the size of compatibility graph $G$. Such a procedure was introduced by Pansart et al. (2022) and is based on the Floyd-Warshall algorithm to compute the shortest path between each pair of vertices in a graph.

Riascos-Álvarez et al. (2023) proposed a procedure to reduce the number of pricing subproblems [PP-C](i), $i \in I$, to be processed in the pricing problem solution. In addition, the same procedure allows to reduce the size of pricing graphs $H_i^C$.

**Initialisation of RMP.** It is well known that column generation suffers from degeneracy which may slow down its convergence. A good initialisation of the set of columns helps in reducing this inconvenience. Hence, we enumerate at most 30000 exchange circuits and paths of length up to three and insert them in the RMP. Precisely, to ensure diversity, we generate at most 30000/|V| exchange circuits/paths starting at each incompatible pair/altruistic donor in the compatibility graph.

**Primal heuristic.** Embedding primal heuristics in a BPC algorithm helps in improving the lower bound and, consequently, reducing the integrality gap. We implement the so-called *restricted master heuristic*, i.e., we solve formulation [SP] restricted to the subset of variables
generated so far by means of a commercial solver. We call such a heuristic after the root
node is solved and at the end of the execution of the BPC algorithm, only if the time limit
is reached. We impose a time limit of 60 seconds for the first call and 1800 seconds for the
second one. Indeed, preliminary tests revealed that the restricted master heuristic struggles
to find good lower bounds on the most complex instances within reasonable computational
times. The results also showed that it was useless to call such a heuristic during the execution
of the BPC algorithm with smaller time limits: the lower bound did not improve within the
time limit, and the number of nodes of the branch-and-bound tree pruned due to the lower
bound was negligible.

**Tabu list.** As in Arslan et al. (2024), when a pricing subproblem [PP-C](i), i ∈ I, does not provide any positive reduced cost circuit, we insert such subproblem in a tabu list. All subproblems in the tabu list are not solved in the following column generation iterations. They are solved only when subproblem [PP-P] does not provide any positive reduced cost path to ensure the correctness of the column generation procedure.

**Appendix D. Impact of the valid inequalities**

In this section, we evaluate the impact of the valid inequalities presented in Section 4.4, namely the SR inequalities heuristically separated from either the CI inequalities (9) or the OH inequalities (10).

Precisely, we first assess their impact at the root node of the branch-and-bound tree, then
on the entire tree. We conduct this analysis on the most challenging instances, namely the
135 instances of Pansart et al. (2022) with a number of pairs greater than or equal to 500.
The objective is the maximization of the medical benefit. Although the instances of Delorme
et al. (2023) with a number of pairs greater than 200 are also challenging when the medical
benefit is maximized, we choose to report only the results for the 135 challenging instances
of Pansart et al. (2022) as they are similar to the ones obtained on the set of Delorme et al.
(2023).
In order to perform this analysis, we define the following four configurations of the BPC algorithm: BPC: no valid inequalities is separated in the course of the algorithm; BPC+Cl: only clique inequalities (9) are separated; BPC+OH: only odd-hole inequalities (10) are separated; BPC+Cl+OH: all valid inequalities are separated.

First, in Table D.11, we compare the results obtained by the four configurations at the end of the solution of the root node of the branch-and-bound tree. The rows of the table correspond to the four configurations. The first column reports the name of the configuration (configuration). The additional column heading used in this table is: the average gap at the root node (avg.impr. cl.gap[%]), expressed as a percentage of the gap at the root node when no cuts are added, that is computed as $100(UB^{VI} - LB^*)/(UB^{root} - LB^*)100$, where $UB^{root}$ and $UB^{VI}$ are the upper bounds obtained, respectively, before and after the valid inequalities and $LB^*$ is the best lower bound among those returned by the four configurations. We chose to assess the impact of the valid inequalities by measuring how much they help to close the optimality gap rather than the average upper bound improvement because the upper bounds at the root node are already of very good quality. Hence, when adding the valid inequalities, the upper bounds can decrease only by a small amount that does not reflect the real impact of the inequalities. With this measure, the smaller the value, the better the performance of the inequalities.

<table><caption>Table D.11: Comparison of four configurations of the BPC algorithm at the root node of the branch-and-bound tree.</caption><thead><tr><th>configuration</th><th>#opt.</th><th>avg.impr. cl.gap[%]</th><th>avg.t[s]</th><th>avg.#Cl</th><th>avg.#OH</th><th>avg.t[s] sep.</th></tr></thead><tbody><tr><td>BPC</td><td>2</td><td>100.00</td><td>82.83</td><td>-</td><td>-</td><td>-</td></tr><tr><td>BPC+Cl</td><td>5</td><td>87.03</td><td>87.46</td><td>8.33</td><td>-</td><td>0.30</td></tr><tr><td>BPC+OH</td><td>14</td><td>75.09</td><td>183.23</td><td>-</td><td>19.69</td><td>99.65</td></tr><tr><td>BPC+Cl+OH</td><td>14</td><td>73.97</td><td>176.54</td><td>9.79</td><td>13.84</td><td>81.56</td></tr></tbody></table>

From the root node analysis, it is clear that separating the Cl and/or the OH inequalities is beneficial w.r.t. configuration BPC. Indeed, when the inequalities are considered, the number of solution proven to be optimal increases: it grows to five with BPC+Cl and to 14 with the configurations involving the OH inequalities. In addition, adding the valid
inequalities help in reducing the gap at the root node w.r.t. BPC. The best configuration is when separating all inequalities (BPC+Cl+OH) that leads to a gap of 73.97% w.r.t. the one obtained by BPC. Note that only separating OH inequalities also leads to a very good root node gap (75.09% w.r.t. the one at the root node), while only separating Cl inequalities has worse performance (87.03% w.r.t. the one at the root node). The price to pay with the inequalities is an increase of the computational time, which is mostly due to the time required by the separation procedures. Precisely, separating the Cl inequalities is much faster than separating the OH inequalities: the separation time in BPC+Cl is on average 0.30 seconds whereas the one of BPC+OH is 99.65 seconds. This difference in the time taken by the algorithm can be explained as follows: the procedure used to separate Cl inequalities (see Section 4.4.1) is designed as a very fast heuristic, whereas the procedure to separate OH inequalities (see Section 4.4.2) is designed as an exact algorithm which is turned into a good quality heuristic by considering 30% of starting vertices, that is still time consuming.

In Table D.12, we compare the results obtained by the four configurations when the instances are solved to optimality. The rows and the first column of the table are the same as those of Table D.11. The second column reports the number of additional instances solved to optimality by each configuration in addition to the 50 instances solved to optimality by all configurations (#add.opt.).

<table><caption>Table D.12: Comparison of four configurations of the BPC algorithm on the instances solved to optimality.</caption><thead><tr><th>configuration</th><th>#add.opt.</th><th>avg.#nodes</th><th>avg.t[s]</th><th>avg.#Cl</th><th>avg.#OH</th><th>avg.t[s] sep.</th></tr></thead><tbody><tr><td>BPC</td><td>4</td><td>922.82</td><td>372.55</td><td>-</td><td>-</td><td>-</td></tr><tr><td>BPC+Cl</td><td>3</td><td>411.78</td><td>288.72</td><td>25.36</td><td>-</td><td>1.87</td></tr><tr><td>BPC+OH</td><td>6</td><td>282.72</td><td>261.23</td><td>-</td><td>26.14</td><td>14.32</td></tr><tr><td>BPC+Cl+OH</td><td>5</td><td>200.02</td><td>224.62</td><td>20.48</td><td>18.76</td><td>12.87</td></tr></tbody></table>

The results of the root node analysis are confirmed: including the valid inequalities is beneficial. First, the inequalities allow to solve more instances to optimality: 54 with BPC+Cl, 56 with BPC+OH and 55 with BPC+Cl+OH. In addition, on the 50 instances solved to optimality by all four configurations, adding the inequalities permit to reduce: (i) the
1060 number of the nodes of the branch-and-bound tree by a factor of at least 3.2, on average; (ii) the computational time by a factor of at least 1.5, on average. The best configuration is BPC+Cl+OH: these two reduction factors become 9.6 and 1.8, respectively. The number of separated valid inequalities is on the order of tens for all the configurations where they are considered. The separation time follows the same trend as in Table D.11.

1065 Finally, Table D.13 compares the results obtained by the four configurations when the instances are not solved to optimality. The rows and the first column of the table are the same as those of Table D.11. The second column reports the number of additional instances not solved to optimality by each configuration in addition to the 77 instances not solved to optimality by all configurations (#add.noOpt.). The following seven columns report statistics regarding the 77 instances not solved to optimality by all configurations. Precisely, heading avg.LB/avg.UB reports the average lower/upper bound when the time limit is reached.

<table><caption>Table D.13: Comparison of four configurations of the BPC algorithm on the instances not solved to optimality.</caption><thead><tr><th>configuration</th><th>#add.noOpt.</th><th>avg.#nodes</th><th>avg.LB</th><th>avg.UB</th><th>avg.gap[%]</th><th>avg.#Cl</th><th>avg.#OH</th><th>avg.t[s] sep.</th></tr></thead><tbody><tr><td>BPC</td><td>4</td><td>1986.77</td><td>39562.21</td><td>39747.03</td><td>0.42</td><td>-</td><td>-</td><td>-</td></tr><tr><td>BPC+Cl</td><td>5</td><td>1246.13</td><td>39556.93</td><td>39746.01</td><td>0.43</td><td>92.36</td><td>-</td><td>11.96</td></tr><tr><td>BPC+OH</td><td>2</td><td>1339.88</td><td>39564.84</td><td>39745.75</td><td>0.41</td><td>-</td><td>15.57</td><td>164.16</td></tr><tr><td>BPC+Cl+OH</td><td>3</td><td>1115.62</td><td>39579.32</td><td>39745.06</td><td>0.38</td><td>85.52</td><td>10.78</td><td>135.24</td></tr></tbody></table>

The benefit of the valid inequalities on the instances not solved to optimality is less evident. Overall the configurations involving the inequalities explore on average less nodes of the branch-and-bound tree w.r.t. BPC. The explanation is that when valid inequalities are active in the RMP, the pricing of the circuits is modelled as an ELPPRC (i.e. a NP-hard problem) and can no longer be modelled as an LPPLC (i.e. a polynomial problem). Therefore, each call to pricing is more time consuming when valid inequalities are active.

In addition, it can be observed that the SR inequalities arising from the OH inequalities are few, and even in the case where only OH inequalities are separated, this number (15.57 on average) is far from the maximum of 100 valid inequalities to be added in the model. On the contrary, there are many SR inequalities arising from the Cl inequalities. This can
be explained by the fact that only CI inequalities are separated after solving the root node of the branch-and-bound tree. The time spent in the separation of the inequalities is small w.r.t. the total time (less than 3 minutes on average out of one hour). As observed at the root node, when separating only CI inequalities the separation time is negligible, only a few seconds.

1085

Finally, in the four configurations the average lower bound, upper bound and optimality gap are rather similar. For the lower bounds, they are slightly worse for the configurations involving the separation of the CI inequalities, and slightly better for the configurations BPC+OH and BPC+CI+OH. The quality of the lower bound comes from the final call to the primal heuristic where a commercial solver solves formulation [SP] restricted to the columns generated so far. As already mentioned, such formulation is very difficult to solve, and even with a 30 minutes time limit, the reported lower bound is usually not proven optimal. Hence, there is no direct correlation between the use of valid inequalities and the quality of the lower bounds. When looking at the average upper bounds, although less nodes are explored, the average upper bound of the configurations with the inequalities is slightly better than the one of BPC. In this respect, the best configuration is BPC+CI+OH. This balance between worsening the lower bounds and improving the upper bounds yields the optimality gap to be comparable among all the configurations. Again, the best configuration in this respect is BPC+CI+OH.

1090

1095

1100

## Appendix E. Results on the instances of Delorme et al. (2023) with obj.=MB

In Table E.14, we present the results obtained by the BPC algorithm where the objective function is the maximization of the medical benefit. Delorme et al. (2023) do not test their procedure in the case of maximization of the medical benefit. The rows and the first three columns of the table have the same meaning as those in Table 9. We consider only instances characterised by a number of pairs up to 400.

1105

From the results of Table E.14, it can be observed that the type of the objective function has a huge impact on the results. Maximizing the medical benefit makes the instances
<table><caption>Table E.14: Results on the set of instances of Delorme et al. (2023) where the objective is the maximization of the medical benefit.</caption><thead><tr><th colspan="3">Instances</th><th colspan="4">BPC results</th><th colspan="3">Instances</th><th colspan="4">BPC results</th></tr><tr><th>L<sup>C</sup></th><th>|I|</th><th>#</th><th>#</th><th>solved instances<br>avg.<br>#nodes</th><th>avg.t[s]</th><th>#</th><th>solved instances<br>avg.<br>#nodes</th><th>avg.<br>gap[%]</th><th>L<sup>C</sup></th><th>|I|</th><th>#</th><th>#</th><th>solved instances<br>avg.<br>#nodes</th><th>avg.t[s]</th><th>#</th><th>solved instances<br>avg.<br>#nodes</th><th>avg.<br>gap[%]</th></tr></thead><tbody><tr><td rowspan="4">3</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.04</td><td>0</td><td>-</td><td>-</td><td rowspan="4">6</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.02</td><td>0</td><td>-</td><td>-</td></tr><tr><td>100</td><td>20</td><td>20</td><td>1.10</td><td>0.02</td><td>0</td><td>-</td><td>-</td><td>100</td><td>20</td><td>20</td><td>8.50</td><td>0.73</td><td>0</td><td>-</td><td>-</td></tr><tr><td>200</td><td>20</td><td>20</td><td>1.40</td><td>0.09</td><td>0</td><td>-</td><td>-</td><td>200</td><td>20</td><td>19</td><td>627.47</td><td>275.26</td><td>1</td><td>7391.00</td><td>0.03</td></tr><tr><td>400</td><td>20</td><td>20</td><td>23.40</td><td>4.79</td><td>0</td><td>-</td><td>-</td><td>400</td><td>20</td><td>0</td><td>-</td><td>-</td><td>20</td><td>779.35</td><td>0.51</td></tr><tr><td rowspan="4">4</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.04</td><td>0</td><td>-</td><td>-</td><td rowspan="4">7</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.02</td><td>0</td><td>-</td><td>-</td></tr><tr><td>100</td><td>20</td><td>20</td><td>2.50</td><td>0.07</td><td>0</td><td>-</td><td>-</td><td>100</td><td>20</td><td>20</td><td>17.05</td><td>2.70</td><td>0</td><td>-</td><td>-</td></tr><tr><td>200</td><td>20</td><td>20</td><td>56.35</td><td>6.72</td><td>0</td><td>-</td><td>-</td><td>200</td><td>20</td><td>19</td><td>1415.79</td><td>882.10</td><td>1</td><td>6225.00</td><td>0.01</td></tr><tr><td>400</td><td>20</td><td>9</td><td>1501.44</td><td>661.98</td><td>11</td><td>8396.82</td><td>0.08</td><td>400</td><td>20</td><td>0</td><td>-</td><td>-</td><td>20</td><td>437.35</td><td>0.56</td></tr><tr><td rowspan="4">5</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.02</td><td>0</td><td>-</td><td>-</td><td rowspan="4">8</td><td>50</td><td>20</td><td>20</td><td>1.00</td><td>0.02</td><td>0</td><td>-</td><td>-</td></tr><tr><td>100</td><td>20</td><td>20</td><td>3.00</td><td>0.19</td><td>0</td><td>-</td><td>-</td><td>100</td><td>20</td><td>20</td><td>8.65</td><td>2.81</td><td>0</td><td>-</td><td>-</td></tr><tr><td>200</td><td>20</td><td>20</td><td>153.80</td><td>35.55</td><td>0</td><td>-</td><td>-</td><td>200</td><td>20</td><td>17</td><td>371.35</td><td>353.96</td><td>3</td><td>3227.00</td><td>0.09</td></tr><tr><td>400</td><td>20</td><td>0</td><td>-</td><td>-</td><td>20</td><td>2175.25</td><td>0.31</td><td>400</td><td>20</td><td>0</td><td>-</td><td>-</td><td>20</td><td>320.75</td><td>0.56</td></tr></tbody></table>

much harder to be solved by the BPC algorithm. The BPC algorithm still provides 384 optima out of the 480 instances. However, contrary to the results where the objective is to maximize the number of transplants, those optima are obtained by exploring more nodes of the branch-and-bound tree (167, on average) and by spending more time (91 seconds, on average). The 96 instances not solved to optimality are characterised by either 200 or 400 pairs and a maximum length of the cycles at least equal to four. None of the instances with 400 pairs and maximum length greater or equal to five is solved to optimality. Nonetheless, the average optimality gap when the time limit is reached is small, 0.42%, on average. The same behaviour was observed when considering instances with more than 400 pairs.