(Solved): 3. A set of subtour elimination constraints, called the Miller-Tucker-Zemlin (MTZ) constraints, is ...

3. A set of subtour elimination constraints, called the Miller-Tucker-Zemlin (MTZ) constraints, is given by $u_i?u_j+n{x}_{ij}?n?1\text{ for }i=2,\dots ,n,j=2,\dots ,n$ where $u_2,\dots ,u_n$ are real numbers. Taha deals with these constraints in Section 11.3 .2 on page 444 and calls the result 'the cutting-plane algorithm'. (i) Write an AMPL TSP model that incudes the MTZ constraints (6). You could use your model without subtour elimination from above, and supplement it with the MTZ constraints. (ii) Run this model for all the given problems $(6,8,15$ and 20 cities). Use GUROBI. (iii) Interpret your results. Are your solutions tours? What are the values of the $u$ variables and what are they indicating? (iv) How do the MTZ constraints (6) work to prevent subtours? Illustrate with a simple example, say the given 6 city example. Note that if a solution does describe subtours, then one of these subtours does not include node 1 , and that is critical.