import sys import math from itertools import combinations from gurobipy import * import math import random #Create TSP instance if len(sys.argv) < 2: print('Usage: tsp.py npoints') exit(1) n = int(sys.argv[1]) D = [[0 for i in range(n)] for i in range(n)] #Create a distance matrix for i in range(n): for j in range(n): if (i==j): D[i][j] = 0 else: D[i][j] = random.randrange(1, 100, 1) # Read the input file # f = open(sys.argv[1]) # # D = [] # for line in f: # line = line.strip() # if len(line) > 0: # D.append(map(int, line.split(" "))) # # n = len(D[0]) print(D) m = Model('TSP') # Create an array of model variables vars = {} for i in range(n): for j in range(n): vars[i,j] = m.addVar(vtype=GRB.BINARY, name='x_'+ str(i)+'_'+str(j), obj=D[i][j]) m.update() # Model your constraints and objective here # Add degree-2 constraint, and forbid loops for i in range(n): m.addConstr(quicksum(vars[i,j] for j in range(n)) == 1) m.addConstr(quicksum(vars[j,i] for j in range(n)) == 1) vars[i,i].ub = 0 m.update() # Explicit sub-tour elimination constraints # Create a list of the cities l = range(n) for i in range(1, n-1): print(i) s = list(combinations(l, i+1)) print(s) for k in s: print(k) m.addConstr(quicksum(quicksum(vars[i,j] for j in k) for i in k) <= len(k)-1) m.update() # Solve the model and write out the solution m.optimize() for v in m.getVars(): print('%s %g' % (v.varName, v.x)) print('Obj: %g' % m.objVal)