# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 4 RLT Applications
### Extended Formulation Derived from the EE Formulation  
In this subsection, we further strengthen the EE formulation by applying the RLT while maintaining the \(y\) variables. The specific RLT procedure we perform is explained in detail below.  
* **Reformulation Phase.** Construct the additional set of constraints via (R6)-(R9) stated below. 1. For each \(i\in V\), multiply the inequality \(\sum_{j:\ (i,\ j)\in A}x_{ij}\leq 1\) of Constraint (1c) by \(y_{i}^{l}\geq 0\) for each \(i\in V\), \(l\in L\). 2. For each \((i,\ j)\in A\) and \(l\in L\), multiply the inequality \(y_{i}^{l}+x_{ij}\leq 1+y_{j}^{l}\) of Constraint (1f) by \(y_{i}^{l}\geq 0\) and \(y_{j}^{l}\). Similarly, for each \((i,\ j)\in A\) and \(l\in L\), multiply the inequality \(y_{j}^{l}+x_{ij}\leq 1+y_{i}^{l}\) by \(y_{i}^{l}\geq 0\). 3. For each \(l\in L\), multiply the inequality \(\sum_{i\in V}y_{i}^{l}\leq k\) of Constraint (1d) by \(y_{j}^{l}\geq 0\) for each \(j\in V\). 4. For each \(i\in V\), \(l\in L\), \(i>l\), multiply the inequality \(y_{i}^{l}\leq y_{i}^{l}\) of the symmetry elimination constraints (3) by \(y_{i}^{l}\geq 0\), \(y_{i}^{l}\geq 0\), and \(y_{j}^{l}\geq 0\) for each \(j\in V\).
* **Linearization Phase.** Linearize the new classes of constraints generated by (R6)-(R9) above by using the substitutions \[x_{ij}^{l}=y_{i}^{l}x_{ij}=y_{j}^{l}x_{ij}\qquad\forall(i,\ j)\in A,\ \forall l\in L \qquad\text{and}\qquad z_{(ij)}^{l}=y_{i}^{l}y_{j}^{l}\qquad\forall i,\ j\in V,\ \forall l\in L.\] Reformulation step (R6) produces \(\sum_{j:\ (i,\ j)\in A}x_{ij}^{l}\leq y_{i}^{l}\) for \(i\in V\), \(l\in L\). Step (R7) gives three classes of valid inequalities \(x_{ij}^{l}\leq z_{(ij)}^{l}\), \(z_{(ij)}^{l}+x_{ij}^{l}\leq 2y_{i}^{l}\), and \(z_{(ij)}^{l}+x_{ij}^{l}\leq 2y_{i}^{l}\) for \((i,\ j)\in A\), \(l\in L\). Step (R8)generates \(\sum_{j(\
eq i)\in V}z_{(ij)}^{l}\leq(k-1)y_{i}^{l}\) for \(i\in V\), \(l\in L\). The last step (R9) produces \(y_{i}^{l}\leq z_{il}^{l}\leq y_{i}^{l}\) for \(i\in V\), \(l\in L\), and \(z_{(ij)}^{l}\leq z_{jl}^{l}\) for \(i,\ j\in V\), \(l\in L\).  
We summarize the overall RLT process above to derive a new compact formulation from the EE formulation in Figure 4. By augmenting the valid inequalities generated above to some set of constraints from the EE and EA formulations, we derive a new integer programming model for the KEP, which is more compact and tighter than the EE formulation, as follows:  
\[\text{RLT}:\;\text{Maximize}\;\sum_{l\in L}\sum_{(i,j)\in A}w_{ij}x_{ij}^{l} \tag{5a}\] \[\text{Subject to Constraints (\ref{eq:E}), (\ref{eq:E}), (\ref{eq:E}), (\ref{eq:E}), (\ref{eq:E}), (\ref{eq:E})}\] \[\sum_{j:\ (i,j)\in A}x_{ij}^{l}\leq y_{i}^{l},\qquad\forall i\in V,\,l\in L\] (5b) \[x_{ij}^{l}\leq z_{(ij)}^{l},\qquad\forall(i,\,j)\in A,\,l\in L\] (5c) \[z_{(ij)}^{l}+x_{ij}^{l}\leq 2y_{j}^{l},\qquad\forall(i,\,j)\in A,\,l\in L\] (5d) \[z_{(ij)}^{l}+x_{ij}^{l}\leq 2y_{i}^{l},\qquad\forall(i,\,j)\in A,\,l\in L\] (5e) \[\sum_{j(\
eq i)\in V}z_{(ij)}^{l}\leq(k-1)y_{i}^{l},\qquad\forall i \in V,\,l\in L\] (5f) \[y_{i}^{l}\leq z_{il}^{l}\leq y_{i}^{l},\qquad\forall i\in V,\,l \in L\] (5g) \[z_{(ij)}^{l}\leq z_{jl}^{l},\qquad\forall i,\,j\in V,\,l\in L\] (5h) \[z_{(ij)}^{l}\in\{0,\,1\},\qquad\forall i,\,j\in V,\,l\in L. \tag{5i}\]