# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 5 Computational Results
\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}  & \(T_{\text{IP}}\) & \(T_{\text{IP}}\) & **GAP** & \(T_{\text{IP}}\) & **GAP** & \(T_{\text{IP}}\) & **GAP** & \(T_{\text{LP}}\) & **T\({}_{\text{IP}}\)** & **GAP** \\ \hline \multirow{3}{*}{\(k=3\)} & \(n=10\) & 0.00 & 0.00 & 10.7\% & 0.00 & 0.00 & 8.7\% & 0.00 & 0.01 & 6.7\% \\  & \(n=20\) & 0.00 & 0.01 & 87.5\% & 0.00 & 0.00 & 68.2\% & 0.02 & 0.03 & 67.8\% \\  & \(n=30\) & 0.02 & 0.53 & 98.1\% & 0.01 & 0.01 & 84.2\% & 0.29 & 0.11 & 83.9\% \\ \hline \multirow{3}{*}{\(k=4\)} & \(n=10\) & 0.00 & 0.00 & 4.3\% & 0.00 & 0.00 & 3.3\% & 0.00 & 0.00 & 3.0\% \\  & \(n=20\) & 0.00 & 0.01 & 45.1\% & 0.00 & 0.00 & 39.0\% & 0.00 & 0.00 & 38.1\% \\  & \(n=30\) & 0.02 & 1.68 & 37.3\% & 0.01 & 0.02 & 33.2\% & 0.22 & 0.05 & 33.1\% \\ \hline \multirow{3}{*}{\(k=5\)} & \(n=10\) & 0.00 & 0.00 & 4.7\% & 0.00 & 0.00 & 4.2\% & 0.00 & 0.00 & 3.8\% \\  & \(n=20\) & 0.00 & 0.01 & 17.9\% & 0.00 & 0.01 & 14.8\% & 0.02 & 0.03 & 14.1\% \\  & \(n=30\) & 0.02 & 0.76 & 18.0\% & 0.01 & 0.07 & 15.9\% & 0.34 & 0.10 & 14.9\% \\ \hline \multirow{3}{*}{\(k=6\)} & \(n=10\) & 0.00 & 0.00 & 0.0\% & 0.00 & 0.00 & 0.0\% & 0.00 & 0.00 & 0.0\% \\  & \(n=20\) & 0.00 & 0.01 & 10.5\% & 0.00 & 0.01 & 9.6\% & 0.02 & 0.04 & 9.5\% \\ \cline{1-1}  & \(n=30\) & 0.01 & 0.59 & 10.9\% & 0.01 & 0.12 & 9.6\% & 0.59 & 0.27 & 9.6\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Computational results for low-density instances. EA: edge-assignment; EE: extended edge; RLT: reformulation-linearization technique; GAP: optimality gap. solution quality--that is, our approach produces more reliable and higher quality solutions than the best-known compact formulations, without compromising computational time. Similarly, Table 2 demonstrates the computational results for medium-density instances. According to the results, the average GAP was smaller than for the low-density instances for all the formulations. Having such a result is intuitive because the medium-density graph had more arcs representing compatibility; thus, feasible solutions could be more easily found than in the low-density cases. In the experiments, the EE formulation found the optimal upper bounds for 83 out of 120 instances. Our RLT formulation improved the upper bounds of 17 out of the remaining  
Figure 5: Box plots of optimality gaps (GAPs) for low-density instances. 37 instances whose optimal solutions were not obtained by the EE formulation. When it comes to the box plots of the GAPs for the medium-density problem instances, we are able to make similar observations to those for the low-density instances as presented in Figure 6. As mentioned previously, compared to the low-density case, there were more combinations of \((n,k)\) for which the GAPs of all the problem instances were equal to zero (i.e., (j), (k) and (l) in Figure 6). Figure 6: Box plots of optimality gaps (GAPs) for medium-density instances. Finally, the computational results for the high-density instances are presented in Table 3. We observe that the GAPs of all the formulations were equal to 0 for all the instances; hence, we here compare them in terms of the computational time only. As presented in Table 3, in terms of computational time, the RLT formulation outperformed the EA formulation, but the EE formulation performed slightly better than the RLT formulation. However, both cases were reasonably acceptable for practical-size problems. We remark that high-density instances rarely appear in real-world situations, as a donor is unlikely to find as many compatible patients as in high-density cases in a given pool of candidates.