# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 1 Introduction
In Figure 2a, a vertex \(i\in V\) corresponds to a current incompatible pair consisting of a patient \(i\) and a donor \(i\), and an arc \((i,j)\in A\) indicates the compatibility between donor \(i\) and patient \(j\), which means that donor \(i\) can provide his or her kidney to patient \(j\). Figure 2b demonstrates an example of a feasible solution. The thick arrows represent an exchange cycle among pairs 1, 2, and 4. We now discuss the optimization problem for a KEP, given a KEP graph \(G\). The objective of the optimization of a KEP is generally to maximize the number of possible kidney exchanges in a given pool of candidates, and the KEP can be mathematically modeled as an integer programming problem,  
Figure 1: Illustration of (**a**) two-way and (**b**) three-way kidney exchange program (KEP). Figure 2: Kidney exchange program (KEP) graph (**a**) and its feasible solution (**b**). which is the main focus of this paper. [PERSON] et al. [17] proposed an edge formulation and a cycle formulation for KEPs, and [PERSON] et al. [7] developed a solution algorithm for those formulations. Furthermore, [PERSON] et al. [18] proposed two compact formulations--that is, an edge-assignment (EA) formulation and an extended edge (EE) formulation. [PERSON] and [PERSON] [19] presented how the cycle formulation by [PERSON] et al. [17] can be extended to find optimal solutions for the KEP in the United Kingdom, which are compatible with U.K. National Living Donor Kidney Sharing Schemes (NLDKSS). The reformulation-linearization technique (RLT), which we intend to utilize in this paper, is a procedure that can be used to generate a tight linear programming (LP) relaxation for a discrete optimization problem. Various strong formulations on several classes of structured problems are generated by the RLT. [PERSON] et al. [20] developed a new integer programming model for the traveling salesman problem (TSP) by applying the RLT to the Miller-Tucker-Zemlin (MTZ) formulation. Moreover, they showed that the resulting formulation dominates the lifted-MTZ formulation of [PERSON] [21]. [PERSON] et al. [22] applied the RLT to the path-based TSP model using logical restrictions. They proposed a variety of new formulations for the TSP, and exploited several dominance relationships between them. [PERSON] et al. [23] dealt with a two-level facility location-allocation problem arising from the access network design of a telecommunication network. They developed a mixed-integer program for the problem and applied the RLT to improve computational effectiveness. In this paper, we focus on the best-known compact formulations for the KEP in the literature, which are the EA and EE formulations proposed by [PERSON] et al. [18]. We first induce the EE formulation by applying the partial level 1 RLT to the EA formulation. After that, we further strengthen the formulation via the level 1 RLT and propose a new integer programming model that dominates existing formulations. Computational results are provided to demonstrate the effectiveness of our formulation compared to that of those previous. Therefore, the contribution of our study can be summarized as below. * We propose a new integer programming model, which is proved to be more compact and effective than previous optimization models through computational experiments. Although our new formulation gives a solution that allows only one more patient to have a kidney transplant than the matching solutions made by existing formulations, this is a meaningful result because a kidney transplant is immediately related to the precious life of a patient. Furthermore, our proposed model would be directly related to the performance of the KEP IT healthcare platform. * We derive the EE formulation from the EA formulation by applying a systematic approach, the RLT. As presented by [PERSON] et al. [18], establishing a more compact integer programming formulation requires the exploitation of the special structures inherent to the problem of interest.