# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 6 Conclusions  
In this paper, we first show that the EE formulation, until now considered to be the most compact formulation, can be systematically derived from the EA formulation through the RLT process. A previous study developed the EE formulation by exploiting special structures inherent to the problem. However, we show that we can readily apply the RLT procedure to the EA formulation to obtain the same EE formulation. Furthermore, we apply the RLT to the EA and EE formulations and thereby derive a tighter and more compact formulation. Computational results show that the proposed RLT model outperforms the existing EA and EE formulations in terms of solution quality as well as computational time. Specifically, the RLT model provides improved GAPs in several instances \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Problem Instances**} & \multicolumn{3}{c}{**EA**} & \multicolumn{3}{c}{**EE**} & \multicolumn{3}{c}{**RLT**} \\ \cline{2-10}  & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** \\ \hline \multirow{3}{*}{\(k=3\)} & \(n=10\) & 0.00 & 0.00 & 22.0\% & 0.00 & 0.00 & 16.2\% & 0.00 & 0.00 & 16.0\% \\  & \(n=20\) & 0.01 & 0.95 & 22.2\% & 0.00 & 0.01 & 20.8\% & 0.05 & 0.07 & 20.5\% \\  & \(n=30\) & 0.03 & 238.11 & 7.1\% & 0.03 & 0.09 & 7.0\% & 0.05 & 0.12 & 6.9\% \\ \hline \multirow{3}{*}{\(k=4\)} & \(n=10\) & 0.00 & 0.00 & 9.7\% & 0.00 & 0.02 & 6.3\% & 0.00 & 0.01 & 5.1\% \\  & \(n=20\) & 0.01 & 0.41 & 6.2\% & 0.00 & 0.06 & 6.0\% & 0.53 & 0.41 & 6.0\% \\  & \(n=30\) & 0.02 & 100.95 & 0.0\% & 0.03 & 0.93 & 0.0\% & 0.68 & 1.55 & 0.0\% \\ \hline \multirow{3}{*}{\(k=5\)} & \(n=10\) & 0.00 & 0.00 & 7.8\% & 0.00 & 0.00 & 5.7\% & 0.00 & 0.01 & 3.8\% \\  & \(n=20\) & 0.01 & 0.22 & 2.9\% & 0.00 & 0.07 & 2.9\% & 0.40 & 0.58 & 2.9\% \\  & \(n=30\) & 0.02 & 12.55 & 0.0\% & 0.02 & 0.38 & 0.0\% & 0.29 & 0.67 & 0.0\% \\ \hline \multirow{3}{*}{\(k=6\)} & \(n=10\) & 0.00 & 0.00 & 6.3\% & 0.00 & 0.00 & 5.5\% & 0.00 & 0.01 & 4.8\% \\  & \(n=20\) & 0.01 & 0.11 & 1.1\% & 0.00 & 0.07 & 1.1\% & 0.27 & 0.76 & 1.1\% \\ \cline{1-1}  & \(n=30\) & 0.02 & 3.91 & 0.0\% & 0.03 & 0.25 & 0.0\% & 0.19 & 0.42 & 0.0\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Computational results for medium-density instances. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Problem Instances**} & \multicolumn{3}{c}{**EA**} & \multicolumn{3}{c}{**EE**} & \multicolumn{3}{c}{**RLT**} \\ \cline{2-10}  & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** & \(\mathbf{T_{\text{LP}}}\) & \(\mathbf{T_{\text{IP}}}\) & **GAP** \\ \hline \multirow{3}{*}{\(k=3\)} & \(n=10\) & 0.00 & 0.02 & 0.0\% & 0.00 & 0.01 & 0.0\% & 0.02 & 0.03 & 0.0\% \\  & \(n=20\) & 0.01 & 1.20 & 0.0\% & 0.01 & 0.14 & 0.0\% & 0.96 & 0.31 & 0.0\% \\  & \(n=30\) & 0.03 & 57.15 & 0.0\% & 0.03 & 0.7 for which the EE formulation could not find the optimal solutions within the time limit--especially for low- and medium-density graphs. For high-density instances, although the RLT model does not significantly reduce the execution time, it can produce the same high-quality solutions as the existing formulations. We believe that, given the results obtained by the proposed model, it could be utilized in the integrated KEP IT healthcare platform to obtain optimized KEP exchange plans. As extended research, several models derived from that proposed in this paper can be considered. For example, firstly, a problem dealing with fair allocations, such as in terms of donor and patient age and health, among the pairs in the candidate pool may be interesting. Indeed, some problems of fairness in kidney transplantation or kidney exchange are discussed by [PERSON] et al. [27] and by [PERSON] [15] respectively in literature.