1
$\begingroup$

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

cost = np.loadtxt('matrix_time-independent_2017to2019_delete.txt')

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:
        mdl.add_indicator(x[(i,j)],d[i]+1==d[j], 
                          name='order_(%d,_%d)'%(i, j))
        
# sequential formulation (Miller, Tucker, Zemlin)
for (i, j) in arcs:
    if i != j:

???

print(mdl.export_to_string())

# possible to add constraint

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()

```
$\endgroup$
2
  • 2
    $\begingroup$ As a starting point you may use the OPL model : github.com/AlexFleischerParis/howtowithopl/blob/master/… since translating OPL to docplex python is easy $\endgroup$ – Alex Fleischer May 28 at 8:13
  • 1
    $\begingroup$ 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? $\endgroup$ – EhsanK Jun 17 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.