# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 4 RLT Applications
### Derivation of the EE Formulation from the EA Formulation  
We now apply a specialized version of the RLT to the EA formulation by following the discussion by [PERSON] and [PERSON] [24; 26]. To contain the size of the resulting relaxation, we apply only a partial first-level version of this approach. Our approach is to first reformulate the EA formulation by generating the additional (nonlinear) implied constraints. By applying a linearization, which substitutes variables in place of each distinct nonlinear term, we can expose the useful relationships between the new and original variables that intend to enforce the nonlinear relationships. Specifically, we perform the following operations:  
* **Reformulation Phase. ** Construct additional sets of constraints via (R1)-(R5) stated below. (R1) Similarly to Constraint (1f), construct the following valid inequalities: \[y_{j}^{l}+x_{ij}\leq 1+y_{i}^{l},\qquad\forall(i,\,j)\in A,\,\,\forall l\in L\] (4) Using Constraints (1f) and (4), construct the valid inequalities \[x_{ij}(y_{i}^{l}+x_{ij}-1-y_{j}^{l})\leq 0\quad\text{for}\quad(i,\,j)\in A,\,l\in L\] and \[x_{ij}(y_{j}^{l}+x_{ij}-1-y_{i}^{l})\leq 0\quad\text{for}\quad(i,\,j)\in A,\,l \in L.\]
* For each \(i\in V\), multiply the equation \(\sum_{j:\,(j,\,i)\in A}x_{ji}=\sum_{j:\,(i,\,j)\in A}x_{ij}\) of Constraint (1b) by \(y_{i}^{l}\geq 0\) for each \(i\in V\), \(l\in L\). (R3) 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\). (R4) From Constraints (1c) and (1e), we can derive \(\sum_{l\in L}y_{i}^{l}\leq 1\) for \(i\in V\). For each \(i\in V\), multiply \(\sum_{l\in L}y_{i}^{l}\leq 1\) and \(\sum_{l\in L}y_{i}^{l}=\sum_{j:\,(i,\,j)\in A}x_{ij}\) by \(y_{i}^{l}\) for each \(i\in V\), \(l^{\prime}\in L\). * For each \(i\in V\), multiply the inequality \(\sum_{j:\ (i,\ j)\in A}x_{ij}\leq 1\) of Constraint (1c) by \(x_{ij^{\prime}}\) for each \((i,\ j^{\prime})\in A\), and for each \(i\in V\), multiply the equation \(\sum_{l\in L}y_{i}^{l}=\sum_{j:\ (i,\ j)\in A}x_{ij}\) by \(x_{ij^{\prime}}\) for each \((i,\ j^{\prime})\in A\). * **Linearization Phase. ** Linearize the new classes of constraints generated by (R1)-(R5) above by using the substitutions \[u_{ij}^{l}=y_{i}^{l}x_{ij}\qquad\text{and}\qquad v_{ij}^{l}=y_{j}^{l}x_{ij} \qquad\forall(i,\ j)\in A,\ \forall l\in L.\] Reformulation step (R1) produces \(u_{ij}^{l}\leq v_{ij}^{l}\) for \((i,\ j)\in A\), \(l\in L\) and \(v_{ij}^{l}\leq u_{ij}^{l}\) for \((i,\ j)\in A\), \(l\in L\). Therefore, we have \(u_{ij}^{l}=v_{ij}^{l}\) for \((i,\ j)\in A\), \(l\in L\) and we only use \(u\) variables for the linearization. Step (R2) produces \(\sum_{j:\ (i,\ j)\in A}u_{ji}^{l}=\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\) for \(i\in V\), \(l\in L\). Step (R3) gives \(\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\leq y_{i}^{l}\) for \(i\in V\), \(l\in L\), and surrogates them for each \(l\in L\), which results in \(\sum_{l\in L}\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\leq\sum_{l\in L}y_{i}^{l}\) for \(i\in V\). By Constraints (1c) and (1e), we have \(\sum_{l\in L}\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\leq 1\) for \(i\in V\). Reformulation step (R4) generates \(y_{i}^{l^{\prime}}+\sum_{(i\
eq l^{\prime})\in L}y_{i}^{l}y_{i}^{l^{\prime}} \leq y_{i}^{l^{\prime}}\) for \(i\in V\), which leads to \(\sum_{l(\
eq l^{\prime})\in L}y_{i}^{l}y_{i}^{l^{\prime}}=0\). Therefore, \(\sum_{l\in L}y_{i}^{l}=\sum_{j:\ (i,\ j)\in A}x_{ij}\) multiplied by \(y_{i}^{l^{\prime}}\) for each \(i\in V\), \(l^{\prime}\in L\) yields \(y_{i}^{l}=\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\) for \(i\in V\), \(l\in L\) (\(l^{\prime}\) is substituted by \(l\) for convenience). Next, surrogating \(y_{i}^{l}=\sum_{j:\ (i,\ j)\in A}u_{ij}^{l}\) for each \(i\in V\) gives \(\sum_{i\in V}y_{i}^{l}=\sum_{(i,\ j)\in A}u_{ij}^{l}\) for \(l\in L\). Hence, by Constraint (1d), we have \(\sum_{(i,\ j)\in A}u_{ij}^{l}\leq k\) for \(l\in L\).