Tsp.java
1package com.gams.examples.tsp;
2 
3 import java.io.File;
4 import java.util.ArrayList;
5 import java.util.Collection;
6 import java.util.HashMap;
7 import java.util.List;
8 import java.util.Map;
9 
10 import com.gams.api.GAMSCheckpoint;
11 import com.gams.api.GAMSDatabase;
12 import com.gams.api.GAMSGlobals;
13 import com.gams.api.GAMSJob;
15 import com.gams.api.GAMSModifier;
16 import com.gams.api.GAMSOptions;
17 import com.gams.api.GAMSParameter;
18 import com.gams.api.GAMSSet;
19 import com.gams.api.GAMSSetRecord;
20 import com.gams.api.GAMSWorkspace;
22 
32 public 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
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 }
GAMSParameter getParameter(String identifier)
void defines(String defStr, String asStr)
void setSystemDirectory(String directory)
GAMSParameter addParameter(String identifier, int dimension)
GAMSSet addSet(String identifier, int dimension)
This example demonstrates how to use a GAMSModelInstance to implement the subtour elimination algorit...
Definition: Tsp.java:32
GAMSSet getSet(String identifier)
GAMSJob addJobFromString(String source)
void instantiate(String modelDefinition, GAMSModifier ... modifiers)
GAMSCheckpoint addCheckpoint()
GAMSModelInstance addModelInstance()
void setWorkingDirectory(String directory)
static final String FILE_SEPARATOR
GAMSDatabase OutDB()
GAMSVariable getVariable(String identifier)
T addRecord(Vector< String > keys)