# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 2 Reformulation-Linearization Technique
Therefore, the last set of inequalities produces_  
\[\{x\in R^{2}:\ x_{1}+x_{2}\leq 1,\ x_{1}\geq 0,\ x_{2}\geq 0\}\]  
_which is_ \(conv(X)\)_._  
**3. Two Representative Models for the KEP: EA and EE Formulations**  
In this section, we present two compact formulations, the EA and EE formulations, which were proposed by [PERSON] et al. [18] as reference models. In these formulations, the possible cycles in \(G\) and \(L\) are considered to be defined as a set composed of indices \(\{1,...,l_{u}\}\), where \(l_{u}\) indicates the upper bound on the possible number of cycles in \(G\). The additional parameters and decision variables used in the formulation are given as follows:  
**Parameters**  
\(w_{ij}\): Weight of edge \((i,j)\in A\), representing the level of compatibility between donor \(i\) and recipient \(j\). \(k\): Maximum cycle length. **Decision Variables**  
\(x_{ij}\): 1 if a kidney is transplanted from donor \(i\) to patient \(j\), and 0 otherwise. \(y_{i}^{l}\): 1 if node \(i\) is included in cycle \(l\), and 0 otherwise. Then, the EA formulation is given as follows:  
\[\text{EA}:\ \text{Maximize}\ \sum_{(i_{i},\ j)\in A}w_{ij}x_{ij} \tag{1a}\] \[\text{subject to}\ \sum_{j:\ (j_{i},\ i)\in A}x_{ji}=\sum_{j:\ (i_{i},\ j)\in A }x_{ij},\qquad\forall i\in V\] (1b) \[\sum_{j:\ (i_{i},\ j)\in A}x_{ij}\leq 1,\qquad\forall i\in V\] (1c) \[\sum_{i\in V}y_{i}^{l}\leq k,\qquad\forall l\in L\] (1d) \[\sum_{l\in L}y_{i}^{l}=\sum_{j:\ (i_{i},\ j)\in A}x_{ij},\qquad \forall i\in V\] (1e) \[y_{i}^{l}+x_{ij}\leq 1+y_{j}^{l},\qquad\forall(i,\ j)\in A,\ \forall l\in L\] (1f) \[x_{ij}\in\{0,\ 1\},\qquad\forall(i,\ j)\in A\] (1g) \[y_{i}^{l}\in\{0,\ 1\},\qquad\forall i\in V,\ l\in L \tag{1h}\]  
The objective function of Equation (1a) is to maximize the sum of weights of the transplantations. Because the weight of each edge indicates the appropriateness of the corresponding transplantation, the KEP maximizing the total appropriateness of all transplantations is planned. We note that setting \(w_{ij}\) to the same value for all \((i,j)\in A\) allows the maximum number of possible kidney exchanges in a given pool of candidates to be obtained. Constraint (1b) indicates that if a donor in pair \(i\) donets his or her kidney to a patient in another pair, then the patient in pair \(i\) must receive a kidney. This constraint further implies that if a donor does not participate in transplantation, the paired patient would not receive a kidney. Constraint (1c) implies that a donor cannot donate more than one kidney. Constraint (1d) ensures that the length of each cycle cannot be greater than \(k\). Constraint (1e) assigns a pair to a cycle if it takes part in kidney exchanges. We note that because \(\sum_{j:(i_{j})\in A}x_{ij}\leq 1\), a pair has to be assigned to one of the cycles. Constraint (1f) implies that if a donor in pair \(i\) gives his or her kidney to a patient in pair \(j\) and if the pair \(i\) is assigned to a cycle \(l\), then pair \(j\) also has to be included in cycle \(l\). Constraints (1g) and (1h) indicate that all the decision variables in the model are binary variables. We now present the EE formulation. We suppose that there are copies of graph \(G\) and we let the index of each copy be \(l\in L\), where \(L\) is a set of the copies of \(G\). Then, the EE formulation requires the additional decision variables \(x_{ij}^{l}\), as follows:  
**Decision Variable**  
\(x_{ij}^{l}\): 1 if a kidney is transplanted from donor \(i\) to patient \(j\) in copy \(l\), and 0 otherwise.