Loading...
Searching...
No Matches
Tsp.java
1package com.gams.examples.tsp;
2
3import java.io.File;
4import java.util.ArrayList;
5import java.util.Collection;
6import java.util.HashMap;
7import java.util.List;
8import java.util.Map;
9
10import com.gams.api.GAMSCheckpoint;
11import com.gams.api.GAMSDatabase;
12import com.gams.api.GAMSGlobals;
13import com.gams.api.GAMSJob;
14import com.gams.api.GAMSModelInstance;
15import com.gams.api.GAMSModifier;
16import com.gams.api.GAMSOptions;
17import com.gams.api.GAMSParameter;
18import com.gams.api.GAMSSet;
19import com.gams.api.GAMSSetRecord;
20import com.gams.api.GAMSWorkspace;
21import com.gams.api.GAMSWorkspaceInfo;
22
32public class Tsp {
33
34 public static void main(String[] args) {
35
36 GAMSWorkspaceInfo wsInfo = new GAMSWorkspaceInfo();
37 // check if system directory has been passed as an argument
38 if (args.length > 0)
39 wsInfo.setSystemDirectory(args[0]);
40
41 // create a directory
42 File workingDirectory = new File(System.getProperty("user.dir"), "Tsp");
43 workingDirectory.mkdir();
44
45 wsInfo.setWorkingDirectory(workingDirectory.getAbsolutePath());
46
47 // create a workspace
48 GAMSWorkspace ws = new GAMSWorkspace(wsInfo);
49
50 // number of cuts that can be added to a model instance
51 int cutsPerRound = 10;
52 // current cut
53 int curCut = 0;
54 // cut limit for current model instance (cmax = curCut + cutsPerRound)
55 int cMax = 0;
56
57 // database used to collect all generated cuts
58 GAMSDatabase cutData = ws.addDatabase();
59 GAMSSet cc = cutData.addSet("cc", 1, "");
60 GAMSParameter acut = cutData.addParameter("acut", 3, "");
61 GAMSParameter rhscut = cutData.addParameter("rhscut", 1, "");
62
63 // list of cities (i1, i2, i3, ...)
64 List<String> n = new ArrayList<String>();
65
66 GAMSCheckpoint cp = null;
67 GAMSModelInstance mi = null;
68 GAMSParameter miAcut = null;
69 GAMSParameter miRhscut = null;
70 List<String> subTour = null;
71
72
73 do {
74 // create a new model instance when the cut limit is reached
75 if (curCut >= cMax) {
76 System.out.print(",");
77 cMax = curCut + cutsPerRound;
78 cutData.export();
79
80 // create the checkpoint
81 GAMSJob tspJob = ws.addJobFromString(model);
82 cp = ws.addCheckpoint();
83 GAMSOptions opt = ws.addOptions();
84 opt.defines("nrcities", "20");
85 opt.defines("cmax", Integer.toString(cMax - 1));
86 opt.defines("cutdata", cutData.getName());
87
88
89 // read input data from "tsp.gdx"
90 String gamsdir = ws.systemDirectory();
91 if (!gamsdir.endsWith(GAMSGlobals.FILE_SEPARATOR))
92 gamsdir += GAMSGlobals.FILE_SEPARATOR;
93 File datafile = new File(gamsdir + "apifiles" + GAMSGlobals.FILE_SEPARATOR
94 + "Data" + GAMSGlobals.FILE_SEPARATOR
95 + "tsp.gdx");
96 opt.defines("tspdata", "\"" + datafile.getAbsolutePath() + "\"");
97 tspJob.run(opt, cp);
98
99 // fill the n list only once
100 if (n.size() == 0)
101 for(GAMSSetRecord i : tspJob.OutDB().getSet("i"))
102 n.add(i.getKey(0));
103
104 // instantiate the model instance with modifiers miAcut and miRhscut
105 mi = cp.addModelInstance();
106 miAcut = mi.SyncDB().addParameter("acut", 3, "");
107 miRhscut = mi.SyncDB().addParameter("rhscut", 1, "");
108 GAMSModifier[] modifiers = { new GAMSModifier(miAcut), new GAMSModifier(miRhscut) };
109 mi.instantiate("assign use mip min z", modifiers);
110 }
111 else {
112 System.out.print(".");
113 }
114 // solve model instance using update type accumulate and clear acut and rhscut afterwards
115 mi.solve(GAMSModelInstance.SymbolUpdateType.ACCUMULATE);
116 mi.SyncDB().getParameter("acut").clear();
117 mi.SyncDB().getParameter("rhscut").clear();
118
119 // collect graph information from the solution
120 Map<String, String> graph = new HashMap<String, String>();
121
122 List <String> notVisited = new ArrayList<String>(n);
123 for(String i : n) {
124 for(String j : n) {
125 String[] keys = { i, j };
126 if (mi.SyncDB().getVariable("x").findRecord( keys ).getLevel() > 0.5)
127 graph.put(i, j);
128 }
129 }
130
131
132 // find all subtours and add the required cuts by modifying acut and rhscut
133 while (notVisited.size() != 0) {
134 String ii = notVisited.get(0);
135 subTour = new ArrayList<String>();
136 subTour.add(ii);
137 while (graph.get(ii) != notVisited.get(0))
138 {
139 ii = graph.get(ii);
140 subTour.add(ii);
141 }
142
143 final List<String> source = subTour;
144 IPredicate<String> doesNotContain = new IPredicate<String>() {
145 public boolean apply(String element) {
146 return !source.contains(element);
147 }
148 };
149 notVisited = (List<String>) filter(subTour, doesNotContain);
150
151 // add the cuts to both databases (cutData, mi.SyncDB)
152 for(String i : subTour) {
153 for(String j : subTour) {
154 String[] keys = { "c"+curCut, i, j };
155 acut.addRecord(keys).setValue( 1 );
156 miAcut.addRecord( keys ).setValue( 1 );
157 }
158 }
159
160 String key = "c"+curCut;
161 rhscut.addRecord( key ).setValue( subTour.size()-0.5 );
162 miRhscut.addRecord( key ).setValue( subTour.size()-0.5 );
163 cc.addRecord( key );
164 curCut += 1;
165 }
166
167 }
168 while(subTour.size() < n.size());
169
170 System.out.println();
171 System.out.println("z=" + mi.SyncDB().getVariable("z").getFirstRecord().getLevel());
172 System.out.println("sub_tour: ");
173 for(String i : subTour)
174 System.out.print(i + " -> ");
175 System.out.println( subTour.get(0) );
176
177 }
178
179 interface IPredicate<T> { boolean apply(T type); }
180 static <T> Collection<T> filter(Collection<T> target, IPredicate<T> predicate) {
181 Collection<T> result = new ArrayList<T>();
182 for (T element : target) {
183 if (predicate.apply(element)) {
184 result.add(element);
185 }
186 }
187 return result;
188 }
189
190 static String model =
191 "$Title Traveling Salesman Problem \n" +
192 "$Ontext \n" +
193 " \n" +
194 "The sub_tour elimination constraints are generated by a Python \n" +
195 "script. The MIP is solved over and over, but GAMS have to \n" +
196 "generate the model only after n cuts have been added. \n" +
197 " \n" +
198 "$Offtext \n" +
199 " \n" +
200 "$if not set tspdata $abort 'tspdata not set' \n" +
201 " \n" +
202 "set ii cities \n" +
203 " i(ii) subset of cities \n" +
204 "alias (ii,jj),(i,j,k); \n" +
205 " \n" +
206 "parameter c(ii,jj) distance matrix; \n" +
207 " \n" +
208 "$gdxin %tspdata% \n" +
209 "$load ii c \n" +
210 " \n" +
211 "$if not set nrCities $set nrCities 20 \n" +
212 "i(ii)$(ord(ii) < %nrCities%) = yes; \n" +
213 " \n" +
214 "variables x(ii,jj) decision variables - leg of trip \n" +
215 " z objective variable; \n" +
216 "binary variable x; x.fx(ii,ii) = 0; \n" +
217 " \n" +
218 "equations objective total cost \n" +
219 " rowsum(ii) leave each city only once \n" +
220 " colsum(jj) arrive at each city only once; \n" +
221 " \n" +
222 "* the assignment problem is a relaxation of the TSP \n" +
223 "objective.. z =e= sum((i,j), c(i,j)*x(i,j)); \n" +
224 "rowsum(i).. sum(j, x(i,j)) =e= 1; \n" +
225 "colsum(j).. sum(i, x(i,j)) =e= 1; \n" +
226 " \n" +
227 "$if not set cmax $set cmax 2 \n" +
228 "set cut /c0*c%cmax%/; \n" +
229 "parameter \n" +
230 " acut(cut,ii,jj) cut constraint matrix \n" +
231 " rhscut(cut) cut constraint rhs; \n" +
232 " \n" +
233 "equation sscut(cut) sub_tour elimination cut; \n" +
234 "sscut(cut).. sum((i,j), Acut(cut,i,j)*x(i,j)) =l= RHScut(cut); \n" +
235 " \n" +
236 "set cc(cut) previous cuts; cc(cut) = no; \n" +
237 "$if set cutdata execute_load '%cutdata%', cc, Acut, RHScut; \n" +
238 " \n" +
239 "Acut(cut,i,j)$(not cc(cut)) = eps; \n" +
240 "RHScut(cut)$(not cc(cut)) = card(ii); \n" +
241 " \n" +
242 "model assign /all/; \n" +
243 " \n" +
244 "option optcr=0; \n";
245
246}
com::gams::api::GAMSCheckpoint::addModelInstance
GAMSModelInstance addModelInstance()
com::gams::api::GAMSDatabase::getParameter
GAMSParameter getParameter(String identifier)
com::gams::api::GAMSDatabase::addSet
GAMSSet addSet(String identifier, int dimension)
com::gams::api::GAMSDatabase::addParameter
GAMSParameter addParameter(String identifier, int dimension)
com::gams::api::GAMSDatabase::getVariable
GAMSVariable getVariable(String identifier)
com::gams::api::GAMSDatabase::getSet
GAMSSet getSet(String identifier)
com::gams::api::GAMSGlobals::FILE_SEPARATOR
static final String FILE_SEPARATOR
com::gams::api::GAMSJob::OutDB
GAMSDatabase OutDB()
com::gams::api::GAMSModelInstance::instantiate
void instantiate(String modelDefinition, GAMSModifier ... modifiers)
com::gams::api::GAMSOptions::defines
void defines(String defStr, String asStr)
com::gams::api::GAMSSymbol::findRecord
T findRecord(String ... keys)
com::gams::api::GAMSSymbol::addRecord
T addRecord(Vector< String > keys)
com::gams::api::GAMSWorkspaceInfo::setSystemDirectory
void setSystemDirectory(String directory)
com::gams::api::GAMSWorkspaceInfo::setWorkingDirectory
void setWorkingDirectory(String directory)
com::gams::api::GAMSWorkspace::addJobFromString
GAMSJob addJobFromString(String source)
com::gams::api::GAMSWorkspace::addCheckpoint
GAMSCheckpoint addCheckpoint()
com::gams.examples.tsp.Tsp
This example demonstrates how to use a GAMSModelInstance to implement the subtour elimination algorit...
Definition: Tsp.java:32
com::gams
Provides package namespace for Java interface and examples to General Algebraic Model System (GAMS).
com
&#160;