Loading...
Searching...
No Matches
Benders2StageMT.java
1package com.gams.examples.benders;
2
3import java.io.File;
4import java.util.HashMap;
5import java.util.LinkedList;
6import java.util.List;
7import java.util.Map;
8import java.util.Map.Entry;
9
12import com.gams.api.GAMSGlobals;
13import com.gams.api.GAMSJob;
16import com.gams.api.GAMSOptions;
23
40@SuppressWarnings("unchecked")
41public class Benders2StageMT {
42
43 public static void main(String[] args) {
45 if (args.length > 0)
46 wsInfo.setSystemDirectory( args[0] );
47
48 File workingDirectory = new File(System.getProperty("user.dir"), "Benders2StageMT");
49 workingDirectory.mkdir();
50 wsInfo.setWorkingDirectory(workingDirectory.getAbsolutePath());
51
52 GAMSWorkspace ws = new GAMSWorkspace( wsInfo );
53
54 GAMSJob dataJob = ws.addJobFromString(data);
55
56 GAMSOptions optData = ws.addOptions();
57 optData.defines("useBig", "1");
58 optData.defines("nrScen", "100");
59
60 dataJob.run(optData);
61
62 optData.dispose();
63
64 GAMSParameter scenarioData = dataJob.OutDB().getParameter("ScenarioData");
65
66 GAMSOptions opt = ws.addOptions();
67 opt.defines("datain", dataJob.OutDB().getName());
68 int maxiter = 40;
69 opt.defines("maxiter", Integer.toString(maxiter));
70 opt.setAllModelTypes( "cplex" );
71
72 GAMSCheckpoint cpMaster = ws.addCheckpoint();
73 GAMSCheckpoint cpSub = ws.addCheckpoint();
74
75 ws.addJobFromString(masterModel).run(opt, cpMaster, dataJob.OutDB());
76
77 GAMSModelInstance masteri = cpMaster.addModelInstance();
78 GAMSParameter cutconst = masteri.SyncDB().addParameter("cutconst", 1, "Benders optimality cut constant");
79 GAMSParameter cutcoeff = masteri.SyncDB().addParameter("cutcoeff", 2, "Benders optimality coefficients");
80 GAMSVariable theta = masteri.SyncDB().addVariable("theta", 0, GAMSGlobals.VarType.FREE, "Future profit function variable");
81 GAMSParameter thetaFix = masteri.SyncDB().addParameter("thetaFix", 0, "");
82 masteri.instantiate("masterproblem max zmaster using lp", opt,
83 new GAMSModifier[] { new GAMSModifier(cutconst), new GAMSModifier(cutcoeff), new GAMSModifier(theta,GAMSGlobals.UpdateAction.FIXED,thetaFix) }
84 );
85
86 ws.addJobFromString(subModel).run(opt, cpSub, dataJob.OutDB());
87
88
89 int numThreads = 4;
90 GAMSModelInstance[] subi = new GAMSModelInstance[numThreads];
91 LinkedList<Tuple> demQueue = new LinkedList<Tuple>();
92
93 subi[0] = cpSub.addModelInstance();
94 GAMSParameter received = subi[0].SyncDB().addParameter("received", 1, "units received from first stage solution");
95 GAMSParameter demand = subi[0].SyncDB().addParameter("demand", 1, "stochastic demand");
96 subi[0].instantiate("subproblem max zsub using lp", opt, new GAMSModifier[] { new GAMSModifier(received), new GAMSModifier(demand) } );
97
98 for (int i = 1; i < numThreads; i++)
99 {
100 subi[i] = subi[0].copyModelInstance();
101 }
102
103 opt.dispose();
104
105 double lowerbound = Double.NEGATIVE_INFINITY, upperbound = Double.POSITIVE_INFINITY, objmaster = Double.POSITIVE_INFINITY;
106 int iter = 1;
107 do {
108 System.out.println("Iteration: " + iter);
109 // Solve master
110 if (iter == 1) // fix theta for first iteration
111 thetaFix.addRecord().setValue( 0.0 );
112 else
113 thetaFix.clear();
114
116 System.out.println(" Master " + masteri.getModelStatus() + " : obj=" + masteri.SyncDB().getVariable("zmaster").getFirstRecord().getLevel());
117
118 if (iter > 1)
119 upperbound = masteri.SyncDB().getVariable("zmaster").getFirstRecord().getLevel();
120
121 objmaster = masteri.SyncDB().getVariable("zmaster").getFirstRecord().getLevel() - theta.getFirstRecord().getLevel();
122
123 for (GAMSSetRecord s : dataJob.OutDB().getSet("s"))
124 {
125 Map<String,Double> demDict = new HashMap<String, Double>();
126 for (GAMSSetRecord j : dataJob.OutDB().getSet("j")) {
127 String[] keys = new String[] { s.getKey(0), j.getKey(0) };
128 demDict.put( j.getKey(0), Double.valueOf( scenarioData.findRecord( keys ).getValue()) );
129 }
130 String item1 = s.getKey(0);
131 Double item2 = Double.valueOf( scenarioData.findRecord(new String[] { s.getKey(0), "prob" } ).getValue() );
132 Tuple items = new Tuple( item1, item2, demDict );
133 demQueue.add(items);
134 }
135
136 for (int i = 0; i < numThreads; i++)
137 subi[i].SyncDB().getParameter("received").clear();
138
139 for (GAMSVariableRecord r : masteri.SyncDB().getVariable("received"))
140 {
141 cutcoeff.addRecord(new String[] {Integer.toString(iter), r.getKey(0)});
142 for (int i = 0; i < numThreads; i++)
143 {
144 subi[i].SyncDB().getParameter("received").addRecord(r.getKeys()).setValue( r.getLevel() );
145 }
146 }
147
148 cutconst.addRecord(Integer.toString(iter));
149 double objsubsum = 0.0;
150
151 // solve multiple model instances in parallel
152 Object queueMutex = new Object();
153 Object ioMutex = new Object();
154 Wrapper<Double>[] objsub = new Wrapper[numThreads];
155 Object[] coef = new Object[numThreads];
156 Wrapper<Double>[] cons = new Wrapper[numThreads] ;
157
158 for (int i = 0; i < numThreads; i++)
159 {
160 objsub[i] = new Wrapper<Double>(Double.valueOf(0.0));
161 cons[i] = new Wrapper<Double>(Double.valueOf(0.0));
162 coef[i] = new HashMap<String, Double>();
163 for (GAMSSetRecord j : dataJob.OutDB().getSet("j")) {
164 Map<String, Double> cmap = (Map<String, Double>) coef[i];
165 cmap.put( j.getKey(0), Double.valueOf(0.0) );
166 }
167 }
168
169 // Solve of sub problems in parallel
170 Scenario[] sc = new Scenario[numThreads];
171 for (int i = 0; i < numThreads; i++)
172 {
173 sc[i] = new Scenario( i, subi[i], cons[i], (Map<String, Double>) coef[i], demQueue, objsub[i], queueMutex, ioMutex );
174 sc[i].start();
175 }
176
177
178 // Synchronize all sub problems
179 for (int i = 0; i < numThreads; i++)
180 {
181 try {
182 sc[i].join();
183 } catch (InterruptedException e) {
184 e.printStackTrace();
185 }
186 }
187
188 for (int i = 0; i < numThreads; i++)
189 {
190 objsubsum += objsub[i].get().doubleValue();
191 double new_consValue = cutconst.findRecord( Integer.toString(iter) ).getValue() + cons[i].get().doubleValue();
192 cutconst.findRecord( Integer.toString(iter) ).setValue( new_consValue );
193
194 for (GAMSSetRecord j : dataJob.OutDB().getSet("j"))
195 {
196 Map<String, Double> map = (Map<String, Double>) coef[i];
197 String[] keys = new String[] { Integer.toString(iter), j.getKey(0) };
198 double newvalue = cutcoeff.findRecord( keys ).getValue( ) + map.get( j.getKey(0) ).doubleValue();
199 cutcoeff.findRecord( keys ).setValue( newvalue );
200 }
201 }
202
203 lowerbound = Math.max(lowerbound, objmaster + objsubsum);
204
205 iter++;
206 if (iter == maxiter + 1)
207 throw new GAMSException("Benders out of iterations");
208
209 System.out.println(" lowerbound: " + lowerbound + " upperbound: " + upperbound + " objmaster: " + objmaster);
210
211 } while ((upperbound - lowerbound) >= 0.001 * (1 + Math.abs(upperbound)));
212
213 masteri.dispose();
214
215 for(GAMSModelInstance inst : subi)
216 {
217 inst.dispose();
218 }
219 }
220
222 static class Scenario extends Thread {
223 int _i;
224 GAMSModelInstance _submi;
225 Wrapper<Double> _cutconst;
226 List<Tuple> _demQueue;
227 Map<String, Double> _cutcoeff;
228 Wrapper<Double> _objsub;
229 Object _queueMutex;
230 Object _ioMutex;
231
242 public Scenario(int i , GAMSModelInstance submi, Wrapper<Double> cutconst, Map<String, Double> cutcoeff, LinkedList<Tuple> demQueue,
243 Wrapper<Double> objsub, Object queueMutex, Object ioMutex) {
244 _i = i;
245 _submi = submi;
246 _cutconst = cutconst;
247 _cutcoeff = cutcoeff;
248 _demQueue = demQueue;
249 _objsub = objsub;
250 _queueMutex = queueMutex;
251 _ioMutex = ioMutex;
252 }
253
255 public void run() {
256 while (true)
257 {
258 Tuple demDict;
259
260 synchronized (_queueMutex)
261 {
262 if (_demQueue.size() == 0)
263 break;
264 else
265 demDict = _demQueue.remove(0); // dequeue
266 }
267
268 _submi.SyncDB().getParameter("demand").clear();
269 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
270 _submi.SyncDB().getParameter("demand").addRecord(kv.getKey()).setValue( kv.getValue() );
271
273
274
275 synchronized (_ioMutex)
276 {
277 System.out.println(" Thread "+_i+" : Sub " + _submi.getModelStatus().toString() + " : obj=" + _submi.SyncDB().getVariable("zsub").getFirstRecord().getLevel());
278 }
279
280 double probability = demDict.getItem2().doubleValue();
281 double new_objsubValue = _objsub.get().doubleValue() + probability * _submi.SyncDB().getVariable("zsub").getFirstRecord().getLevel();
282 _objsub.set( Double.valueOf( new_objsubValue ) );
283
284 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
285 {
286 double new_custconstValue = _cutconst.get().doubleValue() + probability * _submi.SyncDB().getEquation("market").findRecord( kv.getKey() ).getMarginal() * kv.getValue().doubleValue();
287 _cutconst.set( Double.valueOf( new_custconstValue ) );
288 double new_cutcoeffValue = _cutcoeff.get( kv.getKey() ).doubleValue() + probability * _submi.SyncDB().getEquation("selling").findRecord(kv.getKey()).getMarginal();
289 _cutcoeff.put( kv.getKey(), new_cutcoeffValue );
290 }
291 }
292 }
293 }
294
295 static String data = "Sets \n"+
296 "i factories /f1*f3/ \n"+
297 "j distribution centers /d1*d5/ \n"+
298 " \n"+
299 "Parameter \n"+
300 "capacity(i) unit capacity at factories \n"+
301 " /f1 500, f2 450, f3 650/ \n"+
302 "demand(j) unit demand at distribution centers \n"+
303 " /d1 160, d2 120, d3 270, d4 325, d5 700 / \n"+
304 "prodcost unit production cost /14/ \n"+
305 "price sales price /24/ \n"+
306 "wastecost cost of removal of overstocked products /4/ \n"+
307 " \n"+
308 "Table transcost(i,j) unit transportation cost \n"+
309 " d1 d2 d3 d4 d5 \n"+
310 " f1 2.49 5.21 3.76 4.85 2.07 \n"+
311 " f2 1.46 2.54 1.83 1.86 4.76 \n"+
312 " f3 3.26 3.08 2.60 3.76 4.45; \n"+
313 " \n"+
314 "$ifthen not set useBig \n"+
315 "Set \n"+
316 " s scenarios /lo,mid,hi/ \n"+
317 " \n"+
318 "Table ScenarioData(s,*) possible outcomes for demand plus probabilities \n"+
319 " d1 d2 d3 d4 d5 prob \n"+
320 " lo 150 100 250 300 600 0.25 \n"+
321 " mid 160 120 270 325 700 0.50 \n"+
322 " hi 170 135 300 350 800 0.25; \n"+
323 "$else \n"+
324 "$if not set nrScen $set nrScen 10 \n"+
325 "Set s scenarios /s1*s%nrScen%/;\n"+
326 "parameter ScenarioData(s,*) possible outcomes for demand plus probabilities;\n"+
327 "option seed=1234; \n"+
328 "ScenarioData(s,'prob') = 1/card(s); \n"+
329 "ScenarioData(s,j) = demand(j)*uniform(0.6,1.4); \n"+
330 "$endif \n"+
331 " \n";
332
333 static String masterModel = "Sets \n"+
334 "i factories \n"+
335 "j distribution centers \n"+
336 " \n"+
337 "Parameter \n"+
338 "capacity(i) unit capacity at factories \n"+
339 "prodcost unit production cost \n"+
340 "transcost(i,j) unit transportation cost \n"+
341 " \n"+
342 "$if not set datain $abort 'datain not set' \n"+
343 "$gdxin %datain% \n"+
344 "$load i j capacity prodcost transcost \n"+
345 " \n"+
346 "* Benders master problem \n"+
347 "$if not set maxiter $set maxiter 25 \n"+
348 "Set \n"+
349 " iter max Benders iterations /1*%maxiter%/ \n"+
350 " \n"+
351 "Parameter \n"+
352 " cutconst(iter) constants in optimality cuts \n"+
353 " cutcoeff(iter,j) coefficients in optimality cuts \n"+
354 " \n"+
355 "Variables \n"+
356 " ship(i,j) shipments \n"+
357 " product(i) production \n"+
358 " received(j) quantity sent to market \n"+
359 " zmaster objective variable of master problem \n"+
360 " theta future profit \n"+
361 "Positive Variables ship; \n"+
362 " \n"+
363 "Equations \n"+
364 " masterobj master objective function \n"+
365 " production(i) calculate production in each factory \n"+
366 " receive(j) calculate quantity to be send to markets \n"+
367 " optcut(iter) Benders optimality cuts; \n"+
368 " \n"+
369 "masterobj.. \n"+
370 " zmaster =e= theta -sum((i,j), transcost(i,j)*ship(i,j)) \n"+
371 " - sum(i,prodcost*product(i)); \n"+
372 " \n"+
373 "receive(j).. received(j) =e= sum(i, ship(i,j)); \n"+
374 " \n"+
375 "production(i).. product(i) =e= sum(j, ship(i,j)); \n"+
376 "product.up(i) = capacity(i); \n"+
377 " \n"+
378 "optcut(iter).. theta =l= cutconst(iter) + \n"+
379 " sum(j, cutcoeff(iter,j)*received(j)); \n"+
380 " \n"+
381 "model masterproblem /all/; \n"+
382 " \n"+
383 "* Initialize cut to be non-binding \n"+
384 "cutconst(iter) = 1e15; \n"+
385 "cutcoeff(iter,j) = eps; \n"+
386 " \n";
387
388 static String subModel = "Sets \n"+
389 " i factories \n"+
390 " j distribution centers \n"+
391 " \n"+
392 "Parameter \n"+
393 " demand(j) unit demand at distribution centers \n"+
394 " price sales price \n"+
395 " wastecost cost of removal of overstocked products \n"+
396 " received(j) first stage decision units received \n"+
397 " \n"+
398 "$if not set datain $abort 'datain not set' \n"+
399 "$gdxin %datain% \n"+
400 "$load i j demand price wastecost \n"+
401 " \n"+
402 "* Benders' subproblem \n"+
403 " \n"+
404 "Variables \n"+
405 " sales(j) sales (actually sold) \n"+
406 " waste(j) overstocked products \n"+
407 " zsub objective variable of sub problem \n"+
408 "Positive variables sales, waste \n"+
409 " \n"+
410 "Equations \n"+
411 " subobj subproblem objective function \n"+
412 " selling(j) part of received is sold \n"+
413 " market(j) upperbound on sales \n"+
414 "; \n"+
415 " \n"+
416 "subobj.. \n"+
417 " zsub =e= sum(j, price*sales(j)) - sum(j, wastecost*waste(j)); \n"+
418 " \n"+
419 "selling(j).. sales(j) + waste(j) =e= received(j); \n"+
420 " \n"+
421 "market(j).. sales(j) =l= demand(j); \n"+
422 " \n"+
423 "model subproblem /subobj,selling,market/; \n"+
424 " \n"+
425 "* Initialize received \n"+
426 "received(j) = demand(j); \n"+
427 " \n";
428}
429
431class Wrapper<T> {
432 T _value;
433 public Wrapper(T value) { _value = value; }
434 public T get() { return _value; }
435 public void set(T anotherValue) { _value = anotherValue; }
436}
437
441class Tuple {
442 String _item1;
443 Double _item2;
444 Map<String, Double> _item3;
445 public Tuple(String item1, Double item2, Map<String, Double> item3) {
446 _item1 = item1;
447 _item2 = item2;
448 _item3 = item3;
449 }
450 public String getItem1() { return _item1; }
451 public Double getItem2() { return _item2; }
452 public Map<String, Double> getItem3() { return _item3; }
453}
GAMSModelInstance addModelInstance()
GAMSVariable addVariable(String identifier, int dimension, GAMSGlobals.VarType varType)
GAMSParameter getParameter(String identifier)
GAMSEquation getEquation(String identifier)
GAMSParameter addParameter(String identifier, int dimension)
GAMSVariable getVariable(String identifier)
GAMSSet getSet(String identifier)
GAMSDatabase OutDB()
GAMSModelInstance copyModelInstance()
GAMSGlobals.ModelStat getModelStatus()
void instantiate(String modelDefinition, GAMSModifier ... modifiers)
void defines(String defStr, String asStr)
void setAllModelTypes(String value)
T findRecord(String ... keys)
T addRecord(Vector< String > keys)
void setSystemDirectory(String directory)
void setWorkingDirectory(String directory)
GAMSJob addJobFromString(String source)
GAMSCheckpoint addCheckpoint()
This example demonstrates a parallel implementation of a simple Benders decomposition method for a st...
Provides package namespace for Java interface and examples to General Algebraic Model System (GAMS).
&#160;