Hello i want to propose you this proof that i did in order to prove the fact that when we have a MILP where the integer variables are restricted to 0 and 1 it is possible to write it as LP. Please let me know if something is wrong. Thanks
Consider a canonical MILP \begin{equation}\label{milp} \begin{aligned} & {\text{min}} & & [c_c^T\ c_d^T]^T[x_c\ x_d] \\ & \text{subject to} & & Ax \leq b \end{aligned} \end{equation} where $x_c \in \mathbb R^{n_c}$ is a vector representing the continous decision variables and $x_d \in \mathbb B^{n_p}$ represents the integer decision variables. By hypotesis $x_{d_i} \in \{0,1\}$ for any $i=1,...,n_p$. Let us replace each binary variable $x_{d_i} \in \{0,1\}$ with a continuous variable $\tilde x_{d_i} \in [0,1]$. It is clear that \begin{equation}\label{initeq} x_{d_i} \in \{0,1\} \iff \tilde x_{d_i}\tilde x_{d_i}-\tilde x_{d_i}=0\\ \end{equation} By defining $n_p$ slack decision variables, $\tilde x_{d_i}^e \doteq \tilde x_{d_i}\tilde x_{d_i}$,the problem above can be rewritten as \begin{equation}\label{milp2} \begin{aligned} & {\text{min}} & & [c_c^T\ c_d^T]^T[x_c\ \tilde x_d] \\ & \text{subject to} & & Ax \leq b\\ & & & \tilde x_{d_i}^e - \tilde x_{d_i}=0 \hspace{15pt} i=1,...,n_p\\ & & &\tilde x_{d_i}^e=\tilde x_{d_i}\tilde x_{d_i}\\ & & &\tilde x_{d_i} \in [0,1] \end{aligned} \end{equation} Which has nonlinear constraints. By applying what is written here http://www.leandro-coelho.com/linearization-product-variables/ (about the linearisation of a product of binary variables), we obtain: \begin{equation}\label{milptolp} \begin{aligned} & {\text{min}} & & [c_c^T\ c_d^T 0]^T[x_c\ \tilde x_d \ x_d^e] \\ & \text{subject to} & & A_ex_{ext} \leq b_e\\ & & & \tilde x_{d_i}^e - \tilde x_{d_i} \leq 0 \hspace{15pt} i=1,...n_p\\ & & & \tilde x_{d_i}^e - \tilde x_{d_i} \geq 0 \\ & & &\tilde x_{d_i}^e \geq 2\tilde x_{d_i}-1 \\ & & &\tilde x_{d_i} \leq 1\\ & & &\tilde x_{d_i} \geq 0 \end{aligned} \end{equation} which is a Linear Program in the new extended variables $x_{ext}=[x_c\ \tilde x_d \ x_d^e]$. Which is equivalent to the MILP but expressed as LP, so can be solved in polynomial time (even if the extended variables vector is bigger).