Ays ¸e

N Arslan

Jérémy Omer
email: jeremy.omer@insa-rennes.fr

Fulin Yan
email: fulin.yan@insa-rennes.fr

KidneyExchange.jl: A Julia package for solving the kidney exchange problem with branch-and-price

The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when non-directed donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of non-directed donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally present a branch-and-price algorithm based on the position-indexed chain-edge formulation as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the solution of pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances. Our numerical results show that the proposed algorithm can be significantly faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl.

Introduction

The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries. For many patients suffering from a chronic kidney disease, a transplant is an alternative solution which offers longer life expectancy, lower treatment costs, and a better quality of life compared to the more easily accessible solution of dialysis ( [START_REF] Axelrod | An Economic Assessment of Contemporary Kidney Transplant Practice[END_REF]). Although transplants are traditionally performed from a deceased donor, in many countries, the patients are allowed to find a living donor, typically a relative or a friend. Unfortunately, a patient may be incompatible with the person that they designate as their donor. The kidney exchange problem arises from this context: incompatible patient-donor pairs are put in a centralized system, called a kidney exchange program, with a view to find matches between the donors and patients of different pairs.

Transplants in a kidney exchange can be performed in a cyclic manner. In such an exchange, the simplest cycle consists in two pairs swapping their donors so that each patient receives a compatible kidney. This logic can be extended to cycles consisting of more pairs where pairs exchange donors so that each patient receives a compatible kidney. In an increasing number of countries, the law also allows the participation of non-directed donors, individuals who are willing to donate a kidney without being attached to a patient. In this case, transplants are performed in a very similar manner to the cyclic exchange except for the fact that a non-directed donor does not need to receive a transplant in return. Regardless of the type of the exchange, each patient-donor pair and each non-directed donor can participate in at most one exchange. One of the particularities of the kidney exchange problem is that, it is preferable to perform all operations involved in an exchange simultaneously so that no patient looses their donor without receiving a transplant themselves.

Since, transplant operations require multiple operating rooms and an important number of medical staff, this practically restricts the number of pairs that can be in a cyclic exchange to 3 or 4, which is the current state of practice in many countries ( [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF]). This restriction is less strict in the presence of non-directed donors but most countries still limit the number of pairs that can be involved in an exchange initiated by a non-directed donor ( [START_REF] Malik | Foundations and principles of the Canadian living donor paired exchange program[END_REF], [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF]).

The operations research community has long been interested in the optimal solution of the kidney exchange problem and its variants, which led to the development of various mathematical programming formulations and associated solution algorithms. In this work, we concentrate on the optimal solution of the deterministic kidney exchange problem in the existence of non-directed donors. We implement two branch-and-price algorithms based on two different extended formulations previously proposed in the literature [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF][START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] where subproblems are managed through graph copies. We analyze the resulting pricing problems in detail and identify conditions under which they can be solved through polynomial-time algorithms as well as propose numerical improvements to their solution. We propose several improvements to the branch-and-price algorithm specific to the kidney exchange problem. We also adapt existing compact formulations from the literature for use with feedback vertex sets (FVS) proposed by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF]. Our work results in an open source Julia package that integrates state-of-the-art methodology and formulations from the literature, regrouping them on the same easy-to-deploy platform for the first time. Our numerical results show that our implementation of the branch-and-price algorithm can be significantly faster than those proposed in the literature.

The remainder of this article is organized as follows. In Section 2, we formalize the kidney exchange problem and present a literature review. In Section 3, we present and adapt the existing compact mixed-integer programming formulations. In Section 4, we present the branch-and-price algorithm and provide implementation details. In Section 5, we briefly describe the benchmark and our open source Julia package, and we present our numerical results. Conclusions and future research directions are presented in Section 6.

2 Problem description and literature review

Preliminary notations

We first present a few general notations that will be used throughout the article, starting with the problem definition. A (directed) walk p in a directed graph G = (V, A) is a subgraph of G consisting of a sequence of vertices and arcs i 1 , a 1 , i 2 , . . . , a r-1 , i r such that for all 1 ≤ k ≤ r -1, a k = (i k , i k+1 ) ∈ A. Given that we will consider only simple graphs, a walk will be more concisely denoted as p = (i 1 , . . . , i r ) without ambiguity. If p is such that i 1 = i r , then it is a closed walk. A chain is a walk without any repetition of vertices. Although such a walk is more classically referred to as a path, a simple path or an elementary path in the graph theory and network-flow literature (see e.g. [START_REF] Taccari | Integer Programming Formulations for the Elementary Shortest Path Problem[END_REF][START_REF] Ravindra | Network flows[END_REF]), we use the term chain to remain coherent with the kidney exchange literature. A cycle is then a chain such that i 1 = i r , i.e., a closed walk without any repetition of vertices other than the first one. A walk p is neither a chain nor a cycle if and only if it contains a subtour, i.e., a cycle that is strictly contained in p. We will also denote as a ; b the integer interval {a, a+1, . . . , b} for any a, b ∈ Z, a ≤ b.

Problem statement and definitions

An instance of the KEP is characterized by a simple arc-weighted directed graph G = (V, A), and two integers K and L. The set of vertices V is partitioned into P ∪ D, where P represents the patient-donor pairs and D represents the non-directed donors. Each arc (u, v) ∈ A, u ∈ V , v ∈ P, means that the donor in u and the recipient in v are compatible for a transplant. We denote as w a the utility of a transplant represented by arc a ∈ A. It is very common to consider the total number of transplants in the kidney exchange literature, i.e., w a = 1 for a ∈ A. The problem then consists in finding disjoint cycles of length at most K and chains starting from non-directed donors of length at most L in order to maximize the total utility of the arcs covered by these cycles and chains.

For a more concise presentation, any cycle (resp. chain) with length at most K (resp. at most L) will be called a feasible cycle (resp. a feasible chain). We denote the set of all feasible cycles and chains by C K and C L , respectively. For c ∈ C K (resp.c ∈ C L ) we denote by V (c) the set of vertices, and A(c) the set of arcs involved in c. Finally, for any vertex v ∈ V , C K (v) (resp. C L (v)) is the set of cycles in C K (resp. the set of chains in C L ) containing v. We remark that for v ∈ D the set C K (v) is empty.

Literature review

The introduction of the kidney exchange problem is often attributed to Rapaport [START_REF] Felix T Rapaport | [END_REF]. The problem was later formalized by Roth et al. ( [START_REF] Roth | Kidney Exchange[END_REF], [START_REF] Roth | Pairwise Kidney Exchange[END_REF]) and Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] showed that the kidney exchange problem with L = 0 and K ≥ 3 fixed is NP-Hard. Despite this discouraging complexity result, the operations research community has long been interested in the optimal solution of this problem, proposing various compact and extended formulations for the cycles-only and cycles-andchains variants of the problem. Compact formulations can be solved directly using an off-theshelf optimization solver, whereas extended formulations require either cut-or column-generation algorithms in their solution. Below, we present a literature review for the cycles-only and cyclesand-chains variants of the problem, independently. For the sake of conciseness, we do not present the considerable body of literature dealing with variants of the problem under uncertainty (see, for instance, Dickerson et al. [START_REF] Dickerson | Failure-Aware Kidney Exchange[END_REF]).

Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] propose two extended formulations for the cycles-only variant of the problem: edge and cycle formulation (with the latter being also attributed to Roth et al. [START_REF] Roth | Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences[END_REF]). The edge formulation uses flow variables to form cycles and imposes the size limitation with an exponential number of constraints, while the cycle formulation uses an exponential number of cycle selection variables (one variable corresponding to each element of C K ). The first requires cut-generation in its solution whereas the second requires column-generation. Authors report being able to solve instances involving up to 10,000 vertices to optimality using the branch-and-price algorithm with the cycle formulation. They solve the pricing problem using a combination of depth-first-search and heuristic algorithms. In Constantino et al. [START_REF] Constantino | New Insights on Integer-Programming Models for the Kidney Exchange Problem[END_REF] two compact mixed-integer programming formulations are proposed. One of these formulations, the extended-edge (EE) formulation, is based on the idea of creating one copy of the graph for each vertex and constructing cycles involving this vertex in each copy through the use of flow variables. Numerical results are reported, both on Saidman ( [START_REF] Saidman | Increasing the Opportunity of Live Kidney Donation by Matching for Two-and Three-Way Exchanges[END_REF]) and randomly generated instances, comparing the frontal solution of the cycle formulation to that of the compact formulations, with the largest instances considered having 1000 pairs for K = 3. Later, in Klimentova et al. [START_REF] Klimentova | A New Branch-and-Price Approach for the Kidney Exchange Problem[END_REF], Dantzig-Wolfe decomposition is applied to this formulation, which results in a branch-and-price algorithm with many pricing problems (one per vertex). These pricing problems permit searching for exchange cycles involving each vertex independently. Numerical results are reported on Saidman ([33]) instances, comparing different solution strategies as well different objective functions for the column generation algorithm, with the largest instances considered having 2000 pairs for K = 3. In Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF], this idea is further extended, using the concept of feedback vertex sets (FVS). Numerical results are reported on Saidman ( [START_REF] Saidman | Increasing the Opportunity of Live Kidney Donation by Matching for Two-and Three-Way Exchanges[END_REF]) instances available in the PrefLib data set, comparing the branch-and-price algorithm to position-indexed compact formulations ( [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF]), with the largest instances considered having 2048 pairs for K = 6. The authors create a copy only for the vertices in an FVS instead of all vertices. To solve the resulting pricing problems, Klimentova et al. [START_REF] Klimentova | A New Branch-and-Price Approach for the Kidney Exchange Problem[END_REF] apply a combination of a random-walk heuristic and Ford's shortest path algorithm, whereas Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] employ a combination of decision diagrams, depth-first search and mixed-integer programming. Lam and Mak-Hau [START_REF] Lam | Branch-and-Cut-and-Price for the Cardinality-Constrained Multi-Cycle Problem in Kidney Exchange[END_REF] propose to combine the branch-and-price algorithm of Klimentova et al. [START_REF] Klimentova | A New Branch-and-Price Approach for the Kidney Exchange Problem[END_REF] with valid inequalities, giving rise to a branch-and-price-and-cut algorithm. They solve the pricing problems by solving elementary longest path problems on a position-expanded directed acyclic graph through a label-setting algorithm when K = 3, and by exhaustive enumeration otherwise. Numerical results are presented on Saidman ([33]) instances available in the PrefLib data set, comparing the branch-and-price-and-cut algorithm to position-indexed compact models with the largest instances considered having 2048 pairs for K = 4.

Similar to the cycles-only variant, when the possibility of constructing chains is introduced, two main approaches emerge in the literature: using flow variables to form chains starting from non-directed donors or using an exponential number of chain selection variables. In the flow-based models, cycle-flow and chain-flow variables are then distinguished. However, when L ≥ K +1, in the absence of cycle-breaking constraints, it would be possible to construct infeasible cycles (of length ≥ K + 1) using the chain-flow variables. As such, flow-based formulations for the cycles-and-chains variant have been inspired by different modeling techniques used for the traveling salesman and elementary shortest path problems where sub-tour elimination constraints are necessary. In the chain selection-based models, this difficulty emerges in the pricing problem.

In Anderson et al. [START_REF] Anderson | Finding Long Chains in Kidney Exchange Using the Traveling Salesman Problem[END_REF], the authors build on the formulations of Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] to take the existence of unlimited chains into account, inspired by the prize-collecting traveling salesman problem. They propose to solve the resulting formulations using cut generation algorithms. In Mak-Hau [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] authors propose to adapt the extended-edge formulation of Constantino et al. [START_REF] Constantino | New Insights on Integer-Programming Models for the Kidney Exchange Problem[END_REF] to the case of unlimited chains inspired by the Miller-Tucker-Zemlin inequalities for the traveling salesman problem. Their formulation can also be adapted to the case where the chain size is limited. Dickerson et al. [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] propose compact formulations by adding a position index to variables of the extended-edge formulation. The resulting formulation, called the position-indexed edge formulation (PIEF), gives a stronger relaxation than the extended-edge formulation for the cycles-only variant. They call the resulting formulation the hybrid position-indexed edge formulation (HPIEF) for the cycles-and-chains variant. They additionally combine position-indexed variables for chains with cycle selection variables, giving rise to what authors call the position-indexed chain-edge formulation (PICEF). We remark that PICEF can be used as a compact formulation by enumerating the feasible cycles in a pre-processing step, otherwise it needs to be solved using a branch-and-price algorithm generating cycles through the solution of pricing problems. Additionally, this formulation reduces to the cycle formulation of [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] when L = 0. Numerical results are presented on real instances coming from US (UNOS) and UK (NLDKSS) exchanges as well as generated instances based on UNOS data, comparing the position-indexed models to other solvers from the literature for K = 3 and increasing L values, with the largest instances considered having 700 pairs and 25% non-directed donors. Finally, Glorie et al. [START_REF] Kristiaan | Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price[END_REF], Plaut et al. [START_REF] Plaut | Fast optimal clearing of cappedchain barter exchanges[END_REF], and Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] propose branchand-price algorithms that generate both cycles and chains through the solution of pricing problems. We remark that algorithms used in the solution of the pricing problems in both Glorie et al. [START_REF] Kristiaan | Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price[END_REF] and Plaut et al. [START_REF] Plaut | Fast optimal clearing of cappedchain barter exchanges[END_REF] were later shown to be incorrect, i.e., these algorithms may falsely conclude that there are no columns to be added to the master problem. As such, the work of Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] is the only correct branch-and-price algorithm in the literature that generates chains as part of a subproblem for the cycles-and-chains variant. The authors propose a three-phase approach to the solution of pricing problems: a (restricted) decision diagram-based approach, followed by a mixed-integer programming model solved through cut generation, and finally a depth-first search heuristic, followed by the direct solution of a mixed-integer program. In the first phase, they create one decision diagram per non-directed donor and per vertex of an FVS. The former generates chains starting from each non-directed donor, whereas the latter generates cycles starting from each element of the FVS. In the second phase, they solve a relaxed longest-path formulation, which is augmented by cutting planes when necessary. This phase eventually proves that no positive reduced cost chain exists. Finally, in the third phase, positive reduced cost cycles missed in the first two phases are sought, first by depth-first search with a time-limit, and finally by the solution of a flow-based formulation limiting the number of arcs that can be selected to K. Numerical results are presented on Saidman ([33]) instances available in the PrefLib data set, comparing the branch-andprice algorithm to position-indexed compact models with the largest instances considered having 2048 pairs and 15% non-directed donors for K = 4.

While there exists an important body of literature on the exact solution of the KEP, especially its cycles-only variant, the cycles-and-chains variant of the problem is still under investigation with the work of Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] being the current state of the art. The confusion surrounding the solution of subproblems in the existence of non-directed donors, and the associated theoretical and practical difficulty, needs to be clarified. Further, the numerical results in the literature focus mostly on instances from a single type of instance generator (known as the Saidman generator) and the developed algorithms are often inaccessible to researchers. In this work, we address most of these shortcomings. Our contributions include:

• Implementing two branch-and-price algorithms that can solve the cycles-and-chains variant of the kidney exchange problem to exact optimality. Both our implementations gather numerous improvements tailored for the KEP which are detailed in the article. One of these algorithms applies to the position-indexed chain edge formulation (PICEF) of Dickerson et al. [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] and the other is based on the disaggregated cycles and chains formulation DCF of Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF]. To the best of our knowledge, these are the first publicly available implementations of the column generation algorithm for the KEP.

• Integrating the notion of FVS to existing compact formulations, i.e., the extended-edge (EE) formulation [START_REF] Constantino | New Insights on Integer-Programming Models for the Kidney Exchange Problem[END_REF] and the position-indexed edge formulation (PIEF) [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] for the cycles-only variant. We then combine these two formulations with position-indexed chain flow variables in the presence of non-directed donors in order to obtain two compact formulations for the cycles-andchains variant of the problem.

• Gathering state-of-the-art formulations, algorithms, and instance generation schemes on the same easy-to-deploy platform for the first time. Our open source code can be used with different solvers, and facilitates development and numerical testing of new formulations/algorithms.

• Assessing the numerical performance of the two branch-and-price algorithms, as well as the compact formulations on a large benchmark with instances coming from different generators (including the Saidman generator). The largest instances tested include 10,000 pairs and 1,000 non-directed donors. This is, to the best of our knowledge, the first time such large instances are attempted in the literature for the cycles-and-chains variant (the seminal work of Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] considered the cycles-only variant with K = 3), and the first publicly available implementation to do so.

Compact integer programming formulations

In this section, we first adapt the extended-edge [START_REF] Constantino | New Insights on Integer-Programming Models for the Kidney Exchange Problem[END_REF] and position-indexed edge [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] formulations for the cycles-only variant to the case where graph copies are created based on a feedback vertex set (FVS). An FVS is a set of vertices, that we denote by S ⊆ P in the following, whose removal from G leads to an acyclic graph. Any cycle in G passes through at least one vertex s ∈ S, and it therefore suffices to consider only the elements of an FVS in creating the graph copies. We remark that the cycles-only formulations we present here reduce to those presented in the literature when S = P .

To calculate an FVS, we start by removing the vertices with in-degree or out-degree equal to zero from consideration. We then consider the remaining vertices in P in order of decreasing total degree. When considering a vertex s, we first add it in S and then we create a graph copy G s = (V s , A s ) with vertices V s and arcs A s . To determine V s , we use the pairwise distances d(s, v) and d(v, s) for v ∈ P , where d(s, v) is the length of the shortest path from s to v and is set to +∞ when no such path exists. If d(s, v) + d(v, s) > K, vertex v cannot be part of a cycle with length at most K including s, so we do not include v in V s . The set of arcs, A s , is then equal to (V s × V s ) ∩ A. This set can further be reduced using the pairwise distances. More specifically, if d(s, i) + d(j, s) + 1 > K, then arc (i, j) can be removed from A s . Once a vertex is considered in order, we reduce the in-degree of each of its forward neighbors as well as the out-degree of each of its backward neighbors and we remove it from G along with its incoming and outgoing arcs. The process continues until there are no vertices with positive in-and out-degree.

Let x s u,v take value 1 if arc (u, v) ∈ A s is selected in graph copy s ∈ S and 0 otherwise. The extended-edge formulation based on FVS, S, is then written as:

max s∈S (u,v)∈A s w u,v x s u,v (1)
s.t. s∈S v|(u,v)∈A s x s u,v ≤ 1 ∀u ∈ P (2) v|(v,u)∈A s x s v,u = v|(u,v)∈A s x s u,v ∀s ∈ S, u ∈ V s (3) (u,v)∈A s x s u,v ≤ K ∀s ∈ S (4) v|(u,v)∈A s x s u,v ≤ v|(s,v)∈A s x s s,v ∀s ∈ S, u ∈ V s (5) x s u,v ∈ {0, 1} ∀s ∈ S, (u, v) ∈ A s . (6)
Here, constraints (2) impose that each vertex u ∈ P can be part of at most one cycle across all copies s ∈ S, (3) are flow-balance constraints and ensure that the flow in each copy s ∈ S forms cycles, (4) impose the cycle-size limit K and ensure that only feasible cycles are formed, and finally (5) break symmetries by ensuring that at least one of the cycles created in graph copy s ∈ S starts from vertex s. The objective function maximizes the total utility. We remark that constraints [START_REF] Ashlagi | Kidney Exchange in Dynamic Sparse Heterogenous Pools[END_REF] do not eliminate all symmetries since it is still possible for the same cycle to be created in multiple copies when K ≥ 4.

Similarly, let x s u,v,l take value 1 if arc (u, v) ∈ A s is selected in position l = 1, . . . , K in copy s ∈ S and 0 otherwise. The position-indexed formulation based on FVS, S, is then written as:

max s∈S (u,v)∈A s K l=1 w u,v x s u,v,l (7)
s.t. s∈S v|(u,v)∈A s K l=1 x s u,v,l ≤ 1 ∀u ∈ P (8) v|(v,u)∈A s x s v,u,l = v|(u,v)∈A s x s u,v,(l+1) s ∈ S, ∀u ∈ V s \ s, l = 1, . . . , K -1 (9) K l=2 v|(v,s)∈A s x s v,s,l = v|(s,v)∈A s x s s,v,1 s ∈ S ( 10
)
x s u,v,l ∈ {0, 1} ∀s ∈ S, (u, v) ∈ A s , l = 1, . . . , K. (11)
Here, constraints [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF] impose that each vertex u ∈ P can be part of at most one cycle across all copies s ∈ S, and ( 9) and ( 10) are flow-balance constraints and ensure that at least one of the cycles created in graph copy s ∈ S starts from vertex s. The objective function maximizes the total utility.

In order to form chains, we use the position-indexed chain-flow variables y u,v,l that take value 1 if arc (u, v) ∈ A is selected in position l = 1, . . . , L of a chain and 0 otherwise. We write:

L l=1 v|(u,v)∈A y u,v,l ≤ 1 ∀u ∈ V (12) v|(v,u)∈A y v,u,l ≥ v|(u,v)∈A y u,v,(l+1) ∀u ∈ P, l = 1, . . . , L -1 (13) v|(u,v)∈A y u,v,1 = 0 ∀u ∈ P (14) v|(u,v)∈A y u,v,l = 0 ∀u ∈ D, l = 2, . . . , L (15)
y u,v,l ∈ {0, 1} ∀(u, v) ∈ A, l = 1, . . . , L. (16)
Here, constraints [START_REF] Desaulniers | Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems[END_REF] impose that each vertex is involved in at most one chain, (13) are flow balance constraints and ensure that a chain is formed, ( 14)-( 15) impose that only non-directed donors can initiate a chain and therefore appear in position l = 1 and only in position l = 1.

We then combine ( 12)-( 16) with the FVS-based cycles-only formulations presented above. The first compact formulation we obtain is novel, to the best of our knowledge, and is written as:

max s∈S (u,v)∈A s w u,v x s u,v + (u,v)∈A L l=1 w u,v y u,v,l (17)
s.t. ( 3) -( 6), ( 13)

-(16) ( 18
)
s∈S v|(u,v)∈A s x s u,v + L l=1 v|(u,v)∈A y u,v,l ≤ 1 ∀u ∈ V. (19)
The second compact formulation we obtain is an adaptation of the HPIEF to the case where the graph copies are generated from an FVS. This formulation is written as:

max s∈S (u,v)∈A s K l=1 w u,v x s u,v,l + (u,v)∈A L l=1 w u,v y u,v,l (20)
s.t. ( 9) -( 11), ( 13) -(16) ( 21)

s∈S v|(u,v)∈A s K l=1 x s u,v,l + L l=1 v|(u,v)∈A y u,v,l ≤ 1 ∀u ∈ V. (22)
In order to further reduce symmetries in the case of integer weights, the objective function of the two models can be modified by multiplying terms w u,v x s u,v and w u,v x s u,v,l by 1 + ℓ(s)/ρ, where ℓ(s) is the index (position) of s in S and ρ can be set to any large enough value that guarantees that the optimal solution to the modified model is optimal for the initial one. This modification prioritizes the use of arc (u, v) in forming cycles rather than chains. Between cycles that can be obtained in multiple graph copies, those that are obtained from a larger-indexed copy are preferred. In practice, ρ can be set to (w max * |P | 2 ) where w max = max (u,v)∈A w u,v . Indeed, at most P arcs can be chosen in a solution and ℓ(s) ∈ {1, . . . , P }, ∀s, where ℓ(s) = P for at most one copy s, so that

s∈S (u,v)∈A s K l=1 ℓ(s) w max * |P | 2 w u,v x s u,v,l < 1.
For integer weights, this guarantees that the ranking of solutions can be changed only if they have the same total weight in the initial problem.

It is additionally worth noting that ( 12)-( 16) can be combined with any existing cycle-based formulation, making sure that every vertex is involved in at most one cycle or chain, in order to obtain a valid formulation for the cycles-and-chains variant of the problem. For instance, the PICEF is obtained by combining ( 12)-( 16) with the cycle formulation (see Appendix).

Branch-and-price algorithm

In this section, we provide the most important details behind our implementation of the branchand-price algorithm. We consider the disaggregated cycle and chain formulation DCF proposed by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] as well as the position-indexed chain-edge formulation (PICEF) proposed by Dickerson et al. [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF]. In both formulations, graph copies {G s = (V s , A s )} for s ∈ S, of G, based on an FVS, are used to decompose the pricing problem. These copies are obtained as described in Section 3. We additionally create a graph copy G s for each non-directed donor s ∈ D in a similar manner when using DCF. That is, starting from each non-directed donor s ∈ D, we calculate the distance d(s, v) for v ∈ P , and we include only those vertices with

d(s, v) ≤ L in V s . The set of arcs A s is then constituted as (V s × V s ) ∩ A. Denoting as C s K (resp. C s L ) the set of feasible cycles (resp. chains) in G s for s ∈ S (resp. s ∈ D), C s K (v) (resp. C s L (v)) the set of cycles in C s K (resp. chains in C s K ) including vertex v ∈ V s and w(c) the utility of cycle c ∈ C s K (resp. chain c ∈ C s L )
, DCF can be formulated as follows:

(DCF) :

               max s∈S c∈C s K w(c)x c + s∈D c∈C s L w(c)x c s.t. s∈S c∈C s K (v) x c + s∈D c∈C s L (v) x c ≤ 1 ∀v ∈ V x c ∈ {0, 1} ∀c ∈ (∪ s∈S C s K ) ∪ (∪ s∈D C s L ). ( 23
)
The linear relaxation of DCF, DCF LP , is obtained by dropping the integrality restrictions on variables x c . We use a column generation algorithm to solve DCF LP . Accordingly, at iteration i ∈ Z + of the algorithm, we consider Ĉs,i K ⊆ C s K for s ∈ S and Ĉs,i L ⊆ C s L for s ∈ D. In replacing C s K and C s L by Ĉs,i K and Ĉs,i L , respectively, we obtain a restriction of DCF LP , that we denote as RMP. Let the optimal solution of RMP at iteration i be denoted by xi , and let λ i denote a vector of optimal dual variables associated to constraints [START_REF] Lam | Branch-and-Cut-and-Price for the Cardinality-Constrained Multi-Cycle Problem in Kidney Exchange[END_REF], with λ i v denoting the dual variable associated to vertex v ∈ V . The reduced cost of a cycle (resp. chain

) c ∈ C s K (resp. c ∈ C s L ) is given as w(c) -v∈V (c) λ v .
The pricing problem for graph copy G s for s ∈ S ∪ D is then the decision problem that either identifies a positive reduced cost cycle or chain in G s or concludes that none exists. We present our approach to the solution of these pricing problems in detail in Section 4.1.

If any positive reduced cost cycle or chain is detected through the solution of these pricing problems then Ĉs,i K and Ĉs,i L are augmented with these new columns. Otherwise, xi is an optimal solution of RMP which can be extended to an optimal solution of DCF LP by setting

x c = xi c for c ∈ Ĉs,i K and c ∈ Ĉs,i L and x c = 0 for c ∈ C s K \ Ĉs,i K and c ∈ C s L \ Ĉs,i L .
We remark that, as there are |S| + |D| pricing problems, an implementation choice needs to be made in terms of whether or not to solve all subproblems at each iteration as well as in which order to explore the subproblems. We present our approach to managing this algorithmic choice in detail in Sections 4.3 and 4.3.2. Let z LP be the optimal value of DCF LP and z lb the objective value of the best integer solution found. If z lb = z LP (which is true, for instance, if the optimal solution of DCF LP is integer), then DCF is solved to optimality. Otherwise, it is necessary to branch. Following the conclusions of Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF], we chose to branch on arcs in A instead of branching on the cycles and chains or on the arcs of the graph copies G s , s ∈ S ∪ D. As such, we identify an arc (u, v) ∈ A such that 0 < fu,v :=

s∈S c∈C s K |(u,v)∈A s (c) xc + s∈D c∈C s L |(u,v)∈A s (c) xc < 1.
We branch on the arc (u, v) such that fu,v is closest to 0.5. Branching is performed by adding the following constraint in DCF.

s∈S c∈C s K |(u,v)∈A s (c) x c + s∈D c∈C s L |(u,v)∈A s (c) x c ≤ 0 (≥ 1) (24)
Denoting µ, the dual variable associated to this branching constraint, the effect on the pricing problem associated to s ∈ S ∪ D is the addition of the term µ I s c (u, v) in the reduced cost of a cycle (resp. chain), where I s c (u, v) is an indicator function that takes value 1 if (u, v) ∈ A s (c), and 0 otherwise for given c ∈ C s K ∪ C s L . In Section 4.1, pricing problems are presented by taking the effect of these branching constraints into account.

In the case of PICEF, the branch-and-price algorithm changes slightly since only cycles are generated through the solution of subproblems. In particular, all cycle selection variables x c for s ∈ S, c ∈ C s K may be integer in a fractional solution. In this case, there is necessarily (u, v) ∈ A and l ∈ 1 ; L such that 0 < y u,v,l < 1. We then branch by imposing that either arc (u, v) is part of a solution, L l=1 y u,v,l ≥ 1, or not, L l=1 y u,v,l ≤ 0. This branching choice does not affect the reduced cost of cycles.

The pricing problem

In the remainder of the section, we will call a feasible cycle or chain with positive reduced cost a positive cycle or a positive chain unless stated otherwise.

The purpose of the pricing problem is to find a positive cycle or chain or prove that none exists. It has been shown (see for instance [START_REF] Kristiaan | Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price[END_REF][START_REF] Plaut | Fast optimal clearing of cappedchain barter exchanges[END_REF]) that finding a positive cycle or showing that none exists can be done in polynomial time. The proof relies on the study of a dynamic programming algorithm similar to the Bellman-Ford algorithm. In the same articles, the authors have adapted this algorithm to the search for positive chains, but it has later been demonstrated by Plaut et al. [START_REF] Plaut | Hardness of the Pricing Problem for Chains in Barter Exchanges[END_REF] that the resulting algorithms are incorrect. Indeed, for K = 0 and L = |V |, finding a positive chain starting from an non-directed donor or proving that none exists amounts to solving an elementary longest path problem, which is known to be an NP-Hard problem in the presence of positive cost cycles (see e.g. [START_REF] Taccari | Integer Programming Formulations for the Elementary Shortest Path Problem[END_REF]). However, in the kidney exchange problem, K and L are not arbitrary, with the current practice typically limiting K to less than 4 and L to less than 6 ( [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF]). One consequence of this is that adaptations of the Bellman-Ford algorithm are still able to solve the pricing problem in many cases.

At each iteration of the column generation algorithm, we search for a positive cycle in each copy G s , s ∈ S, and a positive chain in each copy G s , s ∈ D. By construction of the copies, there is no positive cycle or chain in G if none is found in G s , ∀s ∈ S ∪ D. In this search, the reduced cost of a chain or cycle c is denoted by w(c). As discussed in [START_REF] Kristiaan | Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price[END_REF], w(c) can be expressed as the sum of weights on the arcs wu,v , ∀(u, v) ∈ A(c) if branching is performed as described in [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 instance, at the root node, we have

w(c) = (u,v)∈A(c) w u,v - v∈V (c) λ v regardless of whether c is a cycle or chain. Setting wu,v = w u,v -λ v , ∀(u, v) ∈ A, we obtain w(c) = (u,v)∈A(c)
wu,v for any cycle c. If c is a chain, the dual cost of the initial non-directed vertex must be added to the reduced cost, so we may set wu,v = w u,v -λ u -λ v for all (u, v) ∈ A such that u ∈ D. At any other node i of the branching tree, we let A i be the set of arcs on which branching was performed. We then write wu,v = w u,v -λ v -µ u,v , for (u, v) ∈ A i where µ u,v is the dual variable associated to the branching constraint on (u, v) (similarly for the case of chains). The reduced cost of arcs (u, v) ∈ A \ A i remain unchanged.

In the remainder, we first show that a polynomial-time dynamic programming algorithm can be used to identify positive columns in a large variety of cases, even when chains are allowed. When no positive chain or cycle is found by this polynomial algorithm, we state conditions under which no such cycle or chain exists and we describe an alternative procedure when these conditions do not hold. Given that most of the branch-and-price solution time is spent in searching for positive columns, we also provide some details on the algorithmic improvements that lead to significant reduction in computational time.

Dynamic programming search for positive cycles

The search for a positive cycle in graph copy G s , for s ∈ S, is described by the pseudo-code in Algorithm 1. It is similar to the K first iterations of the classical Bellman-Ford algorithm for maximum cost walks starting from vertex s ∈ S. The algorithm computes walks p k (v) from s to v with exactly k arcs and their weights wk (v) for all v ∈ V s , k ∈ 0 ; K . The walk obtained by adding arc (v r , v) ∈ A s to any walk p = (v 1 , . . . , v r ) is denoted as p|v. For each k ∈ 0 ; K , the algorithm stores in Q k the list of vertices v such that wk (v) > -∞ to avoid considering vertices that cannot be reached with exactly k arcs from s.

Let P s k be the set of walks of G s with length k starting from s, and among those let P s k (v) be the walks from s to v, v ∈ V s . With these notations, it is straightforward to show that the values computed by Algorithm 1 satisfy, for all v ∈ V s , the classical Bellman-Ford recurrence relation:

max p∈P s k (v) { w(p)} = max u|(u,v)∈A s wuv + max p ′ ∈P s k-1 (u) { w(p ′ )} .
As a consequence, we can directly describe the behavior of the algorithm by the following property.

initialization: w0 (s

) := 0, w0 (v) := -∞, ∀v ∈ V s \ {s} Q 0 := {s}, p 0 (s) := (s) 1 for k ∈ 1 ; K do 2 wk (v) := -∞, ∀v ∈ V s , Q k := ∅, 3 for u ∈ Q k-1 do 4 for (u, v) ∈ A s do 5 if wk-1 (u) + wuv > wk (v) then 6 wk (v) ← wk-1 (u) + wuv 7 p k (v) ← p k-1 (u)|v 8 Q k ← Q k ∪ {v} 9 k * =
• Q k = {v ∈ V : P s k (v) ̸ = ∅}; • ∀v ∈ V, wk (v) = max{ w(p) : p ∈ P s k (v)}.
As a result of Property 1, Algorithm 1 calculates the maximum reduced cost walk of length k from s to s for k ∈ 1 ; K . Since the longest walk problem is a relaxation of the (elementary) longest path problem, this directly guarantees that Algorithm 1 returns an empty walk if and only if there is no positive cycle going through s in G s . When the algorithm returns a positive walk, this walk may contain a subtour if its length is greater than or equal to four. In this case, the contained subtour necessarily has positive length, and constitutes a positive cycle that can be added to the restricted master problem.

Dynamic programming search for positive chains

The search for a positive chain starting from vertex s ∈ D is described by the pseudo-code in Algorithm 2. It starts with the same Bellman-Ford iterations as in Algorithm 1, and returns the first positive chain found, if any.

Property 1 also applies to Algorithm 2. This means that the algorithm computes a maximum reduced cost walk with l arcs from s to each vertex v ∈ V s for l ∈ 1 ; L . The algorithm returns such a walk only if it has positive reduced cost and it can verify that it is a chain. Therefore, if Algorithm 2 returns a non-empty walk then G s contains a positive chain that can be added to RMP. However, when the algorithm returns empty, it may be due to two reasons: (i) there are no positive walks, or (ii) all the positive walks found by the algorithm contain a subtour and therefore are not chains. In the first case, we may conclude that there are no positive chains in G s since the longest walk problem is a relaxation of the (elementary) longest path problem, resulting in the following property.

Property 2. If wl (v) ≤ 0, for all l ∈ 1 ; L and all v ∈ V s when Algorithm 2 returns, then there exists no positive chain in G s . initialization: w0 (s) := 0, w0 (v) := -∞, ∀v ∈ V s \ {s} Q 0 := {s}, p 0 (s) := (s) Despite this positive result, G s may still contain a positive chain starting from s while Algorithm 2 fails to find any, even when G s contains no positive cycle with length at most K. Indeed, Algorithm 2 may return empty in the case where all positive walks contain an infeasible subtour (i.e., a positive cycle of length ≥ K +1) while failing to identify the existence of a positive chain. We illustrate this behavior on an example that was proposed by Plaut et al. [START_REF] Plaut | Hardness of the Pricing Problem for Chains in Barter Exchanges[END_REF] with K = 3 and L = 5 which is reproduced in Figure 1. The example relies on the existence of a positive cycle of length K + 1 = 4, (p 1 , p 2 , p 3 , p 4 , p 1 ), which conceals the only positive chain, (s, p 5 , p 2 , p 3 , p 4 , p 1 ), whose length is L = 5. On this example, Algorithm 2 will identify the walk (s, p 1 , p 2 , p 3 , p 4 , p 1 ) as the longest walk from s to p 1 , and will return empty since all identified walks are either of non-positive weight or contain an infeasible subtour. We remark that, this would not be an issue if K was larger, in which case the positive cycle (p 1 , p 2 , p 3 , p 4 , p 1 ) could be returned to the master problem, or if L was smaller, in which case no walk from s to v ∈ V s \ {s} could contain an infeasible cycle.

1 for l ∈ 1 ; L do 2 wl (v) := -∞, ∀v ∈ V s , Q l := ∅, 3 for u ∈ Q l-1 do 4 for (u, v) ∈ A s do 5 if wl-1 (u) + wuv > wl (v) then 6 wl (v) ← wl-1 (u) + wuv 7 p l (v) ← p l-1 (u)|v 8 Q l ← Q l ∪ {v} 9 for l ∈ 1 ; L do 10 for v ∈ V s do 11 if wl (v) > 0 and p l (v) is a chain then 12 return p l (v)
As a matter of fact, it is possible to find a positive cycle or chain or prove that none exists in polynomial time through executions of Algorithms 1 and 2 when L ≤ K + 1. We formalize this result in the following proposition.

Proposition 1. If L ≤ K + 1 and G s does not contain any positive cycle, G s contains a positive chain if and only if Algorithm 2 returns a non-empty walk when applied to G s . Proof. It is clear that G s contains a positive chain if Algorithm 2 returns a non-empty walk. To prove the reverse implication, observe that vertex s corresponds to a non-directed donor, hence has no incoming arc. As a consequence, any subtour of a walk starting from s with length at most L has length at most L -1. If L -1 ≤ K and G s does not contain any positive cycle, then any such subtour has a nonpositive reduced cost. As a result, there exists a longest walk from s to v ∈ V s \ {s} that does not contain a subtour and is therefore a chain. Hence, G s contains a positive chain starting from s only if it contains a positive walk starting from s. Property 2 then yields the result.

Corollary 1. The graph G s contains a positive chain with length at most K + 1 if and only if G s does not contain any positive cycle and Algorithm 2 returns a non-empty walk when applied to G s .

As a conclusion, we are now able to state a set of necessary conditions for Algorithms 1 and 2 to conclude incorrectly that there are no positive cycles and chains to be added to RMP.

Proposition 2. The execution of Algorithm 1 for G s , ∀s ∈ S, and of Algorithm 2 for G s , ∀s ∈ D, is not sufficient to solve the pricing problem if all of the following conditions are satisfied simultaneously:

1. G does not contain any positive cycle;

2. for all s ∈ D, G does not contain any positive chain starting from s with length at most K + 1;

3. for all s ∈ D, Algorithm 2 returns an empty chain when applied to G s ; 4. there exists s ∈ D such that Algorithm 2 finds a positive walk that includes a subtour, i.e., there exists v ∈ V s and l ∈ K + 2 ; L such that wl (v) > 0.

The above conditions are all met in the counterexample proposed by Plaut et al. [START_REF] Plaut | Hardness of the Pricing Problem for Chains in Barter Exchanges[END_REF], but they seem to be difficult to reproduce in the context of the column generation algorithm using realistic instances of the KEP. We remark, for instance, that the graph of the counterexample (Figure 1) does not contain any cycle with length at most 3. Moreover, the reduced costs given in the example are possible only if arcs do not all have the same weight, so this instance could not be obtained in the context of maximizing the number of transplants. Despite this, to prove the optimality of a solution of RMP, we need to be able to certify that no positive column exists when the conditions of Proposition 2 are not met. We propose to solve an IP formulation in this case. We present one such formulation in the next section.

Integer programming formulation of the pricing problem

As stated above, the execution of Algorithm 1 is sufficient to identify a positive cycle if G contains one. Moreover, the execution of Algorithm 2 is sufficient to prove that no feasible positive chain starting from s ∈ D exists if the algorithm does not identify any positive walk starting from s. As a consequence, it is only when the above conditions are not satisfied that we need another solution approach to search for a positive chain in G s , for s ∈ D.

The problem that needs to be solved in order to identify positive chains is a variant of the elementary shortest path problem (ESPP) in the presence of negative cycles. Various integer programming formulations of the ESPP have been studied and compared in Taccari [START_REF] Taccari | Integer Programming Formulations for the Elementary Shortest Path Problem[END_REF]. In their numerical analysis, the best results were obtained with a strengthened version of the classical Dantzig-Fulkerson-Johnson formulation based on subtour elimination. This model requires a fixed sink vertex, so we add an artificial vertex t to G s , for s ∈ D, together with a set of incoming arcs {(u, t) : ∀u ∈ V s }. The resulting graph is denoted by Ĝs = (V s ∪ {t}, Âs ) where Âs = A s ∪ {(u, t) : ∀u ∈ V s }. The model then involves a set of arc variables y u,v for (u, v) ∈ Âs . We adapt the formulation of Taccari [START_REF] Taccari | Integer Programming Formulations for the Elementary Shortest Path Problem[END_REF] to the search for positive chains in Ĝs as follows: max

(u,v)∈A s wu,v y u,v (25)
s.t.

v|(v,u)∈A s y v,u - v|(u,v)∈A s y u,v ≥ 0 ∀u ∈ V s \ {s} (26) v|(s,v)∈A s y s,v = 1 ( 27
)
v∈V s y v,t = 1 ( 28
) (u,v)∈A s y u,v ≤ L ( 29
) (u ′ ,v ′ )∈ Âs |u ′ ∈U,v ′ / ∈U y u ′ ,v ′ ≥ v|(u,v)∈A s y u,v , ∀U ⊆ V s \ {s}, ∀u ∈ U ( 30
)
y u,v ∈ {0, 1} ∀(u, v) ∈ A s . (31)
Constraints ( 26)-( 29) are flow constraints and they bound the length of the walk to L. Constraints [START_REF] Roth | Kidney Exchange[END_REF] are called generalized cutset inequalities (GCS). They eliminate subtours by ensuring that for all subsets of V s \ {s}, the number of arcs outgoing from the set is larger than the number of arcs outgoing from any vertex of the set. There is an exponential number of GCS inequalities, so they are added in a cut generation procedure. The specificity of our application is that when solving this integer program, we know that the graph does not contain any positive cycle (with length ≤ K), and probably a very small number of positive reduced cost cycles with length at most L -1 > K. So we separate GCS inequalities only for integer solutions of the relaxed problem.

Given that the cardinality of the support of such a solution is bounded by L + 1, separation can be done quickly by searching for connected components using Tarjan's algorithm [START_REF] Endre | Edge-Disjoint Spanning Trees and Depth-First Search[END_REF]. If the optimal value of this model is non-positive for s ∈ D then G does not contain any positive chains.

Algorithmic improvements

It has been observed, in the literature, that the solution of the pricing problem takes the most significant amount of time when solving the kidney exchange problem using the column generation algorithm (see for instance [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF]). As such, significant numerical gains can be obtained by improving the implementation of the pricing algorithms used. In this section, we provide several insights on the algorithmic choices that had most impact on our implementation. We first remark that several immediate improvements over the presented versions of Algorithms 1 and 2 can be obtained by storing only the predecessors of the vertices in the computed walks, and stopping the algorithm as soon as a positive cycle is found. Moreover, in the last iteration of the algorithm, it suffices to update the distance labels only for the arcs going to the source.

Further, a significant improvement can be obtained by adding to the lists of reachable vertices only those vertices that can be involved in a positive cycle or chain. More specifically, denoting the maximum arc reduced cost by wmax = max a∈A wa , the maximum cost of a cycle going through vertex v ∈ V s is wk (v) + (K -k) wmax which is an upper bound obtained at iteration k ≤ K of Algorithm 1. So vertex v is added to Q k at step 8 of Algorithm 1 only if wk (v) + (K -k) wmax > 0. Algorithm 2 can be improved similarly.

Finally, in most of the instances considered in the literature, the arc weights are based solely on the destination vertex and not the source vertex. This reflects, for instance, the maximization of the number of transplants, in which case the arc weight is equal to one, independent of the donor. It can also reflect situations where different weights are assigned to the patient-donor pairs depending on the level of urgency of the transplant expected by the patient (and any donor is equally acceptable). Denoting the weight of vertex v ∈ V by w v , the weight of each arc (u, v) ∈ A is then given by w u,v = w v . When treating the root node of the branch-and-price tree, this means that the reduced cost of an arc may also be written as the sum of independent terms depending on one extremity of the arc. More specifically, for all (u, v) ∈ A, we have:

wu,v = w v -λ v , if u ∈ P w v -λ v -λ u , if u ∈ D.
We remark then that, at any iteration k of Algorithms 1 and 2, and for any vertex v ∈ P , and

u 1 , u 2 ∈ V \ D predecessors of v, we have wk-1 (u 1 ) ≥ wk-1 (u 2 ) =⇒ wk-1 (u 1 ) + wu1,v ≥ wk-1 (u 2 ) + wu2,v .
As a consequence, if we sort Q k-1 by decreasing values of wk-1 (•), we need to treat at most one arc entering each vertex v ∈ P . This means that Algorithms 1 and 2 can be executed in O(K |V |) and O(L |V |), respectively, instead of O(K |A|) and O(L |A|). This observation is unfortunately only valid at the root node of the branch-and-price tree since the dual variables introduced by branching on arcs destroy the above cost structure. However, the numerical improvement obtained is still significant since most calls to Algorithms 1 and 2 are done at the root node (see 4.2 for details on the quality of the linear relaxation).

Heuristic search for a feasible solution and branching rules

As already observed by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF], DCF has a very strong linear relaxation. Indeed, in our numerical tests, we found the dual bound provided by DCF LP to be exact for almost all of the instances tested. On the other hand, optimal solutions provided by DCF LP are not always integer. As such, it might be important to search for integer solutions to prove that the integrality gap is indeed zero in order to avoid unnecessary branching.

To this end, when the column generation algorithm converges with a fractional optimal solution, we solve the integer programming counterpart of RMP, RMP IP , to find an integer feasible solution. In most cases, RMP IP and RMP have the same optimal value, so it is sufficient to solve RMP IP in order to prove optimality. However, in some other cases, there is a gap between the values of RMP IP and RMP, and branching is performed. Unfortunately, branching may prove inefficient in improving the incumbent solution: RMP has many alternative optimal solutions and branching on a single arc is often not sufficient to eliminate all fractional solutions. As such, it might be necessary to explore multiple vertices down the branching tree before an integer solution can be found.

The most promising strategy then seems to be spending an extra computational effort in searching for a feasible solution at the root node. We thus implemented a heuristic algorithm that generates new cycles and chains in the hope that they will be selected to create an integer solution with an improved value. To do so, we randomly choose and remove half of the cycles and chains from RMP and solve it by column generation a second time. Every new column is then added to RMP IP before solving it again. This strategy works particularly well for the kidney exchange problem because there are many feasible solutions with the same value (see, for instance, [START_REF] Carvalho | A Theoretical and Computational Equilibria Analysis of a Multi-Player Kidney Exchange Program[END_REF], [START_REF] Farnadi | Individual Fairness in Kidney Exchange Programs[END_REF]). It is often possible to find an integer solution with the same value as the bound provided by DCF LP through combinations of new columns. When this strategy does not prove successful it is necessary to branch as described at the beginning of the section.

Column generation strategies

The goal of the pricing problem is to find at least one positive cycle or chain in each graph copy G s , s ∈ S ∪D. As mentioned in Section 4.1.4, when executing Algorithms 1 and 2, we always return the first positive cycle or chain found during the dynamic programming search. Alternatively, one can retain all positive cycles/chains obtained from a copy and return one with the most positive reduced cost.

The latter strategy has been tested, but it was significantly less efficient for two reasons. First, it requires that every iteration is completed in Algorithms 1 and 2 instead of terminating them early when possible. Second, it favors long cycles and chains, especially in the first iterations of the column generation algorithm, even though it is possible to obtain optimal solutions including short cycles and chains.

In the remainder of the section, we discuss how to take advantage of the packing constraints ( 23) to accelerate the search of cycles and chains in some graph copies. We then describe a strategy that ignores graph copies where no positive cycle or chain was found in a previous column generation iteration.

Vertex-disjoint columns

The only constraints of DCF, the packing constraints [START_REF] Lam | Branch-and-Cut-and-Price for the Cardinality-Constrained Multi-Cycle Problem in Kidney Exchange[END_REF], impose that for each vertex v ∈ V , at most one cycle or chain involving this vertex will be selected in any feasible solution. Similar constraints in crew scheduling problems, imposing that each task must be assigned at most once, lead Desaulniers et al. [START_REF] Desaulniers | Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems[END_REF] to generate task disjoint columns at each iteration of the column generation algorithm. In this context, a column is a rotation consisting of a sequence of tasks that can be assigned to an employee. Two columns or rotations are task-disjoint when the rotations have no task in common.

In the kidney exchange problem, a column is a cycle or a chain, so two columns are said to be vertex-disjoint when the corresponding cycles/chains do not have any vertex in common. In order to impose the generation of vertex-disjoint columns in the context of sequential treatment of graph copies by Algorithms 1 and 2, it suffices to remove the vertices that are already covered by the walks found for subsequent copies. More specifically, if some positive cycle or chain c is found in graph G s for some s ∈ S ∪ D, then every vertex of c can be removed from the graph copies that still need to be treated. In particular, if there is v ∈ V (c) such that v ∈ S, then G v does not even need to be treated.

Enforcing the generation of vertex-disjoint columns may yield smaller pricing solution time by reducing the size and number of graph copies to be treated as outlined above. On the other hand, the ability to find an optimal solution by solving RMP IP will depend on the size and diversity of the pool of columns used in RMP IP . Imposing a pure vertex-disjoint column generation strategy unfortunately produces a smaller pool of columns. As such, there is a trade-off between the ability to quickly solve pricing problems and the ability to produce integer solutions at the root node. In our implementation, we manage this trade-off by generating no more than κ columns covering the same vertex at each iteration.

Finally, the sets S and D are randomly shuffled before each iteration of the column generation algorithm in order to promote diversity in the pool of columns generated. Without this operation, imposing vertex-disjoint column generation may often concentrate on the same graph copies while ignoring others.

A tabu list of graph copies

The last strategy that we implemented in our branch-and-price algorithm consists in ignoring a graph copy G s , s ∈ S ∪ D, if no positive cycle or chain was found in it in a previous column generation iteration. It may be numerically advantageous to do so for two reasons. First, the dual solution of RMP does not change much from one iteration to another, and when it does, it usually leads to larger dual values hence smaller values of wu,v for (u, v) ∈ A because more vertices are covered at each iteration. As a consequence, it is unlikely that a positive cycle or chain is found in G s if none was found at a previous iteration. Further, the executions of Algorithms 1 and 2 that end up returning empty are the most time-consuming ones.

In practice, if Algorithm 1 or 2 returns empty when executed on G s , s ∈ S ∪ D, we store s in a tabu list L. At each iteration of the column generation algorithm, we then search for a positive cycle or chain in G s for s ∈ (S ∪ D) \ L. Eventually, we obtain L = S ∪ D at which point we empty L and execute Algorithm 1 or 2 once more on each copy. If no positive column is found then we proceed to certifying the optimality of the current RMP solution. To do so, we need to guarantee that Algorithm 2 did not falsely conclude that no positive chain could be found. As such, we verify the conditions of Proposition 2 and if they are satisfied, we solve the integer programming formulation of the pricing problem presented in Section 4.1.3. We remark that this IP formulation does not need to be solved up to this point and is only solved if a certain number of conditions are satisfied simultaneously.

Numerical experiments

In this section, we present the numerical results obtained on a benchmark using our branch-andprice implementations as well as the compact MIP formulations presented in Section 3.

All our experiments are conducted using a 2 Dodeca-core Haswell Intel Xeon E5-2680 v3 2.5 GHz machine with 128GB RAM running Linux OS. The resources of this machine are strictly partitioned using the Slurm Workload Manager 1 to run several tests in parallel. The resources available for each run (algorithm-instance) are set to 4 cores and a 20GB RAM limit (we remark that our branchand-price algorithms do not benefit from parallel processing since we choose to solve the pricing problems for each graph copy sequentially). This virtually creates six independent machines, each running one single instance at a time. All linear and mixed integer linear programs, are solved using Gurobi 9.1.2 with default parameters and a single thread.

Description of the benchmark

Our benchmark includes randomly generated instances based on three different generators described in the literature, i.e., the Saidman generator presented in Saidman et al. [START_REF] Saidman | Increasing the Opportunity of Live Kidney Donation by Matching for Two-and Three-Way Exchanges[END_REF], the heterogeneous generator presented in Ashlagi et al. [START_REF] Ashlagi | Kidney Exchange in Dynamic Sparse Heterogenous Pools[END_REF], and the sparse generator presented in Dickerson et al. [START_REF] John P Dickerson | Optimizing Kidney Exchange with Transplant Chains: Theory and Reality[END_REF]. Our implementation of these random generators is mostly a translation of the corresponding Java functions in the code publicly shared by John Dickerson 2 . Saidman instances were often used in the literature in order to test branch-and-price implementations. For instance Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF], Mak-Hau [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] and Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] have used Saidman instances that are publicly available in the PrefLib data set. This set, contains 310 instances, and consists of 10 randomly generated instances of kidney exchanges with 16, 32, 64, 128, 256, 512, 1024, 2048 pairs and, as a percentage of the number of pairs, non-directed donors at 0%, 5%, 10%, and 15%.

The Saidman generator involves generating patients with random characteristics such as blood type, sex, and probability of being tissue-type incompatible with a randomly chosen donor based on low, medium or high percentage reactive antibodies (PRA) levels for the patient. These probabilities follow real-world population data. Each patient is then assigned a randomly generated potential donor with random blood type and relation to the patient. If the patient and potential donor are incompatible, the two are entered into the kidney exchange program as a pair. Blood and tissue type information is then used to determine compatibility information within the exchange program. The sparse generator is based on the Saidman generator, it adjusts the probabilities used by the generator in order to mimic the state of the UNOS pool as of April, 2013. The resulting instances are sparser since both the probability of a patient having high PRA and the probability 1 https://slurm.schedmd.com/ (accessed July 2022) 2 Github repository of the code: https://github.com/JohnDickerson/KidneyExchange of incompatibility in this case (as well as for low and medium PRA cases) are increased. The heterogeneous generator, on the other hand, is based on the existence of two types of patients: low PRA and high PRA. While the probability that a low PRA-patient being compatible with the donor of another pair is quite high, this probability is very low for high PRA-patients (also known as highly sensitized patients).

A Julia package for the kidney exchange problem

The solution methods described in Sections 3 and 4 and the random generation of instances have been implemented using the Julia language [START_REF] Bezanson | Julia: A Fresh Approach to Numerical Computing[END_REF]. Every interaction with mathematical programming models and solvers is managed using the functions of the mathematical optimization package JuMP [START_REF] Dunning | JuMP: A Modeling Language for Mathematical Optimization[END_REF]. Our implementation can be used with different mathematical programming solvers. Among these, Gurobi and CPLEX are two commercial solvers that may currently be used with a free academic license, and the other three are free and open software. The solver may be chosen among HiGHS [START_REF] Huangfu | Parallelizing the dual revised simplex method[END_REF], GLPK3 , Cbc [START_REF] Forrest | To-St. COIN-OR Branch-and-Cut Solver[END_REF], Gurobi4 , CPLEX 5 or a combination of GLPK as the linear programming solver and Cbc as the integer programming solver. For reproducibility of our results and in order to facilitate future research on the topic, our code is publicly available on Github6 [4]. It is distributed under an MIT license. As a consequence, if one of the three open solvers is selected, the code can be used by anyone under a permissive open license. It is currently the first publicly available implementation that allows to solve the kidney exchange problem with an efficient branch-and-price algorithm.

We have chosen Julia for its great prototyping capabilities, its high performance and the existence of a rich and mature ecosystem of optimization packages 7 . In our view, just as Python or other non-compiled languages, Julia yields easy to read code, which should help understand our technical choices of implementation for those interested in these details. Our code is distributed as a Julia package KidneyExchange.jl. As such, it can readily be installed from any Julia prompt with a single command. Documentation of available functions is available on the Github repository of the package or directly from a Julia prompt. Given that no external library is required, there is no real knowledge required in order to reproduce our results. We also sincerely hope that these choices will encourage the dynamic research community working on the subject to contribute some of their developments to this package. For instance, new instance generation strategies such as in Delorme et al. [START_REF] Delorme | Improved Instance Generation for Kidney Exchange Programmes[END_REF] or cutting planes in the spirit of Lam and Mak-Hau [START_REF] Lam | Branch-and-Cut-and-Price for the Cardinality-Constrained Multi-Cycle Problem in Kidney Exchange[END_REF] can be implemented in our package with minimal effort.

Numerical Results

In this section, we numerically test and compare our branch-and-price implementations as well as the compact formulations proposed in Section 3 on a number of benchmark instances. For all results presented in this section, the parameter κ that governs the maximum number of columns involving a given vertex that can be generated in an iteration of the column generation algorithm is set to 6.

Comparison of compact formulations on smaller instances

In this first set of numerical tests, we compare the numerical performance of the two compact MIP formulations proposed in Section 3 (( 17)-( 19) and ( 20)-( 22)). We test these formulations on the three types of instances of our benchmark, i.e., Saidman, heterogeneous and sparse, with instance sizes |P | ∈ {128, 256, 512, 1024}. For each instance type and size, we fix the number of non-directed donors at 10% of the number of pairs and generate 10 instances. We choose parameters K = 3 and L ∈ {4, 6} as representative of the current kidney exchange practice. We remark that the Saidman instances we use are those provided in the PrefLib data set. In Figure 2, we present the number of instances solved (out of 40 instances) using each compact formulation as a function of time (with a time limit of 2 hours). While both formulations managed to solve the smaller instances with 128 and 256 pairs within seconds, the extended-edge based formulation ( 17)- [START_REF] Forrest | To-St. COIN-OR Branch-and-Cut Solver[END_REF] started to struggle, especially with Saidman instances, starting from 512 pairs. Neither formulation could solve instances with 1024 pairs successfully (with the exception of the sparse instances with K = 3 and L = 4) even with all the model reductions and the symmetry breaking objective function. In Table 4 in the Appendix, we provide further insight into these results by providing the average solution time for those instances that were solved to optimality. The reported times do not include the time required to build the models using JuMP which may be as large as 35 minutes for the larger Saidman instances. We remark that when instances are not solved to optimality both models terminate with extremely large optimality gaps.

Based on these results, the position-indexed model performs better than the extended-edgebased model although for smaller instances the two models are comparable. There does not seem to be a gain from the smaller number of variables afforded by the extended-edge-based model. The superior linear relaxation of the position-indexed HPIEF model justifies the increased number of variables. Finally, not surprisingly, sparse instances are those better solved by the compact formulations. Indeed, these instances require a smaller number of variables in the first place, and profit more from further model reduction based on pairwise distances.

Comparison of branch-and-price algorithms on PrefLib instances

In this section, we compare the two branch-and-price algorithms we have implemented, one based on the disaggregated cycle and chain formulation DCF [START_REF] Lam | Branch-and-Cut-and-Price for the Cardinality-Constrained Multi-Cycle Problem in Kidney Exchange[END_REF] and the other based on the positionindexed chain edge formulation PICEF proposed by Dickerson et al. [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF]. The difference between these two algorithms comes from the treatment of chains in each formulation. While DCF uses chain selection variables and generates chains through the solution of subproblems, PICEF generates chains through the use of position-indexed chain edge variables. Both formulations use cycle selection variables and generate cycles through the solution of subproblems. In the algorithm based on PICEF, we initially generate up to 20 cycles of size 2 per vertex and add them to the restrictions Ĉs K , s ∈ S to warm up dual values.

As is typically done in the literature, we test both algorithms on PrefLib instances with |P | ∈ {16, 32, 64, 128, 256, 512, 1024, 2048} and the number of non-directed donors expressed as a percentage of the number of pairs (5%,10% and 15%). There are a total of 230 instances. We choose K ∈ {3, 4} and L ∈ {3, 4, 5, 6}. We remark that DCF and PICEF lead to the same algorithm when there are no non-directed donors in the graph or when L = 0. In Figure 3, we present the number of instances solved to optimality as a function of time by both algorithms. The DCF-based algorithm was able to solve all instances under 20 seconds whereas the PICEF-based algorithm was not able to solve some of the largest (|P | = 2048) instances when L ∈ {5, 6}. The PICEF-based algorithm was faster for the smaller instances (|P | ≤ 128), whereas the DCF-based algorithm outperformed it for larger instances. This was especially the case for larger values of L where the DCF-based algorithm was one-to-two orders of magnitude faster. Additionally, the DCF-based algorithm solved all instances at the root node except for one whereas the PICEF-based algorithm treated up to 5 nodes for the largest instances.

We should remark that while this manuscript was under revision, Delorme et al. [START_REF] Delorme | Improved Instance Generation for Kidney Exchange Programmes[END_REF] proposed a matheuristic that is based on blood-type compatibility information of Saidman instances. This matheuristic is capable of solving PrefLib instances with K = 3, 4 and L = 0 within seconds. However, its performance is less reliable when the instances are modified through various changes proposed to the Saidman generator. It also cannot treat the chains-and-cycles variant and relies on enumerating certain types of cycles which will become more cumbersome if K is allowed to grow larger than 4. The conclusions of Delorme et al. [START_REF] Delorme | Improved Instance Generation for Kidney Exchange Programmes[END_REF] additionally highlight the importance of exact solvers for the kidney exchange problem: "..., the lack of a guarantee of optimality would be a major drawback, as exact approaches are strongly favoured for optimisation problems where the objective function may impact on human lives".

Branch-and-price performance on larger instances

In this section, we test the DCF-based branch-and-price algorithm on larger kidney exchange instances. We test on the three types of instances, Saidman, heterogeneous and sparse, with |P | ∈ {2048, 6000, 10000} and the number of non-directed donors fixed at 10%. We choose K ∈ {2, 3, 4} and L ∈ {0, 4, 6}. We use the instances provided in the PrefLib data set for Saidman instances when |P | = 2048. Otherwise, all instances are randomly generated and there are 10 instances in each category.

We remark that real-life kidney exchanges currently involve significantly less pairs than the instances we consider in this section ( [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF], [START_REF] Ferrari | Kidney Paired Donation: Principles, Protocols and Programs[END_REF]). Nevertheless, we have several motivations for testing our approach on these large instances the first and foremost being to test its scalability. It is additionally expected that kidney exchanges will grow further by increased public confidence and awareness, by the creation of cross-border exchange programs and by inclusion of compatible pairs in programs ( [START_REF] Biró | Modelling and Optimisation in European Kidney Exchange Programmes[END_REF], [START_REF] Ferrari | Kidney Paired Donation: Principles, Protocols and Programs[END_REF]). Finally, reproducing a similar performance to that reported by the seminal work of Abraham et al. [START_REF] Abraham | Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges[END_REF] was also important from a scientific point of view since their code was not publicly available to researchers.

The number of instances solved to optimality is given in Table branch-and-price algorithm was able to solve almost all of the instances considered for K ∈ {3, 4} and L ∈ {0, 4, 6} with the exception of one sparse instance for K = 4 and L = 0 for which an optimality gap of 0.015% was obtained. We further report the average solution times for these instances in Table 2. We remark that the largest Saidman instances (2048 pairs with 205 nondirected donors ) from the PrefLib library were solved within seconds whereas Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] have reported solution times of up to 20 minutes for these instances, although it should be noted that their code is in C++ and they use CPLEX 12.10 as their solver, so a clear comparison cannot be made. Similarly, heterogeneous and sparse instances were solved to optimality successfully, although the solution time was significantly higher. The difficulty of solving such instances was noted by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] who constructed sparse instances starting from PrefLib instances by removing arcs according to a given highly sensitized patient percentage and compatibility failure probability for these patients. In their numerical results, most of these instances with 256 and 512 patients were not solved to optimality within 30 minutes. This rather counter intuitive difference of difficulty between PrefLib (Saidman) and sparse/heterogeneous instances can be explained by the existence of alternative solutions. Indeed, sparse/heterogeneous instances contain less possibilities to construct exchange cycles and chains. It therefore becomes more critical to find the right columns that constitute the optimal solution. This is not the case for denser instances such as PrefLib (Saidman) instances since there are many alternative optimal solutions. In this case, it is possible to achieve convergence adding only small cycles and chains, which favors our implementation (recall that we exit the pricing routine as soon as a positive reduced cost cycle/chain is found). Nonetheless, these results indicate that our branch-and-price algorithm is able to solve instances that could not be solved with existing methods, and can be up to two orders of magnitude faster. Additionally, this is, to the best of our knowledge, the first time such large instances (|P | ∈ {6000, 10000}) are solved to optimality for the cycles-and-chains variant in the literature.

On the other hand, the algorithm was not able to solve some Saidman instances for K = 2 and L = 0 and some sparse instances for K = 2 and L ∈ {4, 6} although the maximum optimality gap among all the instances that were not solved to optimality was 0.38%. Indeed, these instances include many alternative optimal solutions. Branching, therefore, seems ineffective in this case, especially for the denser Saidman instances. While the maximum number of nodes explored with K ∈ {3, 4} and L ∈ {0, 4, 6} was 29 with 82% of instances solved at the root node, when K = 2 and L = 0 the branch-and-price algorithm has explored as much as 18,000 nodes. When K = 2 and L = 4, 6, the difficulty of solving the master problem was also an important factor. In this case, almost 95% of the solution time for the instances that were not solved to optimality was spent trying to solve RMP IP . The results provided here are, to the best of our knowledge, the first numerical tests for K = 2 and various values of L. Indeed, the problem can be solved through a polynomial-time matching algorithm when K = 2 and L = 0. For this reason, branch-and-price algorithms have historically not been tested for K = 2. Our findings highlight that this case would merit further investigation when L ̸ = 0.

We finally comment on the value of long chains for these instances. To this end, we compare the optimal value for K = 3 when increasing the value of L. Increasing the value of L from 0 to 4 increases the objective value by 9.5%, 13%, and 5.4% on average for heterogeneous, Saidman and sparse instances, respectively. Increasing the value further from 4 to 6 only has an impact on the heterogeneous instances with an average increase of 0.4% (similar values are obtained when K = 4). These findings support those of Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] with a larger benchmark. Indeed, chains do not need to be very long in order to have a significant impact and the added value of longer and longer chains seems to be marginal.

Impact of algorithmic choices

In this section, we evaluate the impact of certain algorithmic choices on the DCF-based branch-andprice algorithm. To do so, we choose the creation of graph copies based on an FVS, S versus the complete set of pairs, P as proposed by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF] (fvs), the generation of vertexdisjoint columns as proposed in Section 4.3.1 (vdjcol), the use of a tabu list for subproblems as proposed in Section 4.3.2 (tabu), and the use of the restart strategy for generating integer optimal solutions at the root note as proposed in Section 4.2 (restart).

For reasonable use of numerical resources, we use the three types of instances from our benchmark, Saidman, heterogeneous and sparse, with |P | ∈ {2048, 6000} and non-directed donors at 10% . We fix K = 3, L = 6. The results are presented in Table 3 as a percentage difference from the default version of the DCF-based branch-and-price algorithm where we apply all of the algorithmic choices listed above. We present three metrics, the total solution time (Solution time), the number of columns generated at the root node (#Columns), and the number of calls made to the pricing algorithms, Algorithm 1 and 2, (#Call SP). In this table, we present 5 different versions of the DCF-based branch-and-price algorithm: a version where the FVS-based graph copies are turned off, a version where the vertex-disjoint column generation is turned off, a version where the tabu list for treating the subproblems is turned off, a version where the vertex-disjoint column generation and the tabu list are turned off, and finally a version where all of these are turned off. The default version of the algorithm was able to solve all of the instances considered here at the root node without recourse to the restart strategy for finding integer solutions. As such, in the results presented in Table 3 we do not consider this algorithmic choice.

Based on the results presented in Table 3, turning off each algorithmic choice leads to a degradation in the solution time, except for the FVS-based graph copies, where the solution time may decrease for the smaller (|P | = 2048) instances. The decrease in the solution time can be explained by the preprocessing time required to calculate the FVS. Indeed, it is possible that for smaller instances this preprocessing time is more important than any numerical gains obtained for the branch-and-price algorithm. We also remark that the difference in this case is in the order of milliseconds. On the other hand, the increase in the solution time by turning certain options off is more significant. For instance, turning off the vertex-disjoint column generation causes the solution time to worsen up to an order of magnitude for heterogeneous and Saidman instances while significantly increasing the number of columns added to RMP. When coupled with the tabu list being turned off this effect is further amplified with the effect of the tabu list being turned off on its own being much less significant. Interestingly, turning the FVS-based graph copies off on top off vertex-disjoint column generation and the tabu list often improves the solution time while decreasing the number of columns at the root node although the number of calls made to pricing algorithms increases substantially.

As can be expected, turning off the FVS-based graph copies causes an increase in the number of calls made to the pricing algorithms, as does turning off the vertex-disjoint column generation and the tabu list. When compared to the last two, the effect of FVS-based graph copies alone seems marginal especially for heterogeneous and Saidman instances. Indeed, using FVS-based graph copies seems to be computationally advantageous only for the sparse instances based on our results.

We finally evaluate the effect of the restart strategy used at the root node. To this end, we choose instances solved at the root node by the default version of the DCF-based branch-and-price algorithm for which RMP IP was called twice. These are instances for which an integer optimal solution at the root node was not readily available after the first execution of the column generation algorithm but was found after deleting half the columns and restarting the algorithm. There were only 3 such instances in the sparse category with parameters K = 3, L = 4 and K = 3, L = 6. Turning the restart off for these instances causes the solution time to increase on average by a factor of 3.5 for L = 4 and 4.1 for L = 6. Across the three instances the maximum number of nodes explored increases from 1 to 21 for L = 4 and to 25 for L = 6.

Conclusions and future research directions

In this article, we present a branch-and-price algorithm for the exact solution of the kidney exchange problem in the presence of non-directed donors. This algorithm is based on the disaggregated cycle and chains formulation where the graph copies are created using a feedback vertex set (FVS) as proposed by Riascos-Álvarez et al. [START_REF] Carolina Riascos-Álvarez | A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem[END_REF]. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation (PICEF) proposed by Dickerson et al. [START_REF] Dickerson | Position-Indexed Formulations for Kidney Exchange[END_REF] as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 non-directed donors. Our numerical results show that the proposed algorithm can be significantly faster compared to the state-of-the-art, and can solve instances that could not previously be solved in the literature such as sparse instances and very large instances. They also highlight the consequent gains that can be obtained based on our algorithmic improvements. This efficient branch-and-price algorithm additionally permits us to test the importance of the chains on very large instances. Our findings indicate that chains do not need to be very long in order to obtain significant objective improvements.

An important aspect that we did not consider in this article is the presence of uncertainty. Indeed, the compatibility information considered for solving the deterministic problem is susceptible to change once additional tests are performed. In this case, the planned cycles cannot be performed whereas the chains can only be partially performed. In order to overcome this difficulty it is then appropriate to consider a version of the problem under uncertainty either through stochastic or robust optimization paradigms. The existence of an efficient deterministic solver can then significantly improve the solution of these versions under uncertainty as the deterministic problem can show up as a subproblem (see for instance [START_REF] Smeulders | Recourse in Kidney Exchange Programs[END_REF]). This is especially the case since the linear relaxation of the disaggregated cycles and chains formulation is often very strong. Future work may consider this aspect and evaluate the value of considering uncertainty in the problem description with different optimization under uncertainty paradigms.

13 return () Algorithm 2 :Figure 1 :

 21 Figure1: Reproduction of the counterexample of Plaut et al.[START_REF] Plaut | Hardness of the Pricing Problem for Chains in Barter Exchanges[END_REF]

Figure 2 :

 2 Figure 2: Performance profiles comparing the two compact formulations.

K = 4 , L = 6 Figure 3 :

 463 Figure 3: Performance profiles comparing the two branch-and-price algorithms on the PrefLib instances.

  argmax k∈ 1;K wk (s) 10 if wk * (s) > 0 then

	11	return p k * (s)
	12 else

13 return () Algorithm 1: Dynamic programming search for a positive cycle in G s Property 1. At the end of any iteration k ∈ 1 ; K of the for loop of Algorithm 1, Q k is the set of vertices that can be reached from s with exactly k arcs, and for all v ∈ Q k , wk (v) is the maximum reduced cost of a walk with length k from s to v in G s . More formally, we have

Table 1 :

 1 Number of instances solved to optimality using the DCF-based branch-and-price algorithm on larger instances.

	1. We first remark that the

Table 2 :

 2 Average solution time (for instances solved to optimality) using the DCF-based branchand-price algorithm on larger instances.

	6000	10000

Table 3 :

 3 Indicators represented as percentage difference from the default version of the DCF-based branch-and-price algorithm for different versions based on listed algorithmic choices.

					Solution time	#Columns	#Call SP
		fvs vdjcol tabu 2048	6000	2048	6000	2048	6000
			✓	✓	-0.7	8.9	-14.6 -16.4	16.3	27.2
		✓		✓	260.6 977.0 296.5 611.7 201.2	398.4
	heterogeneous	✓	✓		13.8	49.3	0.0	-0.2	60.4	81.1
		✓			300.6 1060.8 305.3 637.9 459.2	977.1
					158.1 506.2 106.3 233.9 620.5 1254.0
			✓	✓	-5.1	7.4	-6.2	-12.9	24.7	20.0
		✓		✓	581.8 1114.4 474.3 721.9 364.4	540.2
	Saidman	✓	✓		3.9	-2.5	3.7	1.3	34.6	10.6
		✓			728.9 1429.9 515.9 771.9 925.9	976.2
					535.9 1073.1 362.9 430.2 2126.3 2266.9
			✓	✓	19.0	20.8	2.4	-3.3	28.9	27.4
		✓		✓	22.1	73.3	36.1	51.5	20.1	31.5
	sparse	✓	✓		6.6	7.5	4.2	0.1	64.6	26.8
		✓			19.7	82.3	38.2	56.1	111.5	119.3
					50.9	98.9	64.2	93.8	197.3	261.7

GLPK website: https://www.gnu.org/software/glpk/

CPLEX website: https://www.gurobi.com

Gurobi website: https://www.ibm.com/products/ilog-cplex-optimization-studio

Github repository: https://github.com/jeremyomer/KidneyExchange.jl

See the JuMP-dev organization

Acknowledgements

The authors gratefully thank Pierre Navarro, CNRS research engineer at IRMAR, for his skillful support with Julia Language.

For the purpose of Open Access, a CC-BY public copyright licence has been applied by the authors to the present document and will be applied to all subsequent versions up to the Author Accepted Manuscript arising from this submission.

Funding

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

Availability of data and materials

The PrefLib instances studied in this article are publicly available. Other instances can be randomly generated using the Julia package available through our GitHub repository. URLs are included in this published article. The randomly generated instances used in this article as well as the analysed results are available through the corresponding author upon reasonable request.

Code availability

The full code was made available for review and is publicly available through our GitHub repository. We remark that a set of optimization packages were used in this study, that were either open source or available for academic use. Specific references are included in this published article.

Conflict of interest

The authors declare that they have no conflict of interest. Appendix 6.1 Position-indexed chain-edge formulation (PICEF)

s.t.

Here, constraints [START_REF] Saidman | Increasing the Opportunity of Live Kidney Donation by Matching for Two-and Three-Way Exchanges[END_REF] impose that each vertex is involved in at most one chain or cycle, (34) are flow balance constraints and ensure that a chain is formed by the chain-flow (y) variables, ( 35)- [START_REF] Endre | Edge-Disjoint Spanning Trees and Depth-First Search[END_REF] impose that only non-directed donors can initiate a chain and therefore appear in position l = 1 and only in position l = 1.

Detailed numerical results