1package com.gams.examples.benders;
4import java.util.HashMap;
5import java.util.LinkedList;
8import java.util.Map.Entry;
40@SuppressWarnings(
"unchecked")
43 public static void main(String[] args) {
48 File workingDirectory =
new File(System.getProperty(
"user.dir"),
"Benders2StageMT");
49 workingDirectory.mkdir();
58 optData.
defines(
"nrScen",
"100");
69 opt.
defines(
"maxiter", Integer.toString(maxiter));
82 masteri.
instantiate(
"masterproblem max zmaster using lp", opt,
91 LinkedList<Tuple> demQueue =
new LinkedList<Tuple>();
98 for (
int i = 1; i < numThreads; i++)
105 double lowerbound = Double.NEGATIVE_INFINITY, upperbound = Double.POSITIVE_INFINITY, objmaster = Double.POSITIVE_INFINITY;
108 System.out.println(
"Iteration: " + iter);
125 Map<String,Double> demDict =
new HashMap<String, Double>();
127 String[] keys =
new String[] { s.getKey(0), j.getKey(0) };
128 demDict.put( j.getKey(0), Double.valueOf( scenarioData.
findRecord( keys ).
getValue()) );
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 );
136 for (
int i = 0; i < numThreads; i++)
137 subi[i].SyncDB().getParameter(
"received").clear();
141 cutcoeff.
addRecord(
new String[] {Integer.toString(iter), r.getKey(0)});
142 for (
int i = 0; i < numThreads; i++)
148 cutconst.
addRecord(Integer.toString(iter));
149 double objsubsum = 0.0;
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] ;
158 for (
int i = 0; i < numThreads; i++)
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>();
164 Map<String, Double> cmap = (Map<String, Double>) coef[i];
165 cmap.put( j.getKey(0), Double.valueOf(0.0) );
170 Scenario[] sc =
new Scenario[numThreads];
171 for (
int i = 0; i < numThreads; i++)
173 sc[i] =
new Scenario( i, subi[i], cons[i], (Map<String, Double>) coef[i], demQueue, objsub[i], queueMutex, ioMutex );
179 for (
int i = 0; i < numThreads; i++)
183 }
catch (InterruptedException e) {
188 for (
int i = 0; i < numThreads; i++)
190 objsubsum += objsub[i].get().doubleValue();
191 double new_consValue = cutconst.
findRecord( Integer.toString(iter) ).
getValue() + cons[i].get().doubleValue();
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();
203 lowerbound = Math.max(lowerbound, objmaster + objsubsum);
206 if (iter == maxiter + 1)
209 System.out.println(
" lowerbound: " + lowerbound +
" upperbound: " + upperbound +
" objmaster: " + objmaster);
211 }
while ((upperbound - lowerbound) >= 0.001 * (1 + Math.abs(upperbound)));
222 static class Scenario
extends Thread {
225 Wrapper<Double> _cutconst;
226 List<Tuple> _demQueue;
227 Map<String, Double> _cutcoeff;
228 Wrapper<Double> _objsub;
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) {
246 _cutconst = cutconst;
247 _cutcoeff = cutcoeff;
248 _demQueue = demQueue;
250 _queueMutex = queueMutex;
260 synchronized (_queueMutex)
262 if (_demQueue.size() == 0)
265 demDict = _demQueue.remove(0);
269 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
275 synchronized (_ioMutex)
280 double probability = demDict.getItem2().doubleValue();
282 _objsub.set( Double.valueOf( new_objsubValue ) );
284 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
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 );
295 static String data =
"Sets \n"+
296 "i factories /f1*f3/ \n"+
297 "j distribution centers /d1*d5/ \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"+
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"+
314 "$ifthen not set useBig \n"+
316 " s scenarios /lo,mid,hi/ \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"+
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"+
333 static String masterModel =
"Sets \n"+
335 "j distribution centers \n"+
338 "capacity(i) unit capacity at factories \n"+
339 "prodcost unit production cost \n"+
340 "transcost(i,j) unit transportation cost \n"+
342 "$if not set datain $abort 'datain not set' \n"+
343 "$gdxin %datain% \n"+
344 "$load i j capacity prodcost transcost \n"+
346 "* Benders master problem \n"+
347 "$if not set maxiter $set maxiter 25 \n"+
349 " iter max Benders iterations /1*%maxiter%/ \n"+
352 " cutconst(iter) constants in optimality cuts \n"+
353 " cutcoeff(iter,j) coefficients in optimality cuts \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"+
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"+
370 " zmaster =e= theta -sum((i,j), transcost(i,j)*ship(i,j)) \n"+
371 " - sum(i,prodcost*product(i)); \n"+
373 "receive(j).. received(j) =e= sum(i, ship(i,j)); \n"+
375 "production(i).. product(i) =e= sum(j, ship(i,j)); \n"+
376 "product.up(i) = capacity(i); \n"+
378 "optcut(iter).. theta =l= cutconst(iter) + \n"+
379 " sum(j, cutcoeff(iter,j)*received(j)); \n"+
381 "model masterproblem /all/; \n"+
383 "* Initialize cut to be non-binding \n"+
384 "cutconst(iter) = 1e15; \n"+
385 "cutcoeff(iter,j) = eps; \n"+
388 static String subModel =
"Sets \n"+
390 " j distribution centers \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"+
398 "$if not set datain $abort 'datain not set' \n"+
399 "$gdxin %datain% \n"+
400 "$load i j demand price wastecost \n"+
402 "* Benders' subproblem \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"+
411 " subobj subproblem objective function \n"+
412 " selling(j) part of received is sold \n"+
413 " market(j) upperbound on sales \n"+
417 " zsub =e= sum(j, price*sales(j)) - sum(j, wastecost*waste(j)); \n"+
419 "selling(j).. sales(j) + waste(j) =e= received(j); \n"+
421 "market(j).. sales(j) =l= demand(j); \n"+
423 "model subproblem /subobj,selling,market/; \n"+
425 "* Initialize received \n"+
426 "received(j) = demand(j); \n"+
433 public Wrapper(T value) { _value = value; }
434 public T
get() {
return _value; }
435 public void set(T anotherValue) { _value = anotherValue; }
444 Map<String, Double> _item3;
445 public Tuple(String item1, Double item2, Map<String, Double> item3) {
450 public String getItem1() {
return _item1; }
451 public Double getItem2() {
return _item2; }
452 public Map<String, Double> getItem3() {
return _item3; }
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)
GAMSModelInstance copyModelInstance()
GAMSGlobals.ModelStat getModelStatus()
void instantiate(String modelDefinition, GAMSModifier ... modifiers)
void defines(String defStr, String asStr)
void setAllModelTypes(String value)
void setValue(double 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).