4 minimize the travel cost for visiting n customers exactly once 6 - start with assignment model 7 - add cuts until there are no sub-cycles 8 - two cutting plane possibilities (called inside "solve_tsp"): 9 - addcut: limit the number of edges in a connected component S to |S|-1 10 - addcut2: require the number of edges between two connected component to be >= 2 12 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 17 from pyscipopt
import Model, quicksum
20 """solve_tsp -- solve the traveling salesman problem 21 - start with assignment model 22 - add cuts until there are no sub-cycles 24 - V: set/list of nodes in the graph 25 - c[i,j]: cost for traversing edge (i,j) 26 Returns the optimum objective value and the list of edges used. 29 def addcut(cut_edges):
31 G.add_edges_from(cut_edges)
32 Components = list(networkx.connected_components(G))
33 if len(Components) == 1:
37 model.addCons(quicksum(x[i,j]
for i
in S
for j
in S
if j>i) <= len(S)-1)
38 print(
"cut: len(%s) <= %s" % (S,len(S)-1))
42 def addcut2(cut_edges):
44 G.add_edges_from(cut_edges)
45 Components = list(networkx.connected_components(G))
47 if len(Components) == 1:
54 model.addCons(quicksum(x[i,j]
for i
in S
for j
in T
if j>i) +
55 quicksum(x[i,j]
for i
in T
for j
in S
if j>i) >= 2)
56 print(
"cut: %s >= 2" %
"+".join([(
"x[%s,%s]" % (i,j))
for i
in S
for j
in T
if j>i]))
67 x[i,j] = model.addVar(ub=1, name=
"x(%s,%s)"%(i,j))
70 model.addCons(quicksum(x[j,i]
for j
in V
if j < i) + \
71 quicksum(x[i,j]
for j
in V
if j > i) == 2,
"Degree(%s)"%i)
73 model.setObjective(quicksum(c[i,j]*x[i,j]
for i
in V
for j
in V
if j > i),
"minimize")
81 if model.getVal(x[i,j]) > EPS:
84 if addcut(edges) ==
False:
89 model.chgVarType(x[i,j],
"B")
92 return model.getObjVal(),edges
95 def distance(x1,y1,x2,y2):
96 """distance: euclidean distance between (x1,y1) and (x2,y2)""" 97 return math.sqrt((x2-x1)**2 + (y2-y1)**2)
100 """make_data: compute matrix distance based on euclidean distance""" 102 x = dict([(i,random.random())
for i
in V])
103 y = dict([(i,random.random())
for i
in V])
108 c[i,j] = distance(x[i],y[i],x[j],y[j])
112 if __name__ ==
"__main__":
116 if len(sys.argv) < 2:
117 print(
"Usage: %s instance" % sys.argv[0])
118 print(
"Using randomized example instead")
124 from read_tsplib
import read_tsplib
128 print(
"Cannot read TSPLIB file",sys.argv[1])
131 obj,edges = solve_tsp(V,c)
133 print(
"\nOptimal tour:",edges)
134 print(
"Optimal cost:",obj)