Matteo Petris
email: petris@essec.edu

Claudia Archetti
email: archetti@essec.edu

Diego Cattaruzza
email: diego.cattaruzza@centralelille.fr

Maxime Ogier
email: maxime.ogier@centralelille.fr

Frédéric Semet
email: frederic.semet@centralelille.fr

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

Keywords: Kidney exchange, altruistic donors, elementary paths, elementary circuits, Branch-Price-and-Cut

In this paper, we study a Kidney Exchange Problem (KEP) with altruistic donors and incompatible patientdonor 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.

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. We decompose the pricing problem into a subproblem to price out the path variables and several subproblems to price out the circuit variables. The former can be formulated as an Elementary Longest Path Problem with Length Constraints (ELPPLC), that is NP-hard in the strong sense, and solved by a label correcting dynamic programming algorithm. Conversely, the latter can be formulated as a Longest Path Problem with Length Constraints (LPPLC) and solved in polynomial time. We strengthen the linear relaxation via the inclusion of a family of non-robust inequalities, namely, the subset-row inequalities. We separate them heuristically by looking for violated clique and odd-hole inequalities which are then transformed into subset-row inequalities.

We perform extensive computational experiments to assess the performances of the BPC algorithm on three sets of instances from the literature. On the easiest instances, the BPC algorithm yields comparable results with the literature; while on the other two sets it clearly outperforms the previous results. Hence, contrary to the existing literature, the BPC algorithm is the only exact approach able to effectively solve various and difficult instances with both objective functions and long chains and cycles.

Introduction

Kidneys are essential organs for the survival of the human body: (i) they produce the urine by filtering the blood to expel wastes and toxins; (ii) they play a role in maintaining the homeostasis of the body by regulating the acid-base balance, and the concentrations of electrolyte; (iii) they secrete several hormones responsible, for example, of the maturation of the red blood cells or of regulating the blood pressure.

Unfortunately, kidneys may suffer from chronic diseases or failures which prevent them to perform their usual tasks. According to [START_REF] Kovesdy | Epidemiology of chronic kidney disease: an update 2022[END_REF], more than 10% of the worldwide population was affected by such diseases in 2022.

Chronic kidney diseases or failures are often treated by dialysis or transplantation [START_REF] Levey | Chronic kidney disease[END_REF]. Transplantation is 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 (see, e.g., Yoo et al., 2016;[START_REF] Axelrod | An economic assessment of contemporary kidney transplant practice[END_REF].

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 [START_REF] Kälble | Eau guidelines on renal transplantation[END_REF]. 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. In 2021, more than the 60% of the 92 532 worldwide transplants involved a deceased donor1 . However, patients must register to a waiting list and might wait several years before (possibly) receiving a kidney from a compatible deceased donor [START_REF] Lentine | Optn/srtr 2021 annual data report: Kidney[END_REF]. Transplants from living donors may help patients in receiving a kidney more promptly [START_REF] Nemati | Does kidney transplantation with deceased or living donor affect graft survival?[END_REF]. Such transplants are possible because one functioning kidney is enough for a human being to conduct a healthy life. The organisation of transplants from living donors is more complex than the one from deceased donors. Indeed, patients need to find a willing and compatible donor in their circle of acquaintances, that is often not easy.

Most of the times, a patient is capable of finding a willing donor with whom it is unfortunately not compatible.

However, together, they can form an incompatible patient-donor pair and join a kidney exchange programme (see [START_REF] Rapaport | The case for a living emotionally related international kidney donor exchange registry[END_REF] and Roth et al. (2004)). Such programmes 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 [START_REF] Biró | Building kidney exchange programmes in europe-an overview of exchange practice and activities[END_REF]. However, we report the breakthrough cases of cycles involving five, six or seven pairs in the Czech-Austrian kidney exchange programme (Viklicky et al., 2020). In recent years, altruistic donors, i.e., donors who are not paired with any patient, may join the pool of a kidney exchange programme (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, although usually limited by regulations, is larger than the one of the cycles2 .

Typically, kidney exchange programmes are run regularly (e.g., each one, three, or four months depending on the country regulation [START_REF] Biró | Modelling and optimisation in european kidney exchange programmes[END_REF]) 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 maximised.

Recently, [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF] and [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] proposed two Branch-and-Price (BP) algorithms to solve the same problem. Both works employ an extended formulation based on the Extended Edge Formulation introduced in [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF]. The exponentially-many variables correspond to cycles and chains. Hence, in the column generation procedure, the pricing problem is decomposed in several subproblems to price out variables associated with cycles or chains. All subproblems can be formulated as an Elementary Longest Path Problem with Length Constraints (ELPPLC) which is strongly NP-hard. However, the pricing subproblems associated with cycles can be solved in polynomial time. Indeed, the elementarity constraints can be dropped as they can be formulated as a Longest Path Problem with Length Constraints (LPPLC).

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 (which corresponds to the case where each transplant is associated with a value of the medical benefit equal to one). Precisely, we propose a Branch-Price-and-Cut (BPC) algorithm based on the cycle formulation for the KEP introduced by Roth et al. (2007) where the exponentially-many variables correspond to cycles and chains. We exploit the theoretical results of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] to solve as few as possible ELPPLCs. However, instead of calling an integer program to solve the ELPPLC in the case of the chains, as done by [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF], 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 [START_REF] Jepsen | Subset-row inequalities applied to the vehiclerouting problem with time windows[END_REF]. Usually, in the literature, only small cardinality subset-row inequalities are separated heuristically by enumeration. However, given the size of the KEP instances, adopting such 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. We also propose two original procedures to transform those inequalities 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 identified three different sets of instances for the KEP in the literature, each of them with different characteristics: (i) the PrefLib dataset with small cycles and chains and maximisation of the number of transplants (medical benefit set to value one) where [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] report the state-of-art results, (ii) the set of instances introduced by [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with long chains, and (iii) the set of instances introduced by [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] with long cycles only. The more challenging instances are the ones considering either long chains or the maximisation of the medical benefit (i.e. not all values set to one).

Contrary to the solution approaches 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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] struggles on instances with long chains and maximisation of the medical benefit as it will be discussed in Section 5.3.2. The approach of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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, their approach is not able to prove optimality when branching is required, that is especially on the largest instances. Finally, the results reported by [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] show that their approach already struggles on instances with maximal length of the cycles equal to six and the maximisation of the number of transplants, thus preventing it to efficiently scale on instances with long cycles/chains or the maximisation of the medical benefit.

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. Finally, in Section 5, we report and analyse the results obtained by the BPC algorithm on three sets of benchmark instances.

Literature review

In this section, we survey the existing literature on solution approaches for the Kidney Exchange Problem (KEP). Roth et al. (2005) study the KEP with cycles of length two only. Such variant of the KEP can be reduced to a Maximum Weighted Matching Problem and thus solved in polynomial time by, e.g., the Edmond's algorithm [START_REF] Edmonds | Maximum matching and a polyhedron with 0, 1-vertices[END_REF]. However, the KEP with cycles of length larger than two (and chains of arbitrary length) is proven to be NP-hard (Roth et al., 2007;[START_REF] Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges[END_REF]. For this reason, several formulations and solution methods have been proposed through the years.

In the following we review the main formulations proposed for the KEP with cycles only. Roth et al. (2007) introduced the edge formulation for the KEP, a first formulation with an exponential number of constraints and a polynomial number of variables w.r.t. the size of the instance. Whereas the first extended formulation, the cycle formulation, was introduced by Roth et al. ( 2007) and [START_REF] Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges[END_REF]. The authors proved that the cycle formulation dominates the edge formulation in terms of linear relaxation. As a solution method, they considered a column generation approach where the pricing problem is solved by enumeration. [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF] proposed the first compact formulation for the KEP with cycles only, the extended edge formulation. [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF] presented the disaggregated cycle formulation, a variant of the cycle formulation where the set of cycles is decomposed in subsets, one per each patient-donor pair, containing the cycles starting at that pair. Both [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF] and [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF] adopt an idea to break symmetries: a cycle starting at pair i does not contain pairs with an index lower than i.

In addition, [START_REF] Dickerson | Position-indexed formulations for kidney exchange[END_REF] introduced the position-indexed edge formulation, a compact formulation which achieves linear relaxation bounds equivalent to the ones of the cycle formulation. More recently, [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] 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 maximise the number of transplants. Such formulation has less 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 variable-fixing strategy.

Precisely, first, an upper bound on the maximum number of transplants is obtained by solving the linear relaxation of the formulation. Then, an iterative procedure starts: the half-cycle formulation is solved by a commercial solver by imposing that the solution value is equal to the upper bound; if an integer solution is found the procedure stops, otherwise the upper bound is decreased by one and the procedure repeats. They tested instances with up to 1000 incompatible pairs and cycles of length up to eight. All these formulations can be easily adapted to solve the KEP with altruistic donors and thus with chains. For example, [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] extended the cycle formulation to include the chains, as well. The interested reader may refer to [START_REF] Mak-Hau | On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches[END_REF] for a survey on formulations for the KEP up to 2015.

For scalability reasons, several works focus on developing column generation approaches for the KEP.

As already mentioned, [START_REF] Abraham | Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges[END_REF] presented the first Branch-and-Price (BP) algorithm to solve the KEP with cycles only. The works of [START_REF] Glorie | Iterative branch-and-price for large multi-criteria kidney exchange[END_REF], [START_REF] Glorie | Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price[END_REF], [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF] and Plaut et al. (2016a) developed BP algorithms to solve the KEP with both cycles and chains. However, [START_REF] Plaut | Hardness of the pricing problem for chains in barter exchanges[END_REF] proved that the algorithms of [START_REF] Glorie | Iterative branch-and-price for large multi-criteria kidney exchange[END_REF], [START_REF] Glorie | Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price[END_REF]Plaut et al. (2016a) were not correct. In addition, [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF] did not provide any computational experiments with KEP instances with chains. Based on the work of [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF], [START_REF] Lam | Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange[END_REF] 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. However, the considered valid inequalities are rather ineffective in strengthening the linear relaxation. [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] is the first column generation approach capable of dealing with both cycles and chains. The objective is to maximise 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. In their approach the cycles are enumerated and the chains are detected via the solution of the pricing problem, namely the ELPPLC.

Precisely, they proposed new heuristic algorithms to solve the pricing problem. The correctness of their algorithm is based on the solution of the ELPPLC via an exact dynamic programming algorithm. [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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 [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF]. The authors developed a BP algorithm based on the disaggregated cycle formulation of [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF] where the element of novelty is solving the pricing problem with a three-steps approach. Precisely, the pricing subproblems associated with the cycles and chains are formulated as dynamic programs and Mixed Integer Programs (MIPs). The first step of the pricing problem solves restricted versions of the dynamic programs with the aim of quickly finding positive reduced cost cycles or chains. If the first step fails, the second step solves the ELPPLC to price out the chains via the solution of a MIP model with dynamic inclusion of cuts for subtours elimination constraints. If the second step fails, the third step solves the pricing for cycles via enumeration until a certain time limit, and then via the solution of a MIP formulation for the LPPLC. In addition, the authors exploited the idea of [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF] to represent each cycle by its vertex with the lowest index, that permits to apply a preprocessing procedure which reduces the subset of cycles to consider in the formulation of [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF]. Consequently, the number of the pricing subproblems associated with the cycles is heavily reduced. Their approach is tested on the instances of the PrefLib dataset with cycles and chains of maximum length equal to three or four and chains of maximum length from three to six. The objective is the maximisation of the number of transplants.

The large majority of the instances are solved to optimality at the root node. However, their results are outperformed by the BP algorithm of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF]. Precisely, the BP algorithm of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] builds on the one of [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF] 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 more elementary positive reduced cost chain exist. [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] 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 [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF], 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.

The BPC algorithm we propose in this work exploits the preprocessing of [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF] to reduce the number of the pricing subproblems associated with the cycles and the interesting properties of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] 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 in opposition to the integer program used by [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF].

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

Problem formulation

Let I be the set of incompatible patient-donor pairs and let D be the set of altruistic donors. The KEP can be defined on a directed weighted graph G = (V, A) referred to as compatibility graph. Vertex set V = I ∪ D contains a vertex for each incompatible patient-donor pair of I and each altruistic donor of D.

The arcs in A model all the possible transplants between donors and patients. Hence, arc set A contains an arc (i, j) from vertex i ∈ V to patient-donor pair j ∈ 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) ∈ A representing the utility (medical benefit) of the associated transplant. Cycles and chains of kidney exchanges between donors and patients are modelled in graph 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 circuit or path. In this respect, we call an exchange circuit an elementary circuit in graph G of length at most L C > 1. Similarly, we call an exchange path an elementary path in graph G of length at most L P > 1, starting with a vertex in 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 := (i,j)∈A(e) W ij , where A(e) is the set of arcs traversed by e.

Finally, we define an exchange scheme as a union of pairwise vertex-disjoint exchanges 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 V. Remark that if all weights W ij , (i, j) ∈ A, are set to one, the objective of the KEP is to maximise the number of transplants. In what follows, with abuse of language, we refer to an exchange circuit or path with the term exchange.

Example 1. We consider the following toy instance of the KEP. The compatibility graph G = (V, A) is shown in Figure 1. Vertex set V = I ∪ D is composed of two altruistic donors D = {1, 2} and seven patientdonor pairs 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), andone cycle (6, 7, 6). Note that the maximisation of the medical benefit favours quality over quantity, indeed, patient-donor pair 9 is not served even if it exists a feasible solution that would serve all patient-donor pairs.

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. We now report the set packing formulation proposed in [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] to model the KEP.

We denote by E = E C ∪ E P the set of the exchanges in graph G, where E C (E P ) denotes the set of the exchange circuits (paths) in graph G. Let a e i be a binary parameter equal to one if vertex i ∈ V is involved in exchange e ∈ E and zero otherwise. For each exchange e ∈ E, we define a binary variable λ 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:

[SP] max e∈E W e λ e (1)
s.t. e∈E a e i λ e ≤ 1 ∀i ∈ V (2) e∈E λ e ≤ |V| 2 (3) λ e ∈ {0, 1} ∀e ∈ E. (4)
Objective function (1) maximises 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. 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 bound may be used as a termination condition in the column generation procedure (see [START_REF] Desrosiers | A primer in column generation[END_REF], for more details). Finally, Constraints (4) define variables λ e as binary.

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

A Branch-Price-and-Cut algorithm

Formulation [SP] is an integer model defined over exponentially-many variables λ e , e ∈ E. We solve

[SP] by means of an exact algorithm based on the Branch-Price-and-Cut (BPC) paradigm [START_REF] Barnhart | Branch-and-price: Column generation for solving huge integer programs[END_REF]. BPC algorithms are variants of the branch-and-bound algorithm where, at each node of the branchand-bound tree, the linear relaxation of [SP] is solved via a column generation procedure [START_REF] Desrosiers | A primer in column generation[END_REF]. 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 valid inequalities are detected, branching rules are applied to ensure the correctness of the BPC algorithm.

The outline of this section is as follows. Section 4.1 is devoted to the column generation procedure we employ in our BPC algorithm. 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. Finally, the branching strategies are discussed in Section 4.5.

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 λ 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 maximisation problem. When the pricing problem proves that no positive reduced cost variables exist, the current solution of the RMP is then 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.

[RMP(E ′ )] max

e∈E ′ W e λ e (5) s.t. e∈E ′ a e i λ e ≤ 1 ∀i ∈ V (6) e∈E ′ λ e ≤ |V| 2 (7) λ e ≥ 0 ∀e ∈ E ′ . (8)

Pricing problem formulation

Let π i ≥ 0, i ∈ V and β ≥ 0 be the dual prices associated with Constraints ( 6) and ( 7), respectively. The reduced cost of a λ e variable is:

We = W e - i∈V a e i π i -β.
The pricing problem reads as follows:

[PP] max{ We : e ∈ E}.

We observe that exchange set E can be partitioned as:

E = E C ∪ E P = i∈I E C i ∪ E P ,
where E C i is the set of the exchange circuits starting and ending at incompatible pair i ∈ I. Hence, pricing problem [PP] can be decomposed in |I| + 1 independent subproblems:

[PP-C](i) max{ We : e ∈ E C i }, i ∈ I [PP-P] max{ We : e ∈ E P }.
The aim of problem [PP-C](i) is to determine the most positive reduced cost variable λ e , e ∈ E C i , associated with exchange circuits starting and ending in i ∈ 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 λ e , e ∈ E P or state that no positive reduced cost variable exists.

In the following, we show that problems First, we formally define the ELPPLC having as a reference [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF]. Let H = (N , F) be a directed weighted graph, where the weights associated with the arcs (i, j) ∈ F are denoted by Wij . The objective of the ELPPLC is to find an elementary path e * in graph H starting at a given vertex s ∈ N , ending at a given vertex t ∈ N and such that its weight We * = (i,j)∈A(e * ) Wij is maximum and its length is less than or equal to L > 0. The ELPPLC is NP-hard in the strong sense (see [START_REF] Dror | Note on the complexity of the shortest path models for column generation in vrptw[END_REF]).

[PP-C](i), i ∈ I,
Now, we describe the topology of the graph H arising when pricing circuits and paths.

Let i ∈ I be an incompatible patient-donor pair. To model [PP-C](i) as an ELPPLC, we define a directed weighted graph

H C i = (N C i , F C i ) as follows. The vertices of H C i are the incompatible pairs of I plus a copy i ′ of pair i, i.e., N C i := I ∪ {i ′ }. The arcs set of H C i is F C i = {(h, j) ∈ A : h, j ∈ I, j ̸ = i} ∪ {(j, i ′ ) : (j, i) ∈ A}
that is F C i contains the arcs of compatibility graph G between the incompatible pairs, except those entering in pair i and for all arcs (j, i) ∈ A entering in i, we add an arc (j, i ′ ) entering in the copy i ′ of i.

Remark that circuits in graph G starting and ending in i correspond to paths in graph H C i starting in i and ending in i ′ . Weights Whj assigned to arcs (h, j) ∈ F are defined as follows

Whj =            W ij -π j -β, if h = i; W hi -π i , if j = i ′ ; W hj -π j , otherwise. (9)
To consider the path length, we define a resource consumption L hj = 1 for each arc (h, j) ∈ F. Solving problem [PP-C](i) consists in finding the most positive reduced cost elementary path starting at i and ending at i ′ in graph H C i such that the length of the path is less than or equal to L C .

We model [PP-P] as an ELPPLC on graph H P = (N P , F P ) defined as compatibility graph G augmented with source vertex s and an arc from s to each altruistic donor of D. Precisely, we set N P := {s} ∪ V and

F P = A ∪ {(s, i) : i ∈ D}. Given an arc (i, j) ∈ F P , its weight Wij is defined as follows Wij =      W ij -π j -β, if i = s; W ij -π j , otherwise. (10)
Resource consumption L ij is set to be one on all arcs (i, j) ∈ F P . Problem [PP-P] consists in finding the most positive reduced cost elementary path starting at s ∈ N and ending in any vertex j ∈ N P \ {s} in graph H P such that the length of the path is less than or equal to L P + 1. 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 H P used to solve [PP-P], we add a source vertex s which is not included in the compatibility graph G.

In the following, we report two theoretical results which identify conditions under which subproblems [PP-C](i), i ∈ 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., [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF]. 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 H = (N , F) by pseudo-polynomial algorithms with a temporal complexity of O( R|F|) [START_REF] Desrochers | An algorithm for the shortest path problem with resource constraints[END_REF] where R is the maximal amount of resource. Conversely, the LPPLC can be solved in polynomial time with a temporal complexity of O(|N ||F |). Indeed, in the LPPLC, the maximal amount of resource R is the maximum length of the path L, which is bounded from above by the number of vertices in the graph |N |. In addition, being the LPPLC a relaxation of the ELPPLC, the correctness of the column generation procedure is ensured.

The first result states that the subproblems to price the circuits reduce to an LPPLC. 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 ∈ I, then at least one of the elementary circuits composing it must have a positive reduced cost. 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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] 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 ≤ L C + 1 and problems [PP-C](i), i ∈ I, do not
identify any circuit with a reduced cost larger than -β, 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 ∈ I, do not identify any circuit (of length at most L C ) with a reduced cost larger than -β, then [PP-P] will not provide any positive reduced cost path which is non-elementary.

Note that the comparison is done with -β and not zero since for the chains the β term is subtracted from the weight of the outgoing arcs from altruistic donors.

Remark that if L P > L C + 1, solving the LPPLC on graph H P provides an upper bound on the value of [PP-P] since the LPPLC is a relaxation of the ELPPLC.

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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] 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{ We : e ∈ E C i } ≤ 0, for all i ∈ 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 in the other case no reduced cost circuit has a value greater than -β. 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 ≤ 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 -β, then [PP-P] will not provide any positive reduced cost path that is non-elementary.

The procedure of Algorithm 1 solves the MP to optimality at each node of the branch-and-bound tree. i be its optimal value, for all i ∈ I; In the following, we describe the algorithms to solve: (i) the LPPLC to provide solutions for subproblems [PP-C](i) and [PP-P], and (ii) the ELPPLC to provide optimal solutions for [PP-P].

6 let W * C = max{ W * i : i ∈ I}; 7 if W * C ≤
We report a polynomial time procedure based on the Bellman-Ford algorithm to solve the LPPLC.

Precisely, such algorithm corresponds to the first L iterations of the Bellman-Ford algorithm, and is detailed in Algorithm 2, where we make use of the generic notation introduced in Section 4.2. In addition, we denote by W l i the weight of a path of length l = 0, . . . , L starting in s and ending in vertex i ∈ N . Matrix (p l i ) l=0,..., L,i∈N stores the predecessor p l i of vertex i ∈ N in a path of length l starting in s and ending in vertex i. We write P for the set of the positive reduced cost paths found by the algorithm.

To complete this section, we describe the label correcting dynamic programming algorithm [START_REF] Feillet | An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems[END_REF] we propose to solve the ELPPLC. In the work of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF], 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 ∈ N are repeatedly processed and their associated labels (set L i ), which identify paths in the graph, are extended. Precisely, a label l = (L, W , U, i) ∈ L i represents a path in graph H starting at vertex s and ending at vertex i ∈ N characterised by its accumulated weight W , its length L and the subset of visited vertices U ⊆ N . A label l = (L, W , U, i) associated with vertex i can be extended along arc (i, j) ∈ F if the length constraint (L < L) and the elementarity constraint (j / ∈ U) are respected. If this is the case, a new label l ′ = (L + 1, W + W ij , U ∪ {j}, j) associated with vertex j ∈ 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, W , U, i) and l ′ = (L ′ , W ′ , U ′ , i) associated with the Algorithm 2: A Bellman-Ford algorithm for the LPPLC

Input: Graph H = (N , F ).
Initialisation: W 0 s := 0 and p 0 s := s, W l i := -∞ and p l i = null for all i ∈ N \ {s} and l = 0, . . . , L and P = ∅. same vertex i, we say that l dominates l ′ if:

1 forall l = 1, . . . , L do 2 forall i ∈ N do 3 forall (i, j) ∈ δ + (i) do 4 if W l-1 i + Wij > W l j then 5 set W l j := W l-1 i + Wij
           L ≤ L ′ W ≥ W ′ U ⊆ U ′ (11)
and one of the inequalities (inclusion) is strict. The labelling algorithm is presented in Algorithm 3.

The elementarity constraint makes the ELPPLC strongly NP-hard and slows down the solution algorithm.

Adopting the ng-path relaxation [START_REF] Baldacci | New route relaxation and pricing strategies for the vehicle routing problem[END_REF], which partially relaxes the elementarity constraint of the paths, helps in accelerating the solution of the ELPPLC and, in practice, the paths found when solving this relaxation are usually elementary. Each vertex i ∈ N is assigned with a neighbourhood U i of a given 350 size. Circuits along a path are then allowed only if each vertex visited more than once does not belong to the neighbourhoods of its predecessors in the path. The label definition and extension rule are modified accordingly. Precisely, the set of visited customers U becomes the memory of the label. The extension of

l = (L, W , U, i) along arc (i, j) is l ′ = (L + 1, W + W ij , (U ∩ U j ) ∪ {j}, j).

Cut generation 355

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 [START_REF] Jepsen | Subset-row inequalities applied to the vehiclerouting problem with time windows[END_REF]. A common practice from the literature is to separate such inequalities by enumeration (see, e.g., [START_REF] Pecin | Improved branch-cut-and-price for capacitated vehicle routing[END_REF].

Input: Graph H = (N , F ).
Initialisation: Lj := ∅, for all j ∈ N ; Ls := {(0, 0, ∅, s)}; termination := f alse.

1 while termination ̸ = true do 2 set termination := true; However, the characteristics of the KEP instances make this procedure prohibitive in terms of computational time. Indeed, on instances with thousands of incompatible pairs, one may end up with millions of subsetrow inequalities even associated with only subsets of cardinality equal to three. Note that although these subsets can be determined a priori, they need to be inspected at each separation round to identify violated inequalities. 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 (see [START_REF] Padberg | On the facial structure of set packing polyhedra[END_REF], respectively.

3 forall i ∈ N do 4 forall l = (L, W , U , i) ∈ Li s.t. L < L do 5 if l has not been extended yet then 6 forall (i, j) ∈ F s.t. j / ∈ U do 7 let l ′ = (L + 1, W + Wij , U ∪ {j}, j)
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. On the other side, such non-robust inequalities are worth to be used 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 ∈ E, we denote by V(e)

the set of vertices in exchange e. We say that two exchanges e, e ′ ∈ E are in conflict if they share common vertices, i.e., if V(e) ∩ V(e ′ ) ̸ = ∅. 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 λ of the MP, we define the so-called conflict graph C = (Q, T ) as follows. Node set Q contains nodes associated with the exchanges e ∈ E whose corresponding variable has a fractional value, i.e., λe ∈]0, 1[. Edge set T contains an edge (e, e ′ ) if exchanges e ∈ Q and e ′ ∈ Q are in conflict. In the following, we say that an edge (e, e ′ ) ∈ T

is covered by a vertex v ∈ V if v ∈ V(e) ∩ V(e ′ ).
In Section 4.4.1, we first introduce the subset-row inequalities and how they are managed in the pricing algorithm. Then, in Sections 4.4.2 and 4.4.3, we present clique and odd-hole inequalities, respectively. For each family of inequalities, we present the separation algorithm considered and the procedure to transform them into subset-row inequalities. Finally, the strategy used to separate the inequalities and add them to the MP is described in Section 4.4.4.

Subset-row inequalities

Given a subset S ⊆ V and a multiplier p i for each i ∈ S, subset-row (SR) inequalities are obtained as a

Chvátal-Gomory rounding of the Constraints (2) associated with elements in S:

e∈E i∈S p i a e i λ e ≤ i∈S p i , S ⊆ V. ( 12
)
We recall that we do not directly separate SR inequalities and in the following, we detail how to manage these non-robust inequalities in the pricing algorithm. As mentioned above, considering non-robust inequalities modifies the structure of the pricing problem. For the KEP, this translates into formulating all pricing problems [PP-C](i), i ∈ I, and [PP-P] as an Elementary Longest Path Problem with Resource Constraints (ELPPRC). Indeed, each subset-row inequality enforces a resource. It is important to notice this implies that when considering such inequalities, it is no longer possible to solve any pricing problem in polynomial time. Hence, all pricing subproblems are solved via the labelling algorithm presented in Section 4.3 where the following modifications have to be applied. Let σ S ≥ 0 be the dual variable associated with SR inequality (12) defined for subset S ⊆ V. To consider such dual variable in the ELPPRC, we follow the procedure proposed by [START_REF] Pecin | Improved branch-cut-and-price for capacitated vehicle routing[END_REF]. We choose to do so because [START_REF] Pecin | Improved branch-cut-and-price for capacitated vehicle routing[END_REF] provide a general management rule of the SR inequalities which is valid also in the case where the elementarity of the paths is relaxed. In the label definition, we include an attribute for each SR inequality in the RMP whose associated dual variable is different from zero. The attribute of a SR inequality identified by S ⊆ V is a parameter M (S) which records the visits of a path to vertices in S and establishes when dual variable σ S has to be discounted from the reduced cost of the path. Precisely, parameter M (S) is initialised to 0 and every time a path visits a vertex i ∈ S, M (S) is incremented by p i = 1/2. If M (S) ≥ 1, dual variable σ S is discounted from the reduced cost and M (S) is decremented by one unit.

Moreover, the new label attributes M (S) have to be included also in the dominance rule (11). To do so, the second condition in dominance rule has to be replaced by:

W ≥ W ′ + S∈M: M (S)>M ′ (S) σ S ,
where M is the set of subsets S ⊆ V representing SR inequalities in the RMP whose dual variable σ S is different from zero.

Clique inequalities

Clique inequalities (Cl) correspond to cliques in conflict graph C. A clique is a set of nodes W ⊆ Q that induces a complete subgraph, i.e., such that (e, e ′ ) ∈ T , for each e, e ′ ∈ W, e ̸ = e ′ . The clique inequality associated with W is:

e∈W λ e ≤ 1. ( 13
)
The separation of these inequalities is performed via the iterative heuristic algorithm proposed by [START_REF] Marzi | Computational study of separation algorithms for clique inequalities[END_REF]. First, each node e ∈ Q is assigned with a weight equal to the number of its incident edges times λe .

At each iteration, the algorithm selects a node e ∈ Q with the highest weight and builds a maximal weighed 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 W, hence, the management of the associated dual variable γ W ≥ 0 when solving the pricing problem is not tractable. Indeed, when solving the pricing problem, the dual variable γ W has to be discounted if the associated exchange is the same as one of the exchanges in set 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 W, that would be computationally very costly. Subset S is defined as follows. First, we determine the subset of candidate vertices V(W) ⊆ V that can cover the edges in T (W), i.e., V(W) = e,e ′ ∈W,e̸ =e ′ V(e) ∩ V(e ′ ). The vertices of v ∈ V(W) are ordered by decreasing number of nodes e ∈ W such that v ∈ V(e), i.e., of exchanges in the clique which visit vertices v.

Then, each vertex v ∈ V(W) is processed in such order and inserted in S if there exists an edge (e, e ′ ) ∈ T (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.

Finally, the procedure determines multipliers p i , i ∈ S. First, if the cardinality of S is less or equal to five, we assign the multipliers proposed in Pecin et al. ( 2017): (i) if |S| = 3, then p i = 1/2, for all i ∈ S;

(ii) if |S| = 4, then p i = 2/3, for all i ∈ S; (iii) if |S| = 5, then p i = 1/2, for all i ∈ S. 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 the following mixed-integer program.

For each e ∈ W, we introduce an integer non-negative variable y int

r int = i∈S p i -r f rac (16) m ≤ p i ∀i ∈ S (17) m ≥ p i ∀i ∈ S (18)
r int ∈ Z ≥0 , 0 ≤ r f rac ≤ 0.99 (19)
y int e ∈ Z ≥0 , 0 ≤ y f rac e ≤ 0.99 ∀e ∈ W (20) 0 ≤ p i ≤ 1 ∀i ∈ S (21) m, m ∈ R ≥0 . (22)
Objective ( 14) minimises two terms: the first one is the negative of the violation of the SR inequality w.r.t.

solution λ 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 α 1 and α 2 so that the two objectives are managed hierarchically: among the solutions which maximise the violation, we look for the one that minimises the distance between the minimal and maximal multiplier. Constraints (15) model the value of variable y int e for each e ∈ W. Similarly, Constraint ( 16) models the value of variable r int . Constraints ( 17) and ( 18) compute the minimal and maximal values of the multipliers, respectively. Finally, Constraints ( 19), ( 20), ( 21) and ( 22) 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 ∈ S.
Example 2. We make use of the toy instance of the KEP presented in Example 1. We consider fractional solution λ with five exchanges e 1 , e 2 , e 3 , e 4 and e 5 defined as in Table 1. The associated conflict graph 2 where on each edge we report the set of vertices of the compatibility graph G = (V, A) that can cover that edge. It is easy to see that set of nodes 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 λe1 + λe2 + λe3 + λe4 = 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 ∈ 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.

C = (Q, T ) is shown in Figure
In Table 2, 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 ∈ 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}.

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

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 , . . . , e 2k+1 }, k ≥ 2, such that edge set T contains edges t i = (e i , e i+1 ), i = 1, . . . , 2k, and t 2k+1 = (e 2k+1 , e 1 ) and no other edge incident on two nodes of P. The odd-hole inequality associated with P is:

e∈P λ e ≤ |P| -1 2 . ( 23
)
The separation of these inequalities is done based on the exact procedure of [START_REF] Hoffman | Solving airline crew scheduling problems by branch-and-cut[END_REF].

Such procedure considers each vertex of conflict graph 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 [START_REF] Hoffman | Solving airline crew scheduling problems by branch-and-cut[END_REF], 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 P, hence, the management of the associated dual variable θ P ≥ 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.2).

For this reason, we propose a procedure to retrieve a SR inequality from an OH inequality defined on cycle P. Moreover such SR inequality is a lifted version of the associated OH inequality. For each edge t of the odd cycle P, we select in the compatibility graph G = (V, A) a vertex v ∈ V such that t is covered by v. Precisely, for each edge t i = (e i , e i+1 ) ∈ T , i = 1, . . . , 2k, we select a vertex v i in the set V(e i ) ∩ V(e i+1 );

and for edge t 2k+1 = (e 2k+1 , e 1 ) ∈ T , we select a vertex v 2k+1 in the set V(e 2k+1 ) ∩ V(e 1 ).

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 S = {v 1 , . . . , v 2k+1 } and multipliers p i = 1/2 for each i ∈ S:

e∈E 1 2 i∈S a e i λ e ≤ |S| 2 . ( 24
)
Lemma 1. If a fractional solution λ violates OH inequality (23) then it violates also SR inequality (24) associated with inequality (23).

Proof. First, we observe that the right hand-side of inequality ( 24) coincides with the one of inequality ( 23 Note that Inequality ( 24) is a lifted version of Inequality (23). Indeed, the left hand-side of ( 24) contains additional variables in E \ P with positive coefficients.

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

Example 3. We make use of the toy instance of the KEP presented in Example 1. We consider fractional solution λ defined as in Table 3. The associated conflict graph C = (Q, T ) is shown in Figure 3 where on each edge we report the set of vertices of the compatibility graph G = (V, A) that can cover that edge. It is easy to see that the set of nodes 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 3, we have λe1 + λe2 + λe3 + λe4 + λe5 = 2.5 > (|P| -1)/2 = 2, thus the violation of the OH inequality is equal to 0.5. Now, we retrieve the associated SR inequality. In this case, we just need to define set S. For each edge in the odd cycle, we select one of the vertices reported in Figure 3 on that edge. By defining S = {1, 4, 6, 7, 8}, and multipliers p i = 1/2, i ∈ S, we obtain a violated SR inequality with the same violation of the OH inequality. 3, where odd cycle without cords P = {e 1 , e 2 , e 3 , e 4 , e 5 } is marked in blue.

Cut generation strategy

We use the following 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, we do not separate any inequality. 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-andbound 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.

Branching scheme

To ensure the integrality of the solution returned by the BPC algorithm, we branch on the use of the arcs in A. Let λ be an optimal fractional solution of the MP at a node of the branch-and-bound tree. We branch on values f ij = e∈E b e ij λe , (i, j) ∈ A, where parameter b e ij takes value one if arc (i, j) ∈ A belongs to exchange e ∈ E and zero otherwise. Precisely, we select the branching candidate whose value is the closest to 0.5. Remark that value f ij ∈]0, 1[, hence, in one branch we force arc (i, j) to be used ( e∈E b e ij λ e ≥ 1) while in the other branch, we forbid its use ( e∈E b e ij λ e = 0). In the former case, dual variable ϕ ij ≤ 0 associated with the branching constraint is considered when solving the pricing problem. Precisely, it is discounted from arc weight Wij in Equation ( 9) or and (10). In the latter case, arc (i, j) is removed from graph H when we solve the pricing problem. Last, the branch-and-bound tree is explored according to the best-first strategy.

Accelerating techniques

We make use of the following accelerating techniques to speed up our BPC algorithm.

Preprocessing of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF]. Imposing length constraints on cycles and chains allows us to perform a preprocessing procedure to reduce the size of compatibility graph G. Such procedure was introduced by [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] and is based on the Floyd-Warshall algorithm to compute the shortest path between each pair of vertices in a graph. Precisely, we consider a graph G = ({s} ∪ V, Ã), where à = A ∪ {(s, i) : i ∈ D}. Graph G is defined as graph H P used to price out variables associated with exchange paths. The weights on the arcs are set to one. Then, the Floyd-Warshall algorithm is applied to G to detect the minimum length l * (i, j) paths between each pair of vertices i, j ∈ {s} ∪ V.

We remove all arcs (i, j) ∈ A that satisfy the following two conditions:

1. the length of the shortest path from source s to vertex i is larger than or equal to the maximum path length, i.e., l * (s, i) ≥ L P + 1; 2. the length of the shortest path from vertex j to vertex i is larger than or equal to the maximum cycle length, i.e., l * (j, i) ≥ L C . Finally, isolated vertices are removed from V as well.

Preprocessing of [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF]. [START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF] proposed a procedure to reduce the number of pricing subproblems [PP-C](i), i ∈ I, to be processed in the pricing problem solution. In addition, the same procedure allows to reduce the size of pricing graphs H C i . As [START_REF] Constantino | New insights on integer-programming models for the kidney exchange problem[END_REF] and [START_REF] Klimentova | A new branch-and-price approach for the kidney exchange problem[END_REF][START_REF] Riascos-Álvarez | A branch-and-price algorithm enhanced by decision diagrams for the kidney exchange problem[END_REF] exploit the symmetry of the circuits subproblems: a circuit starting at vertex i considered in subproblem [PP-C](i) and containing vertex j will also appear as a circuit starting at vertex j when solving [PP-C](j). The procedure reads as follows. In the following, we work on a copy of compatibility graph G = (V, A) where we progressively remove vertices and arcs. For the ease of readability, we keep notation G = (V, A) to refer to this copy. We write l * (i, j) for the value of the shortest path, in terms of length, from i to j in compatibility graph G = (V, A). First, the incompatible pairs with no in-going or no out-going arcs are removed from I. Indeed, these pairs cannot be part of any circuit. The remaining ones are sorted by decreasing number of incident arcs. Then, the first pair i ∈ I is selected and graph

H C i = (N C i , F C i ) is built as follows. We include in N C
i all pairs j ∈ I whose distance from i is less than or equal to the cycle length, i.e., l * (i, j) + l * (j, i) ≤ L C . Once the vertex set is built, arc set F C i contains all the arcs (i ′ , j ′ ) ∈ A whose extremes are in N C i and such that l * (i, i ′ ) + l * (j ′ , i) + 1 ≤ L C . Finally, vertex i is removed from graph G along with its incident arcs. Set I is re-ordered according to the reduced graph G and a new iteration starts. The procedure terminates when either all the pairs in I are processed or there is no pair with both in-going or out-going arcs. Those reduced graphs H C i are then used to price the variables associated with the circuits.

Initialisation of [RMP(E ′

) .] It is well known that column generation suffers from degeneracy which may slow down its convergence [START_REF] Desrosiers | A primer in column generation[END_REF]. 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 set E ′ . 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 [START_REF] Archetti | Optimal solutions for routing problems with profits[END_REF]. 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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF], 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.

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.

In this section, first, we present the characteristics of the benchmark instances we consider. We assess the impact of the valid inequalities to select the best configuration for the BPC algorithm (Section 5.2).

Then, we compare the results obtained with the BPC algorithm on the benchmark instances with those reported in [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF], [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] and [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF]. Note that these authors reported computational results on different datasets. Finally, in Section 5.4, we assess the impact of the length constraints on the objective function value.

The instances and detailed results can be found at [START_REF] Petris | Instances and detailed results for the whole testbed of "A Branch-Price-and-Cut algorithm for the Kidney Exchange Problem[END_REF].

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 [START_REF] Mattei | Preflib: A library for preferences http://www. preflib[END_REF]

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 Cl inequalities (13) or the OH inequalities (23).

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 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 (13) are separated; BPC+OH: only odd-hole inequalities (23) are separated; BPC+Cl+OH: all valid inequalities are separated.

First, in Table 5, 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 following three columns report statistics regarding the impact of the valid inequalities: the number of instances solved to optimality at the root node (#opt.); the average gap at the root node (avg.gap[%no.cuts] ), expressed as a percentage of the gap at the root node when no cuts are added, that is computed as 100(U B V I -LB * )/(U B root -LB * )100, where U B root and U B V I 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; the average time in seconds to solve the root node (avg.t [s] ). 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. The last three columns report statistics on the cut generation strategy: the average number of SR inequalities arising from the Cl inequalities (avg.#Cl ), the average number of SR inequalities arising from the OH inequalities (avg.#OH ) and the average separation time (avg.t[s] sep.). We use '-' when the information is not available. 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 74.34% w.r.t.

the one obtained by BPC. Note that only separating OH inequalities also leads to a very good root node gap (75.36% w.r.t. the one at the root node), while only separating Cl inequalities has worse performance (87.31% 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.28 seconds whereas the one of BPC+OH is 101.59 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.2) is designed as a very fast heuristic, whereas the procedure to separate OH inequalities (see Section 4.4.3) 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 6, 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 5. 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.). The following five columns report statistics regarding the 50 instances solved to optimality by all configurations: the average number of nodes of the branch-and-bound tree (avg.#nodes), the average computational time in seconds (avg.t[s] ), the average number of SR inequalities arising from the Cl inequalities (avg.#Cl ), the average number of SR inequalities arising from the OH inequalities (avg.#OH ) and the average separation time in seconds (avg.t[s] sep.). We use '-' when the information is not available. 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 and 56 BPC+OH and BPC+Cl+OH. In addition, on the 50 instances solved to optimality by all four configurations, adding the inequalities permit to reduce: (i) the number of the nodes of the branch-and-bound tree by a factor of at least 2.5; (ii) the computational time by a factor of at least 1.2. The best configuration is BPC+Cl+OH: these two reduction factors become 4.0 and 1.3, 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 5.

Finally, Table 7 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 5. 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:

the average number of nodes of the branch-and-bound tree (avg.#nodes), the average lower bound when the time limit is reached (avg.LB ), the average upper bound when the time limit is reached (avg.UB ), the average optimality gap expressed as a percentage, i.e., 100(U B -LB)/LB (avg.gap[%] ), the average number of SR inequalities arising from the Cl inequalities (avg.#Cl ), the average number of SR inequalities arising from the OH inequalities (avg.#OH ) and the average separation time in seconds (avg.t[s] sep.). We use '-' when the information is not available. The benefit of the valid inequalities on the instances not solved to optimality is less evident. Overall the 695 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.

700

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.69 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 Cl inequalities are separated after solving the root node of the branch-and-bound tree. The time spent in the separation of the inequalities 705 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 Cl inequalities the separation time is negligible, only a few seconds.

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 Cl inequalities, and slightly better for the configuration BPC+OH. The quality of the lower bound comes from 710 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 715 the inequalities is slightly better than the one of BPC. In this respect, the best configuration is BPC+Cl+OH.

This balance between worsening the lower bounds and improving the upper bounds yields the optimality gap to be comparable among all the configurations.

We choose configuration BPC+Cl+OH for the BPC algorithm 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 720 RAM. Note that [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] do not test their procedure on all these instances with more than 500 pairs.

Table 9 summarises the results of the comparison between the BPC algorithm and the restricted master heuristic of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF]. The rows of the table group instances with the same maximum path length and the same number of incompatible pairs. The first three columns report some information about the in- From the results in Table 9, the BPC algorithm solves all the 135 instances to optimality. The optimality is proven at the root node for 104 instances in on average 0.48 seconds. For the remaining ones, the BPC algorithm explores a few tens of nodes on 29 instances and a few hundreds on the remaining two. For these instances, the computational time increases. On average, it is equal to 29.35 seconds, however it is always less than 300 seconds. Conversely, the heuristic with a performance guarantee of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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 133 instances. The two 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 [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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 an order of magnitude w.r.t.

the algorithm of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF].

In Table 10 shows that the performances of the BPC algorithm decrease as the size of the instances increases, both in terms of maximum path length and number of pairs. The BPC algorithm identifies 56 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 11, 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 |I|. Precisely, it increases with the number of 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 |I| = 750, the computational time is less than four seconds when the instances are solved to optimality at the root node while it is larger than 200 seconds when more than 100 nodes are explored.

The BPC algorithm is not able to prove the optimality of 79 instances. However, they are left with a small optimality gap, on average, equal to 0.05%, 0.21% and 0.76% 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.08%.

The comparison with the results of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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 ). The results of Table 11 clearly highlight the superiority of the BPC algorithm w.r.t. the destructive bound procedure of [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF]. Indeed, the BPC algorithm solves to optimality each of the 840 instances in less than 350 seconds. More precisely, the computational time is less than 30 seconds for 837 instances. 812 instances are solved at the root node, the remaining ones by exploring 244 nodes of the branch-and-bound tree, on average. Conversely, the procedure of [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] suffers from lack of scalability. Indeed, such procedure entails enumerating all the half-cycles of length up to ⌈L C ⌉ + 1. This operation becomes intractable when the size of the instance grows.

In Table 12, we present the results obtained by the BPC algorithm where the objective function is the maximisation of the medical benefit. [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] do not test their procedure in the case of maximisation of the medical benefit. The rows and the first three columns of the table have the same meaning as those in Table 11. The next three columns report results regarding the instances solved to optimality by the BPC algorithm: the number of such instances (#), the average number of nodes of the branch-and-bound tree to prove the optimality (avg.#nodes) and the average time expressed in seconds (avg.t[s] ). The last three columns report the results regarding the instances not solved to optimality by the BPC algorithm: the number of such instances (#), the average number of nodes of the branch-and-bound tree explored by the BPC algorithm (avg.#nodes) and the average optimality gap expressed as a percentage (avg.gap[%] ). We consider only instances characterised by a number of pairs up to 400.

From the results of Table 12, it can observed that the type of the objective function has a huge impact on the results. Maximising the medical benefit makes the instances 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 maximise 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 (90 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.43%, on average. The same behaviour was observed when considering instances with more than 400 pairs.

Impact of the length constraints on the objective function

In this section, we assess the impact of the length constraints of the exchange paths on the objective function value. To conduct such analysis, we take into account both objective function types, i.e., either maximisation of the number of transplants (#TR) or maximisation of the medical benefit (MB). For the former case, we only consider the instances of the PrefLib dataset with maximum length of the circuits L C = 3; for the latter case, we only consider the instances of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with 50, 100, or 250 incompatible pairs. In both sets, we group the instances characterised by the same compatibility graph and we observe how the objective function value behaves when the maximum length of the exchange paths increases. Note that all these instances are solved to optimality by the BPC algorithm.

In the case of the maximisation of the number of transplants, we do not report any result because the improvements are extremely sporadic. Indeed, on the 230 instances characterised by the same compatibility graph, the number of transplants improves only 19 times when we increase the length of the paths from 3 to 4, from 4 to 5 or from 5 to 6. Therefore, it seems that the influence of the path length on the maximum number of transplants is negligible. We try to explain this phenomenon with the results in Table 13. In this table, we group the instances by maximum length of the paths L P . The first three columns report the value of L P , the number of instances in each group (#) and the total number of altruistic donors (tot.|D|), that is the sum of the altruistic donors over the instances. The following six columns report the total number of paths in the optimal solution (tot.#paths) and, for each length of the paths l = 1, . . . , L P , the percentage of the total number of paths with length l (#paths per length[%] ). First, almost all the altruistic donors available in the compatibility graphs start a path in the optimal solutions (see columns tot.|D| and tot.#paths). Precisely, all of them are used in the instances with L P = 3, 4, 5 and only 12 out of 12120 of them remain unused in the instances with L P = 6. However, the vast majority of the paths are of small length: in each group of instances, at least the 99% of the paths is of length less than or equal to three.

Finally, Table 14 reports the average improvements of the medical benefit as the maximum length of the paths increases on the instances of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with up to 250 incompatible pairs. The rows of the table group instances with the same number of incompatible pairs (same compatibility graph). The first two columns report the number of incompatible pairs (|I|) and the number of instances (#) in each group.

The remaining two columns report the average improvement of the medical benefit (objective function value) expressed as a percentage (avg.impr[%] ) as the maximum path length increases from three to six (L P : 3 → 6)

and from six to twelve (L P : 6 → 12), respectively. of transplants. Indeed, we observe that the maximum length constraints on the paths has a great impact on the value of the objective function. The largest improvements of the medical benefit are obtained when the path length is increased from three to six. These improvements are reduced when the maximum length is increased from six to twelve.

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 maximisation 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. We propose two heuristics to separate them based on the separation of the clique and odd-hole inequalities, respectively.

We test the BPC algorithm against the three algorithms recently proposed in the literature, namely, the restricted master heuristic of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF], the destructive bound procedure of [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] and the Branch-and-Price algorithm of [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF]. 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. Indeed, although the approaches of Pansart In addition, the impact of the valid inequalities is assessed: they permit to 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 maximisation 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 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 [START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF], where the exponentially-many variables are the half-cycles.

Figure 1 :

 1 Figure 1: Compatibility graph of the toy instance of the KEP defined in Example 1.

  and [PP-P] share the same structure: they can be formulated as an Elementary Longest Path Problem with Length Constraint (ELPPLC), i.e., a variant of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC).

Algorithm 1 :

 1 Column generation procedure. Initialisation: Initialise the set of columns to the RMP. 1 do 2 solve the RMP; 3 get the optimal solution of the dual of the RMP; 4 build pricing subproblems [PP-C](i), i ∈ I and [PP-P]; 5 solve [PP-C](i) and let W *

  Now, we propose a heuristic procedure to retrieve a violated SR inequality (12) given a violated Cl inequality defined on a clique W. We denote by T (W) = {(e, e ′ ) ∈ T : e, e ′ ∈ W, e ̸ = e ′ } the subset of the edges whose incident nodes are in clique W. The procedure first determines a subset of vertices S ⊆ V such all the edges (e, e ′ ) ∈ T (W) are covered with at least one vertex v ∈ S. Then, it defines multipliers p i , i ∈ S to obtain a violated SR inequality.

e

  and a continuous variable y f rac e ∈ [0, 0.99] to model the integer and fractional parts of coefficients of the λ variables in SR inequality (12).Similarly, we introduce an integer non-negative variable r int and a continuous variable r f rac ∈ [0, 0.99] to model the integer and fractional parts of the right hand-side of SR inequality(12). With abuse of notation, we denote the continuous non-negative variables modelling the multipliers by p i , i ∈ S. In addition, we denote by m and m two continuous non-negative variables to model the minimal and maximal values of the multipliers. Finally, we denote by α 1 , α 2 ∈ R >0 two weights.Given a fractional solution λ and subset S, we propose the following mixed-integer program to determine the multipliers:[M( λ, S)] min α 1 r int -

  ), indeed, it holds |S| = |P| by construction and |P| is odd. Then, in the left hand-side of inequality (24), at least the variables associated with exchanges in P appear with coefficient one. Indeed, such exchanges visit exactly two vertices in S. Finally, it holds inequality (24).

Figure 3 :

 3 Figure 3: Conflict graph arising from the fractional solution of Table3, where odd cycle without cords P = {e 1 , e 2 , e 3 , e 4 , e 5 }

  , the set proposed by[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] and the one considered by[START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF]. 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). Both generators take as input the number of incompatible patient-donor pairs (|I|), the number of altruistic donors (|D|) and several medical related parameters to build a realistic compatibility graph G. The medical related parameters influence the density of the graph and the medical benefit associated with the arcs of the graph. The interested reader may refer to Saidman et al. (2006) and Delorme et al. (2022) for more information. Table 4 summarises the characteristics of the instances in the three sets. The rows of the tables are associated with the sets of instances. The column headings are as follows: set: name of the set; #: total number of instances in the set; |I|: number of incompatible patient-donor pairs in the set; |D|[% :] percentage of altruistic donors w.r.t. the number of pairs |I|; avg. density of G: average density of compatibility graph 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 G; L C : maximum length of the cycles; L P : maximum length of the paths; obj.: type of objective function, either maximisation 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 + |D|[%])|I|.

  et al. (2022) with a number of pairs greater than or equal to 500. The objective is the maximisation 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 maximised, 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).

  stance subset: maximum path lengths (L P ), number of incompatible patient-donor pairs (|I|) and number of instances (#). The next three columns show the results obtained by the BPC algorithm: number of instances solved to optimality (#opt.), average number of nodes of the branch-and-bound tree (avg.#nodes) and average computational time in seconds (avg.t[s] ). The last three columns report some statistic related to the algorithm of Pansart et al. (2022): number of instances solved to optimality (#opt.), average computational time in seconds (avg.t[s] ) and optimality gap expressed as a percentage for the instances not solved to optimality (avg.gap[%] noOpt.). If all the instances in a row are solved to optimality by the algorithm of Pansart et al. (2022), we make use of '-' in column avg.gap[%] noOpt..

Finally, we tested

  the code of the BP algorithm of[START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] 3 on the instances of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] characterised by values of the maximum length of the paths larger or equal to six. Our tests show that the algorithm do 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[START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF], the ELPPLC is solved with a mixed integer program with exponentially-many constraints. It turns 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. 5.3.3. Results on the set of instances of Delorme et al. (2023) Table 11 reports the results obtained on the instances of Delorme et al. (2023) when the objective function is the maximisation of the number of transplants. A comparison with the results of Delorme et al. (2023) is also conducted. The algorithm of Delorme et al. (2023) was implemented in C++ and ran on a machine equipped with an Intel(R) Core(TM) i5-1135G7, 2.40GHz and 32GB of memory.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. The first three columns report the characteristics of the subset of instances: the maximum length of the cycles (L C ), the number of pairs (|I|) and the number of instances in the subset (#). The next two columns report the results obtained by the BPC algorithm, namely, the number of instances solved to optimality (#opt.) and the average time expressed in seconds to solve the instances to optimality (avg.t[s] ). The last two columns report the same two statistics on the results obtained by[START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF]. Columns are doubled to include all the instances in the table.

  et al. (2022) and[START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] are able to solve any kind of instance, the BPC algorithm clearly outperform the first and the second one does not scale on instances with long chains and maximisation of medical benefit as objective. The approach of[START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] solves instances with cycles only and, in any case, its results are clearly outperformed by those of the BPC algorithm.

  * P > 0 and all the positive reduced cost paths returned by solving the LPPLC are non-elementary then 10 if (L P ≤ L C + 1 and W * C > -β) or (L P > L C + 1) then 11 solve the ELPPLC on graph H P and let W * P be its optimal value;

	12	end
	13	end
	14	end

0 then 8 Solve the LPPLC on graph H P and let W * P be its optimal value; 9 if W 15 add positive reduced cost elementary circuits and paths to the RMP, if any is detected; 16 while max{ W * C , W * P } > 0;

  ;

	6	set p l j = i;
	7	end
	8	end
	9	end
	10 end
	// retrieve positive reduced cost paths
	11 forall l = 1, . . . , L do
	12	forall i ∈ N do
	13	if W l i > 0 then
	14	apply backtracking to p l i to build the path;

15 add the path to P; 16 end 17 end 18 end 19 return P;

Table 1 :

 1 Fractional solution λ.

	exchange	value in	λ
	e 1 = (1, 8, 9, 6)	0.33
	e 2 = (2, 8, 9, 7)	0.33
	e 3 = (6, 7, 6)	0.33
	e 4 = (1, 8, 4, 5, 7)	0.33
	e 5 = (2, 3, 4, 5)	0.66

Table 2 :

 2 Ordering of the elements of V(W).

	V(W) exchanges of W
	7	e 2 , e 3 , e 4
	8	e 1 , e 2 , e 4
	1	e 1 , e 4
	6	e 1 , e 3
	9	e 1 , e 2

Figure 2: Conflict graph arising from the fractional solution of Table

1

, where clique W = {e 1 , e 2 , e 3 , e 4 } is marked in blue.

Table 3 :

 3 Fractional solution λ.

Table 4 :

 4 Characteristics of the sets of instances.

	Characteristics

Table 5 :

 5 Comparison of four configurations of the BPC algorithm at the root node of the branch-and-bound tree.

	BPC	2	100.00	84.02	-	-	-
	BPC+Cl	5	87.31	89.08	7.97	-	0.28
	BPC+OH	14	75.36	187.64	-	19.57	101.59
	BPC+Cl+OH	14	74.34	169.60	9.52	13.60	78.54

configuration #opt. avg.impr. cl.gap[%] avg.t[s] avg.#Cl avg.#OH avg.t[s] sep.

Table 6 :

 6 Comparison of four configurations of the BPC algorithm on the instances solved to optimality. configuration #add.opt. avg.#nodes avg.t[s] avg.#Cl avg.#OH avg.t[s] sep.

	BPC	3	682.70	332.43	-	-	-
	BPC+Cl	4	269.46	257.60	23.70	-	1.26
	BPC+OH	6	253.38	282.88	-	24.82	14.51
	BPC+Cl+OH	6	174.42	254.8	20.76	18.56	14.18

Table 7 :

 7 Comparison of four configurations of the BPC algorithm on the instances not solved to optimality.

	configuration #add.noOpt. avg.#nodes	avg.LB	avg.UB avg.gap[%] avg.#Cl avg.#OH avg.t[s] sep.
	BPC	5	1908.64	39571.57 39747.08	0.41	-	-	-
	BPC+Cl	4	1197.48	39567.40 39746.16	0.43	91.95	-	11.82
	BPC+OH	2	1271.79	39577.23 39746.04	0.40	-	15.69	165.98
	BPC+Cl+OH	2	1085.87	39560.12 39744.84	0.43	85.25	10.14	136.69

Table 9 :

 9 Results on the set of instances of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with up to 250 pairs.

		Instances			BPC			Pansart et al. (2022)
	L P	|I|	#	#opt. avg.#nodes avg.t[s]	#opt.	avg.t[s]	avg.gap[%] noOpt.
		50	15	15	1.00	0.04	15	1.07	-
	3	100 15	15	1.00	0.15	9	1.21	0.33
		250 15	15	1.00	1.06	7	3.45	0.07
		50	15	15	1.40	0.04	14	1.20	0.05
	6	100 15	15	2.07	0.36	8	2.17	0.64
		250 15	15	45.27	16.55	2	27.74	0.32
		50	15	15	1.00	0.04	15	2.52	-
	12	100 15	15	1.13	0.29	14	26.59	0.19
		250 15	15	40.47	142.81	8	1420.20	1.26

  Table10, we report the results obtained by the BPC algorithm on the instances of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with |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. The first three columns have the same meaning as those in Table9. The next three columns summarise the results obtained by the BPC algorithm on the instances solved to optimality: number of instances solved to optimality (#), average number of nodes of the branch-and-bound tree (avg.#nodes) and average computational time in seconds (avg.t[s] ). The next three columns summarise the results obtained by the BPC algorithm on the instances not solved to optimality: number of instances not solved to optimality (#), average number of nodes of the branch-and-bound tree (avg.#nodes) and optimality gap expressed as a percentage (avg.gap[%] ). The last three columns report the same information about the results of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] as in Table9. 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 10 :

 10 Results on the set of instances of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] with at least 500 pairs.

						BPC results		Pansart et al. (2022)
		Instances
					solved instances		unsolved instances			avg.gap[%]
	L P	|I|	#	#	avg.#nodes	avg.t[s]	#	avg.#nodes avg.gap[%]	#opt.	avg.t[s]	noOpt.
		500	15	15	158.93	73.98	0	-	-	1	14.23	0.13
	3	750	15	13	646.85	418.59	2	3361.00	0.04	0	85.51	0.15
		1000 15	5	177.00	129.37	10	2711.40	0.05	-	-	-
		500	15	6	89.67	90.32	9	2233.44	0.10	0	1011.70	0.44
	6	750	15	5	286.60	370.89	10	918.70	0.25	-	-	-
		1000 15	1	1353	2733.54	14	942.43	0.24	-	-	-
		500	15	7	75.43	599.08	8	523.50	0.40	-	-	-
	12	750	15	4	74.75	1206.27	11	227.91	0.65	-	-	-
		1000 15	0	-	-	15	118.47	1.04	-	-	-

Table 11 :

 11 Results on the set of instances of[START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] where the objective is the maximisation of the number of transplants.

		Instances		BPC		Delorme et al. (2023)		Instances			BPC	Delorme et al. (2023)
	L C	|I|	#	#opt. avg.t[s]	#opt.	avg.t[s]	L C	|I|	#	#opt. avg.t[s]	#opt.	avg.t[s]
		50	20	20	0.02	20	0.00		50	20	20	0.02	20	0.00
		100	20	20	0.02	20	0.00		100	20	20	0.08	20	0.00
		200	20	20	0.09	20	0.00		200	20	20	7.11	20	15.00
	3	400	20	20	0.53	20	0.00	6	400	20	20	0.94	20	680.00
		600	20	20	1.92	20	1.00		600	20	20	2.25	0	3600.00
		800	20	20	2.87	20	3.00		800	20	20	3.70	-	-
		1000 20	20	3.88	20	6.00		1000 20	20	6.00	-	-
		50	20	20	0.02	20	0.00		50	20	20	0.02	20	0.00
		100	20	20	0.04	20	0.00		100	20	20	0.25	20	0.00
		200	20	20	0.55	20	0.00		200	20	20	17.90	20	57.00
	4	400	20	20	0.75	20	7.00	7	400	20	20	0.93	10	3138.00
		600	20	20	2.09	20	41.00		600	20	20	2.43	0	-
		800	20	20	3.14	20	107.00		800	20	20	4.38	-	-
		1000 20	20	4.30	20	294.00		1000 20	20	6.50	-	-
		50	20	20	0.02	20	0.00		50	20	20	0.02	20	0.00
		100	20	20	0.11	20	0.00		100	20	20	0.22	20	1.00
		200	20	20	1.78	20	2.00		200	20	20	2.36	20	250.00
	5	400	20	20	0.84	20	76.00	8	400	20	20	1.04	0	-
		600	20	20	2.28	20	623.00		600	20	20	2.44	-	-
		800	20	20	3.55	13	2735.00		800	20	20	4.35	-	-
		1000 20	20	5.13	0	3600.00		1000 20	20	7.01	-	-

Table 12 :

 12 Results on the set of instances of[START_REF] Delorme | Half-cycle: A new formulation for modelling kidney exchange problems[END_REF] where the objective is the maximisation of the medical benefit.

						BPC results
		Instances
					solved instances		unsolved instances
	L C	|I|	#	#	avg.#nodes avg.t[s]	#	avg.#nodes avg.gap[%]
		50	20	20	1.00	0.05	0	-	-
		100 20 20	1.10	0.02	0	-	-
	3
		200 20 20	1.40	0.09	0	-	-
		400 20 20	24.40	4.80	0	-	-
		50	20	20	1.00	0.05	0	-	-
		100 20 20	2.50	0.07	0	-	-
	4
		200 20 20	66.10	6.97	0	-	-
		400 20	9	1485.22	574.63	11	8452.18	0.07
		50	20	20	1.00	0.05	0	-	-
		100 20 20	3.00	0.18	0	-	-
	5
		200 20 20	154.10	36.59	0	-	-
		400 20	0	-	-	20	2295.15	0.32
		50	20	20	1.00	0.05	0	-	-
		100 20 20	8.85	0.72	0	-	-
	6
		200 20 19	652.79	294.29	1	6989.00	0.04
		400 20	0	-	-	20	834.00	0.56
		50	20	20	1.00	0.02	0	-	-
		100 20 20	14.65	2.44	0	-	-
	7
		200 20 19	1407.32	887.05	1	5965.00	0.01
		400 20	0	-	-	20	466.25	0.55
		50	20	20	1.00	0.02	0	-	-
		100 20 20	8.65	2.45	0	-	-
	8
		200 20 17	344.47	335.58	3	3115.67	0.08
		400 20	0	-	-	20	326.70	0.59

Table 13 :

 13 Statistics on the length of the paths in the optimal solutions of the set of instances of the PrefLib dataset with

	L C = 3.
		Instances			#paths per length[%]
	L P	#	tot.|D| tot.#paths	1	2	3	4	5	6
	3	230	12120	12120	77.02 17.24 5.74	-	-	-
	4	230	12120	12120	77.06 16.96 5.07 0.92	-	-
	5	230	12120	12120	77.09 16.85 5.15 0.65 0.26	-
	6	230	12120	12108	77.27 16.73 5.10 0.64 0.26 0.13

Table 14 :

 14 Impact of the path length increase on the set of instances of[START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] when the objective is the maximisation of the medical benefit (MB).

	Instances	avg.impr[%]
	|I|	#	L P : 3 → 6 L P : 6 → 12
	50	15	9.31	2.13
	100	15	15.77	5.41
	250	15	14.36	5.13

https://www.transplant-observatory.org/

https://www.uwhealth.org/news/uw-health-led-nation-in-paired-kidney-exchanges-in-2020

the code is available online at https://github.com/jeremyomer/KidneyExchange.jl

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.

Throughout the section the percentage optimality gap is computed as 100(U B -LB)/LB, where U B and LB are the upper and lower bounds returned by the BPC algorithm.

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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF].

Table 8 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. The first three columns report some information about the instance subset.

The next three columns summarise the results obtained by the BPC algorithm: number of instances solved to optimality (#opt.), average number of nodes of the branch-and-bound tree (avg.#nodes) and average computational time in seconds (avg.t[s] ). The last column reports the computational time in seconds of the BP algorithm of Arslan et al. (2024) (avg.t[s] ). The authors implemented their BP algorithm using Julia language and ran the experiments on a 2 Dodeca-core Haswell Intel Xeon E5-2680 v3 2.5 GHz machine with 128Go RAM running Linux OS. In this column, we make use of '-' when no result is available: [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] do not test the BP algorithm on instances where only circuits are to be priced, i.e., those with L P = 0. No further information is required about their algorithm, since, it manages to solve to optimality all the instances at the root node. From the results of Table 8, 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), except in one case where the BPC algorithm required the insertion of valid inequalities and the exploration of two nodes. 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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF] is faster than 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 two 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 [START_REF] Arslan | Kidneyexchange. jl: A julia package for solving the kidney exchange problem with branch-and-price[END_REF].

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

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 [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF]. We compare the BPC algorithm performances with the restricted master heuristic of [START_REF] Pansart | Dealing with elementary paths in the kidney exchange problem[END_REF] 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