I am working on a specific vehicle routing problem, where I am using MTZ constraints for subtour elimination. I have been looking at the topic of lifting the MTZ constraints, as proposed by Desrochers and Laporte and later corrected in various papers.
I am having trouble finding information of a definition of what "lifting" actually means and how it helps strengthening the linear relaxation. Can someone explain in simple terms or maybe link to some literature?
A lifting of a constraint $\sum_j a_j x_j + \beta y \le b$, where $y \ge 0$, is a stronger valid inequality $\sum_j a_j x_j + \alpha y \le b$, where $\alpha \ge \beta$. To get the strongest such lifting, you want to find the largest value of $\alpha$ that yields a valid inequality. You can find a description in the context of lifted cover inequalities in Wolsey's Integer Programming.
For lifted MTZ constraints, assume that node $1$ is the depot and $0 \le u_i \le n-1$, where $n$ is the number of nodes. The basic MTZ constraint is $$u_i + 1 - u_j \le n(1-x_{ij}) \quad \text{for $(i,j)$ such that $j \not= 1$},$$ equivalently, $$u_i - u_j + n x_{ij} \le n - 1 \quad \text{for $(i,j)$ such that $j \not= 1$}. \tag1\label1$$ The lifted MTZ constraint is $$u_i - u_j + n x_{ij} + \alpha_{ji} x_{ji} \le n - 1 \quad \text{for $(i,j)$ such that $j \not= 1$}.$$ If $x_{ji}=0$, then any value of $\alpha_{ji}$ is valid in that case. If instead $x_{ji}=1$, then $x_{ij}=0$, and we want to find the largest value of $\alpha_{ji}$ such that $$u_i - u_j + \alpha_{ji} \le n - 1 \quad \text{for $(i,j)$ such that $j \not= 1$}. \tag2\label2$$ Reverse the roles of $i$ and $j$ in \eqref{1} and substitute $x_{ji}=1$, yielding $$u_j - u_i + n \le n - 1,$$ equivalently, $$u_j - u_i \le -1. \tag3\label3$$ Hence \eqref{2} and \eqref{3} imply that $$\alpha_{ji} \le n - 1 + u_j - u_i \le n - 2,$$ so take $\alpha_{ji} = n - 2$, yielding $$u_i - u_j + n x_{ij} + (n-2) x_{ji} \le n - 1 \quad \text{for $(i,j)$ such that $j \not= 1$}.$$