# Reformulation-Linearization Technique Approach for Kidney Exchange Program IT Healthcare Platforms
## 2 Reformulation-Linearization Technique  
In this section, we briefly describe the concept of the RLT process in the context of zero-one integer problems. Let us define the feasible region of a zero-one integer problem as  
\[X=\{x:\mathbf{A}x\leq b,\ x\in\mathbb{B}^{r}\}\]  
where \(\mathbf{A}\) is a \(q\times r\) matrix, \(b\) is a \(q\) vector, and \(N=\{1,\ 2,\ \ldots,\ r\}\) is the index set of all variables. Without loss of generality, we assume that every component of \(\mathbf{A}\) and \(b\) is an integer. Additionally, the inequalities accommodate the upper bounds of \(x_{j}\leq 1\) for \(j\in N\). As usual, \(\mathbb{B}\) and \(\mathbb{R}\) denote the sets of binary and real numbers, respectively. The RLT process by [PERSON] and [PERSON] [24] to construct relaxation \(X_{d}\) at any level \(d\in\{1,\ \ldots,\ r\}\) in higher dimensional space consists of two steps, as follows:  
**Step 1. **: (Reformulation) Multiply each constraint defining the feasible region with every product factor of the form \(\prod_{i\in I_{1}}x_{i}\prod_{i\in I_{2}}(1-x_{i})\), where \(J_{1},\ J_{2}\subseteq N,\ J_{1}\cap J_{2}=\emptyset\), and \(|J_{1}\cup J_{2}|=d\), and then apply the identity \(x_{i}^{2}=x_{i}\) for all \(i\in N\). **Step 2. **: (Linearization) Linearize the resulting polynomial system by substituting a variable \(\lambda_{J}\) for every distinct product term \(\prod_{i\in J}x_{i}\), where \(J\subseteq N\). The results of [PERSON] and [PERSON] [24] show that, by denoting the projection of \(X_{d}\) onto the space of the original variables \(x\) by \(X_{P_{d}}=\{x:\ (x,\ \lambda)\in X_{d}\}\), we obtain the hierarchy of relaxations  
\[X_{P_{0}}\equiv X_{0}\supseteq X_{P_{1}}\supseteq X_{P_{2}}\supseteq\cdots \supseteq X_{P_{r}}\equiv conv(X)\]  
where \(X_{P_{0}}\equiv X_{0}\) denotes the linear programming relaxation of \(X\). The results above imply that we can theoretically obtain the convex hull of the feasible solution set \(X\) via the level \(r\) RLT and can hence obtain the optimal solution by solving the linear programming problem over \(X_{P_{r}}\). For a better understanding, we illustrate the RLT process through the following example [25]. **Example 1**: _Consider the following polytope:_  
\[X=\{x\in\mathbb{R}^{2}:\ 2x_{1}+3x_{2}\leq 4,\ x_{j}\in\{0,\ 1\},\ j=1,\ 2\}.\]  
_The linear programming of this polytope is given as \(X_{0}=\{x\in R^{2}:\ 2x_{1}+3x_{2}\leq 4,\ 0\leq x_{1}\leq 1,\ 0\leq x_{2}\leq 1\}\), and the convex hull of \(X\) is given as \(conv(X)=\{x\in R^{2}:\ x_{1}+x_{2}\leq 1,\ x_{1}\geq 0,\ x_{2}\geq 0\}\) (see Figure 3)._  
_Now, we apply the level 2 RLT to \(X_{0}\) to illustrate how \(conv(X)\) can be obtained by the RLT process._  
Figure 3: Illustration of polytope \(X_{0}\) (**left**) and its convex hull \(conv(X)\) (**right**). **Step 1**. : _(_(Reformulation) Multiply each constraint of_ \(X_{0}\) _by each of the factors_ \(x_{1}x_{2}\)_,_ \(x_{1}(1-x_{2})\)_,_ \((1-x_{1})x_{2}\)_, and_ \((1-x_{1})(1-x_{2})\)_. This process generates various duplicated or redundant inequalities; thus, we summarize the valid inequalities only, as follows:_  
\[ \begin{array}{ccc}(2x_{1}+3x_{2}\leq 4)\times x_{1}x_{2}&\to&2x_{1}x_{2}+3x_{1}x_{2} \leq 4x_{1}x_{2}\\ &\hookrightarrow&x_{1}x_{2}\leq 0\\ (2x_{1}+3x_{2}\leq 4)\times(1-x_{1})(1-x_{2})&\to&0\leq 4(1-x_{1})(1-x_{2})\\ &\hookrightarrow&x_{1}+x_{2}\leq 1+x_{1}x_{2}\\ (x_{1}\geq 0)\times x_{1}x_{2}&\to&x_{1}x_{2}\geq 0\\ (x_{1}\geq 0)\times x_{1}(1-x_{2})&\to&x_{1}-x_{1}x_{2}\geq 0\\ (x_{2}\geq 0)\times(1-x_{1})x_{2}&\to&x_{2}-x_{1}x_{2}\geq 0\end{array} \]
**Step 2**. : _(Linearization) After linearizing the resulting polynomial system by substituting a variable_ \(z_{12}\) _for the product term_ \(x_{1}x_{2}\)_, we have_  
\[ \begin{array}{l}z_{12}\leq 0\\ x_{1}+x_{2}\leq 1+z_{12}\\ z_{12}\geq 0\\ x_{1}-z_{12}\geq 0\\ x_{2}-z_{12}\geq 0\end{array} \]  
_By_ \(z_{12}\leq 0\) _and_ \(z_{12}\geq 0\)_, we have_ \(z_{12}=0\)_.