enter image description hereI 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.


1 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$.)

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – TheSimpliFire
    Jan 16, 2021 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.