# Implement sequential formulation in TSP (Miller, Tucker, Zemlin)

I'm trying to solve a TSP in different ways. I already did it with the formulation of Dantzig, Fulkerson and Johnson und now I want to do use the Miller, Tucker, Zemlin constraint. $$u_i-u_j+nx_{ij}\le n-1\quad\forall i,j\in N-\{1\},i\ne j$$

I'm a little bit stuck because I don't know how to implement it and I do not find anything useful on the internet. Does somebody know how to do it?

import numpy as np
import matplotlib.pyplot as plt
from docplex.mp.model import Model
import docplex.mp.solution as Solution

# for sequentiel solving

from itertools import product

cities=[i for i in range(len(cost))]
#print(cities)
arcs =[(i,j) for i in cities for j in cities if i!=j]

distance={(i, j): cost[i,j] for i,j in arcs}
#print(distance)

# CPLEX model
mdl=Model('TSP')

# decision variables

x=mdl.binary_var_dict(arcs,name='x')
d=mdl.continuous_var_dict(cities,name='d')

mdl.minimize(mdl.sum(distance[i]*x[i] for i in arcs))

# Constraints
for c in cities:
mdl.add_constraint(mdl.sum(x[(i,j)] for i,j in arcs if i==c)==1,
ctname='out_%d'%c)

for c in cities:
mdl.add_constraint(mdl.sum(x[(i,j)] for i,j in arcs if j==c)==1,
ctname='in_%d'%c)

# conventional way to eliminate subtours (Dantzig, Fulkerson and Johnson)
for i,j in arcs:
if j!=0:
name='order_(%d,_%d)'%(i, j))

# sequential formulation (Miller, Tucker, Zemlin)
for (i, j) in arcs:
if i != j:



???

print(mdl.export_to_string())

mdl.parameters.timelimit=120
mdl.parameters.mip.strategy.branch=1
mdl.parameters.mip.tolerances.mipgap=0.15

solution = mdl.solve(log_output=True)

mdl.get_solve_status()

solution.display()

$$$$

• As a starting point you may use the OPL model : github.com/AlexFleischerParis/howtowithopl/blob/master/… since translating OPL to docplex python is easy – Alex Fleischer May 28 at 8:13
• Maybe I'm missing something but what's wrong with adding mdl.add_constraint(d[i] + d[j]+n*x[i,j]<=n-1, ctname=f'mtz_{i}_{j}' where n = len(cities)` inside of your loop? – EhsanK Jun 17 at 2:18