Miller-Tucker-Zemlin subtour elimination constraints to obtain a minimum spanning tree

Question

I need Miller-Tucker-Zemlin subtour elimination formulation for symmetric traveling salesman problem (STSP) to use to construct a minimum spanning tree. Ie, I need Miller-Tucker-Zemlin formulation for an undirected graph.

Answer 1

Replace each undirected edge $(i,j)\in E$ with two directed arcs $(i,j),(j,i)\in A$ with the same cost $c_{i,j} = c_{j,i}$. For each $(i,j)\in A$, let binary variable $x_{i,j}$ indicate whether that arc appears in the tree. Let node $1$ (arbitrarily) be the root, and omit all arcs into the root. For each node $i\in N$, let $u_i\in [0,n-1]$ be the MTZ variable. The problem is to minimize $$\sum_{(i,j) \in A} c_{i,j} x_{i,j}$$ subject to \begin{align} \sum_j x_{1,j} &\ge 1 \tag1\\ \sum_i x_{i,j} &= 1 &&\text{for $j\in N \setminus \{1\}$} \tag2\\ u_i + 1 - u_j &\le n(1-x_{i,j}) &&\text{for $(i,j)\in A$ with $j \not= 1$} \tag3 \end{align} Constraint $(1)$ forces at least one arc to leave the root node. Constraint $(2)$ forces exactly one arc to enter each non-root node. Constraint $(3)$ eliminates subtours by enforcing the logical implication $x_{i,j} = 1 \implies u_i + 1 \le u_j$.

For your sample data, an optimal solution is $$x_{1,6}=x_{3,2}=x_{5,3}=x_{5,4}=x_{6,5}=x_{6,7}=x_{7,10}=x_{8,9}=x_{10,8}=1,$$ $$u_{1}=0, u_{2}=9, u_{3}=8, u_{4}=9, u_{5}=7, u_{6}=1, u_{7}=6, u_{8}=8, u_{9}=9, u_{10}=7,$$ with all other $x_{i,j}=0$, yielding objective value $38$. (The optimal $x$ solution turns out to be unique, but there are multiple possibilities for optimal $u$.)