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
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])
133 print(
"\nOptimal tour:",edges)
134 print(
"Optimal cost:",obj)