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
10import com.gams.api.GAMSCheckpoint;
11import com.gams.api.GAMSException;
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.GAMSSetRecord;
19import com.gams.api.GAMSVariable;
20import com.gams.api.GAMSVariableRecord;
21import com.gams.api.GAMSWorkspace;
22import com.gams.api.GAMSWorkspaceInfo;
23
40@SuppressWarnings("unchecked")
41public class Benders2StageMT {
42
43 public static void main(String[] args) {
44 GAMSWorkspaceInfo wsInfo = new GAMSWorkspaceInfo();
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
115 masteri.solve(GAMSModelInstance.SymbolUpdateType.BASECASE);
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
272 _submi.solve(GAMSModelInstance.SymbolUpdateType.BASECASE);
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}
com::gams::api::GAMSCheckpoint::addModelInstance
GAMSModelInstance addModelInstance()
com::gams::api::GAMSDatabase::addVariable
GAMSVariable addVariable(String identifier, int dimension, GAMSGlobals.VarType varType)
com::gams::api::GAMSDatabase::getParameter
GAMSParameter getParameter(String identifier)
com::gams::api::GAMSDatabase::getEquation
GAMSEquation getEquation(String identifier)
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::GAMSJob::OutDB
GAMSDatabase OutDB()
com::gams::api::GAMSModelInstance::copyModelInstance
GAMSModelInstance copyModelInstance()
com::gams::api::GAMSModelInstance::getModelStatus
GAMSGlobals.ModelStat getModelStatus()
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::GAMSOptions::setAllModelTypes
void setAllModelTypes(String value)
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.benders.Benders2StageMT
This example demonstrates a parallel implementation of a simple Benders decomposition method for a st...
Definition: Benders2StageMT.java:41
com::gams
Provides package namespace for Java interface and examples to General Algebraic Model System (GAMS).
com
&#160;