Loading...
Searching...
No Matches
Tsp.cs
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using GAMS;
6using System.IO;
7using System.Reflection;
8
9namespace Tsp
10{
21 class Tsp
22 {
23 static void Main(string[] args)
24 {
25 GAMSWorkspace ws;
26 if (Environment.GetCommandLineArgs().Length > 1)
27 ws = new GAMSWorkspace(systemDirectory: Environment.GetCommandLineArgs()[1]);
28 else
29 ws = new GAMSWorkspace(".");
30 // number of cuts that can be added to a model instance
31 int cutsPerRound = 10;
32 // current cut
33 int curCut = 0;
34 // cut limit for current model instance (cmax = curCut + cutsPerRound)
35 int cMax = 0;
36
37 // database used to collect all generated cuts
38 GAMSDatabase cutData = ws.AddDatabase();
39 GAMSSet cc = cutData.AddSet("cc", 1, "");
40 GAMSParameter acut = cutData.AddParameter("acut", 3, "");
41 GAMSParameter rhscut = cutData.AddParameter("rhscut", 1, "");
42 // list of cities (i1, i2, i3, ...)
43 List<string> n = new List<String>();
44
45 GAMSCheckpoint cp = null;
46 GAMSModelInstance mi = null;
47 GAMSParameter miAcut = null;
48 GAMSParameter miRhscut = null;
49 List<string> subTour = null;
50
51 do
52 {
53 // create a new model instance when the cut limit is reached
54 if (curCut >= cMax)
55 {
56 cMax = curCut + cutsPerRound;
57 cutData.Export();
58
59 // create the checkpoint
60 GAMSJob tspJob = ws.AddJobFromString(GetModelText());
61 cp = ws.AddCheckpoint();
62 GAMSOptions opt = ws.AddOptions();
63 opt.Defines.Add("nrcities", "20");
64 opt.Defines.Add("cmax", (cMax - 1).ToString());
65 opt.Defines.Add("cutdata", cutData.Name);
66 opt.Defines.Add("tspdata", "\"" + Path.Combine(ws.SystemDirectory, @"apifiles/Data/tsp.gdx") + "\"");
67 tspJob.Run(opt, cp);
68
69 // fill the n list only once
70 if (n.Count == 0)
71 foreach(GAMSSetRecord i in tspJob.OutDB.GetSet("i"))
72 n.Add(i.Key(0));
73
74 // instantiate the model instance with modifiers miAcut and miRhscut
75 mi = cp.AddModelInstance();
76 miAcut = mi.SyncDB.AddParameter("acut", 3, "");
77 miRhscut = mi.SyncDB.AddParameter("rhscut", 1, "");
78 mi.Instantiate("assign use mip min z", new GAMSModifier(miAcut), new GAMSModifier(miRhscut));
79 }
80
81 // solve model instance using update type accumulate and clear acut and rhscut afterwards
82 mi.Solve(GAMSModelInstance.SymbolUpdateType.Accumulate);
83 mi.SyncDB.GetParameter("acut").Clear();
84 mi.SyncDB.GetParameter("rhscut").Clear();
85
86 // collect graph information from the solution
87 Dictionary<string, string> graph = new Dictionary<string, string>();
88 List<string> notVisited = new List<string>(n);
89 foreach (string i in n)
90 foreach (string j in n)
91 if (mi.SyncDB.GetVariable("x").FindRecord(i, j).Level > 0.5)
92 graph[i] = j;
93
94 // find all subtours and add the required cuts by modifying acut and rhscut
95 while (notVisited.Count != 0)
96 {
97 string ii = notVisited[0];
98 subTour = new List<string>();
99 subTour.Add(ii);
100 while (graph[ii] != notVisited[0])
101 {
102 ii = graph[ii];
103 subTour.Add(ii);
104 }
105 notVisited = notVisited.Where(x => !subTour.Contains(x)).ToList<string>();
106
107 // add the cuts to both databases (cutData, mi.SyncDB)
108 foreach (string i in subTour)
109 foreach (string j in subTour)
110 {
111 acut.AddRecord("c" + curCut, i, j).Value = 1;
112 miAcut.AddRecord("c" + curCut, i, j).Value = 1;
113 }
114
115 rhscut.AddRecord("c" + curCut).Value = subTour.Count() - 0.5;
116 miRhscut.AddRecord("c" + curCut).Value = subTour.Count() - 0.5;
117 cc.AddRecord("c" + curCut);
118 curCut += 1;
119 }
120 }
121 while (subTour.Count < n.Count);
122
123 Console.WriteLine("z=" + mi.SyncDB.GetVariable("z").FirstRecord().Level);
124 Console.WriteLine("sub_tour: ");
125 foreach (string i in subTour)
126 Console.Write(i + " -> ");
127 Console.WriteLine(subTour[0]);
128
129 }
130
131 static String GetModelText()
132 {
133 String model = @"
134$Title Traveling Salesman Problem Instance with Python
135
136$Ontext
137
138The sub_tour elimination constraints are generated by a Python
139script. The MIP is solved over and over, but GAMS have to
140generate the model only after n cuts have been added.
141
142$Offtext
143
144$if not set tspdata $abort 'tspdata not set'
145
146set ii cities
147 i(ii) subset of cities
148alias (ii,jj),(i,j,k);
149
150parameter c(ii,jj) distance matrix;
151
152$gdxin %tspdata%
153$load ii c
154
155$if not set nrCities $set nrCities 20
156i(ii)$(ord(ii) < %nrCities%) = yes;
157
158variables x(ii,jj) decision variables - leg of trip
159 z objective variable;
160binary variable x; x.fx(ii,ii) = 0;
161
162equations objective total cost
163 rowsum(ii) leave each city only once
164 colsum(jj) arrive at each city only once;
165
166* the assignment problem is a relaxation of the TSP
167objective.. z =e= sum((i,j), c(i,j)*x(i,j));
168rowsum(i).. sum(j, x(i,j)) =e= 1;
169colsum(j).. sum(i, x(i,j)) =e= 1;
170
171$if not set cmax $set cmax 2
172set cut /c0*c%cmax%/;
173parameter
174 acut(cut,ii,jj) cut constraint matrix
175 rhscut(cut) cut constraint rhs;
176
177equation sscut(cut) sub_tour elimination cut;
178sscut(cut).. sum((i,j), Acut(cut,i,j)*x(i,j)) =l= RHScut(cut);
179
180set cc(cut) previous cuts; cc(cut) = no;
181$if set cutdata execute_load '%cutdata%', cc, Acut, RHScut;
182
183Acut(cut,i,j)$(not cc(cut)) = eps;
184RHScut(cut)$(not cc(cut)) = card(ii);
185
186model assign /all/;
187
188option optcr=0;
189";
190 return model;
191 }
192 }
193}
GAMS::GAMSCheckpoint::AddModelInstance
GAMSModelInstance AddModelInstance(string modelInstanceName=null)
GAMS::GAMSDatabase::GetVariable
GAMSVariable GetVariable(string variableIdentifier)
GAMS::GAMSDatabase::AddSet
GAMSSet AddSet(string identifier, int dimension, string explanatoryText="", SetType setType=SetType.multi)
GAMS::GAMSDatabase::GetParameter
GAMSParameter GetParameter(string parameterIdentifier)
GAMS::GAMSDatabase::AddParameter
GAMSParameter AddParameter(string identifier, int dimension, string explanatoryText="")
GAMS::GAMSDatabase::Export
void Export(string filePath=null)
GAMS::GAMSJob::Run
void Run(GAMSOptions gamsOptions=null, GAMSCheckpoint checkpoint=null, TextWriter output=null, Boolean createOutDB=true)
GAMS::GAMSModelInstance::Solve
void Solve(SymbolUpdateType updateType=SymbolUpdateType.BaseCase, TextWriter output=null, GAMSModelInstanceOpt miOpt=null)
GAMS::GAMSModelInstance::Instantiate
void Instantiate(string modelDefinition, params GAMSModifier[] modifiers)
GAMS::GAMSOptions::Defines
Dictionary< string, string > Defines
GAMS::GAMSParameter::AddRecord
new GAMSParameterRecord AddRecord(params string[] keys)
GAMS::GAMSSet::AddRecord
new GAMSSetRecord AddRecord(params string[] keys)
GAMS::GAMSSymbolRecord::Key
string Key(int index)
GAMS::GAMSVariable::FindRecord
new GAMSVariableRecord FindRecord(params string[] keys)
GAMS::GAMSVariable::FirstRecord
new GAMSVariableRecord FirstRecord()
GAMS::GAMSWorkspace::AddJobFromString
GAMSJob AddJobFromString(string gamsSource, GAMSCheckpoint checkpoint=null, string jobName=null)
GAMS::GAMSWorkspace::AddDatabase
GAMSDatabase AddDatabase(string databaseName=null, string inModelName=null)
GAMS::GAMSWorkspace::AddCheckpoint
GAMSCheckpoint AddCheckpoint(string checkpointName=null)
GAMS::GAMSWorkspace::AddOptions
GAMSOptions AddOptions(GAMSOptions optFrom=null)
Tsp
Definition: Tsp.cs:10