14 from itertools
import product
20 $Title Traveling Salesman Problem Instance with Python
24 The sub_tour elimination constraints are generated by a Python
25 script. The MIP is solved over and over, but GAMS have to
26 generate the model only after n cuts have been added.
30 $if not set tspdata $abort 'tspdata not set'
33 i(ii) subset of cities
34 alias (ii,jj),(i,j,k);
36 parameter c(ii,jj) distance matrix;
41 $if not set nrCities $set nrCities 20
42 i(ii)$(ord(ii) < %nrCities%) = yes;
44 variables x(ii,jj) decision variables - leg of trip
46 binary variable x; x.fx(ii,ii) = 0;
48 equations objective total cost
49 rowsum(ii) leave each city only once
50 colsum(jj) arrive at each city only once;
52 * the assignment problem is a relaxation of the TSP
53 objective.. z =e= sum((i,j), c(i,j)*x(i,j));
54 rowsum(i).. sum(j, x(i,j)) =e= 1;
55 colsum(j).. sum(i, x(i,j)) =e= 1;
57 $if not set cmax $set cmax 2
60 acut(cut,ii,jj) cut constraint matrix
61 rhscut(cut) cut constraint rhs;
63 equation sscut(cut) sub_tour elimination cut;
64 sscut(cut).. sum((i,j), Acut(cut,i,j)*x(i,j)) =l= RHScut(cut);
66 set cc(cut) previous cuts; cc(cut) = no;
67 $if set cutdata execute_load '%cutdata%', cc, Acut, RHScut;
69 Acut(cut,i,j)$(not cc(cut)) = eps;
70 RHScut(cut)$(not cc(cut)) = card(ii);
77 if __name__ ==
"__main__":
79 ws = GamsWorkspace(system_directory = sys.argv[1])
91 cut_data = ws.add_database()
92 cc = cut_data.add_set(
"cc", 1,
"")
93 acut = cut_data.add_parameter(
"acut", 3,
"")
94 rhscut = cut_data.add_parameter(
"rhscut", 1,
"")
102 cmax = curcut + cuts_per_round
107 cp = ws.add_checkpoint()
108 opt = ws.add_options()
109 opt.defines[
"nrcities"] =
"20"
110 opt.defines[
"cmax"] = str(cmax - 1)
111 opt.defines[
"cutdata"] = cut_data.name
112 opt.defines[
"tspdata"] =
'"' + os.path.join(os.path.dirname(os.path.realpath(__file__)),
"..",
"Data",
"tsp.gdx") +
'"'
113 tsp_job.run(gams_options=opt, checkpoint=cp)
117 for i
in tsp_job.out_db[
"i"]:
121 mi = cp.add_modelinstance()
122 mi_acut = mi.sync_db.add_parameter(
"acut", 3,
"")
123 mi_rhscut = mi.sync_db.add_parameter(
"rhscut", 1,
"")
124 mi.instantiate(
"assign use mip min z", [GamsModifier(mi_acut), GamsModifier(mi_rhscut)])
127 mi.solve(SymbolUpdateType.Accumulate)
128 mi.sync_db[
"acut"].clear()
129 mi.sync_db[
"rhscut"].clear()
133 not_visited = list(n)
134 for i,j
in product(n,n):
135 if mi.sync_db[
"x"].find_record([i, j]).level > 0.5:
142 while graph[i] != not_visited[0]:
145 not_visited = list(filter(
lambda x: x
not in sub_tour, not_visited))
148 for i,j
in product(sub_tour,sub_tour):
149 acut.add_record([
"c"+str(curcut), i, j]).value = 1
150 mi_acut.add_record([
"c"+str(curcut), i, j]).value = 1
151 rhscut.add_record(
"c"+str(curcut)).value = len(sub_tour)-0.5
152 mi_rhscut.add_record([
"c"+str(curcut)]).value = len(sub_tour)-0.5
153 cc.add_record(
"c"+str(curcut))
157 if len(sub_tour) == len(n):
158 print(
"z=" + str(mi.sync_db[
"z"].first_record().level))
161 print(i +
" -> ", end=
"")