# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 5 Computational Results  
In this section, we present the results of the computational experiments for the KEP. The experiments were performed using an Intel(R) Core(TM) i7-4770 CPU @ 3.40 GHz, and CPLEX 12.4 as a LP/MIP (mixed integer programming) optimization solver. The experiments were designed to compare the EA, EE, and RLT formulations in terms of performance. Problem instances were  
Figure 4: Illustration of the reformulation-linearization technique (RLT) for deriving new valid inequalities. constructed as by [PERSON] et al. [18]. A random generator that created random KEP graphs of chosen certain arc densities was used. To be specific, on each position of the node adjacency matrix of a graph, a probability \(p\) is used to determine whether the element equals 1 or 0. [PERSON] et al. [18] used values of 0.2, 0.5, and 0.7 for the probability \(p\). However, it was found that with probabilities of 0.5 and 0.7, almost every instance had an optimal objective \(n\) equal to the number of nodes. Because \(n\) is the trivial upper bound of these KEP problems, no formulation can improve the linear relaxation bound of such problem instances. Thus, because an important goal of this paper is to compare the tightness of KEP formulations, \(p\) was set to 0.1, 0.2, and 0.5 for low-, medium-, and high-density instances, respectively. For each density, we generated the problem instances with the input parameter \(k=3,4,5,6\). In addition, \(n\), the number of pairs, was further set to 10, 20, and 30 for each \(k\). For each \(n\) and \(k\), 10 instances were generated and tested. All the cases were executed within a time limit of 3600 s. The formulations were compared in terms of the optimality gap (GAP) and the execution time. The GAP is calculated by \((Z_{\text{LP}}-Z_{\text{IP}})/Z_{\text{IP}}\), where \(Z_{\text{IP}}\) is the best objective function value of the integer programming model and \(Z_{\text{LP}}\) is the optimal objective function value of the corresponding linear programming relaxation. Hence, the lower the GAP obtained, the better the solution (i.e., closer to the optimal solution). On the other hand, \(T_{\text{IP}}\) and \(T_{\text{LP}}\) are the average elapsed time of the integer programming model and its linear programming relaxation, respectively. Table 1 summarizes the computational results for low-density instances. The EE formulation found the optimal upper bound for 43 out of 120 low-density instances. Of the remaining 77 instances for which the EE formulation could not find the optimal solution, the upper bounds of 36 instances were improved by our RLT model. Subsequently, the average value of the GAP was improved by our RLT formulation. On the other hand, the improvement in the GAP obtained by the RLT formulation tended to be smaller as \(k\) grew. Figure 5 presents box plots of the GAPs (%) produced by each formulation from problem instances for each combination of \((n,k)\). From the figure, we can observe that our RLT formulation yielded the lowest average GAPs, and that furthermore, the variability of the GAPs produced by our RLT formulation was also lower than that of the best-known compact formulations. Specifically, both the maximum and minimum GAPs, as well as the difference between the lower and upper quartiles, significantly dropped from the EA formulation to the EE formulation, and then further again to the RLT formulation. Moreover, such observations were consistent for every combination of \((n,k)\). The results imply that the EA formulation is highly dominated by the EE and RLT formulations, and moreover, that our proposed RLT formulation is more reliable than the EE formulation in terms of