1package com.gams.examples.benders;
4 import java.util.HashMap;
5 import java.util.LinkedList;
8 import java.util.Map.Entry;
39 @SuppressWarnings(
"unchecked")
42 public static void main(String[] args) {
47 File workingDirectory =
new File(System.getProperty(
"user.dir"),
"Benders2StageMT");
48 workingDirectory.mkdir();
57 optData.
defines(
"nrScen",
"100");
68 opt.
defines(
"maxiter", Integer.toString(maxiter));
81 masteri.
instantiate(
"masterproblem max zmaster using lp", opt,
90 LinkedList<Tuple> demQueue =
new LinkedList<Tuple>();
97 for (
int i = 1; i < numThreads; i++)
104 double lowerbound = Double.NEGATIVE_INFINITY, upperbound = Double.POSITIVE_INFINITY, objmaster = Double.POSITIVE_INFINITY;
107 System.out.println(
"Iteration: " + iter);
124 Map<String,Double> demDict =
new HashMap<String, Double>();
126 String[] keys =
new String[] { s.getKey(0), j.getKey(0) };
127 demDict.put( j.getKey(0),
new Double( scenarioData.
findRecord( keys ).getValue()) );
129 String item1 = s.getKey(0);
130 Double item2 =
new Double( scenarioData.
findRecord(
new String[] { s.getKey(0),
"prob" } ).getValue() );
131 Tuple items =
new Tuple( item1, item2, demDict );
135 for (
int i = 0; i < numThreads; i++)
136 subi[i].SyncDB().getParameter(
"received").clear();
140 cutcoeff.
addRecord(
new String[] {Integer.toString(iter), r.getKey(0)});
141 for (
int i = 0; i < numThreads; i++)
147 cutconst.
addRecord(Integer.toString(iter));
148 double objsubsum = 0.0;
151 Object queueMutex =
new Object();
152 Object ioMutex =
new Object();
153 Wrapper<Double>[] objsub =
new Wrapper[numThreads];
154 Object[] coef =
new Object[numThreads];
155 Wrapper<Double>[] cons =
new Wrapper[numThreads] ;
157 for (
int i = 0; i < numThreads; i++)
159 objsub[i] =
new Wrapper<Double>(
new Double(0.0));
160 cons[i] =
new Wrapper<Double>(
new Double(0.0));
161 coef[i] =
new HashMap<String, Double>();
163 Map<String, Double> cmap = (Map<String, Double>) coef[i];
164 cmap.put( j.getKey(0),
new Double(0.0) );
169 Scenario[] sc =
new Scenario[numThreads];
170 for (
int i = 0; i < numThreads; i++)
172 sc[i] =
new Scenario( i, subi[i], cons[i], (Map<String, Double>) coef[i], demQueue, objsub[i], queueMutex, ioMutex );
178 for (
int i = 0; i < numThreads; i++)
182 }
catch (InterruptedException e) {
187 for (
int i = 0; i < numThreads; i++)
189 objsubsum += objsub[i].get().doubleValue();
190 double new_consValue = cutconst.
findRecord( Integer.toString(iter) ).getValue() + cons[i].get().doubleValue();
191 cutconst.
findRecord( Integer.toString(iter) ).setValue( new_consValue );
195 Map<String, Double> map = (Map<String, Double>) coef[i];
196 String[] keys =
new String[] { Integer.toString(iter), j.getKey(0) };
197 double newvalue = cutcoeff.
findRecord( keys ).getValue( ) + map.get( j.getKey(0) ).doubleValue();
198 cutcoeff.
findRecord( keys ).setValue( newvalue );
202 lowerbound = Math.max(lowerbound, objmaster + objsubsum);
205 if (iter == maxiter + 1)
208 System.out.println(
" lowerbound: " + lowerbound +
" upperbound: " + upperbound +
" objmaster: " + objmaster);
210 }
while ((upperbound - lowerbound) >= 0.001 * (1 + Math.abs(upperbound)));
221 static class Scenario
extends Thread {
224 Wrapper<Double> _cutconst;
225 List<Tuple> _demQueue;
226 Map<String, Double> _cutcoeff;
227 Wrapper<Double> _objsub;
241 public Scenario(
int i ,
GAMSModelInstance submi, Wrapper<Double> cutconst, Map<String, Double> cutcoeff, LinkedList<Tuple> demQueue,
242 Wrapper<Double> objsub, Object queueMutex, Object ioMutex) {
245 _cutconst = cutconst;
246 _cutcoeff = cutcoeff;
247 _demQueue = demQueue;
249 _queueMutex = queueMutex;
259 synchronized (_queueMutex)
261 if (_demQueue.size() == 0)
264 demDict = _demQueue.remove(0);
268 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
274 synchronized (_ioMutex)
279 double probability = demDict.getItem2().doubleValue();
281 _objsub.set(
new Double( new_objsubValue ) );
283 for (Entry<String, Double> kv : demDict.getItem3().entrySet())
285 double new_custconstValue = _cutconst.get().doubleValue() + probability * _submi.
SyncDB().
getEquation(
"market").
findRecord( kv.getKey() ).getMarginal() * kv.getValue().doubleValue();
286 _cutconst.set(
new Double( new_custconstValue ) );
287 double new_cutcoeffValue = _cutcoeff.get( kv.getKey() ).doubleValue() + probability * _submi.
SyncDB().
getEquation(
"selling").
findRecord(kv.getKey()).getMarginal();
288 _cutcoeff.put( kv.getKey(), new_cutcoeffValue );
294 static String data =
"Sets \n"+
295 "i factories /f1*f3/ \n"+
296 "j distribution centers /d1*d5/ \n"+
299 "capacity(i) unit capacity at factories \n"+
300 " /f1 500, f2 450, f3 650/ \n"+
301 "demand(j) unit demand at distribution centers \n"+
302 " /d1 160, d2 120, d3 270, d4 325, d5 700 / \n"+
303 "prodcost unit production cost /14/ \n"+
304 "price sales price /24/ \n"+
305 "wastecost cost of removal of overstocked products /4/ \n"+
307 "Table transcost(i,j) unit transportation cost \n"+
308 " d1 d2 d3 d4 d5 \n"+
309 " f1 2.49 5.21 3.76 4.85 2.07 \n"+
310 " f2 1.46 2.54 1.83 1.86 4.76 \n"+
311 " f3 3.26 3.08 2.60 3.76 4.45; \n"+
313 "$ifthen not set useBig \n"+
315 " s scenarios /lo,mid,hi/ \n"+
317 "Table ScenarioData(s,*) possible outcomes for demand plus probabilities \n"+
318 " d1 d2 d3 d4 d5 prob \n"+
319 " lo 150 100 250 300 600 0.25 \n"+
320 " mid 160 120 270 325 700 0.50 \n"+
321 " hi 170 135 300 350 800 0.25; \n"+
323 "$if not set nrScen $set nrScen 10 \n"+
324 "Set s scenarios /s1*s%nrScen%/;\n"+
325 "parameter ScenarioData(s,*) possible outcomes for demand plus probabilities;\n"+
326 "option seed=1234; \n"+
327 "ScenarioData(s,'prob') = 1/card(s); \n"+
328 "ScenarioData(s,j) = demand(j)*uniform(0.6,1.4); \n"+
332 static String masterModel =
"Sets \n"+
334 "j distribution centers \n"+
337 "capacity(i) unit capacity at factories \n"+
338 "prodcost unit production cost \n"+
339 "transcost(i,j) unit transportation cost \n"+
341 "$if not set datain $abort 'datain not set' \n"+
342 "$gdxin %datain% \n"+
343 "$load i j capacity prodcost transcost \n"+
345 "* Benders master problem \n"+
346 "$if not set maxiter $set maxiter 25 \n"+
348 " iter max Benders iterations /1*%maxiter%/ \n"+
351 " cutconst(iter) constants in optimality cuts \n"+
352 " cutcoeff(iter,j) coefficients in optimality cuts \n"+
355 " ship(i,j) shipments \n"+
356 " product(i) production \n"+
357 " received(j) quantity sent to market \n"+
358 " zmaster objective variable of master problem \n"+
359 " theta future profit \n"+
360 "Positive Variables ship; \n"+
363 " masterobj master objective function \n"+
364 " production(i) calculate production in each factory \n"+
365 " receive(j) calculate quantity to be send to markets \n"+
366 " optcut(iter) Benders optimality cuts; \n"+
369 " zmaster =e= theta -sum((i,j), transcost(i,j)*ship(i,j)) \n"+
370 " - sum(i,prodcost*product(i)); \n"+
372 "receive(j).. received(j) =e= sum(i, ship(i,j)); \n"+
374 "production(i).. product(i) =e= sum(j, ship(i,j)); \n"+
375 "product.up(i) = capacity(i); \n"+
377 "optcut(iter).. theta =l= cutconst(iter) + \n"+
378 " sum(j, cutcoeff(iter,j)*received(j)); \n"+
380 "model masterproblem /all/; \n"+
382 "* Initialize cut to be non-binding \n"+
383 "cutconst(iter) = 1e15; \n"+
384 "cutcoeff(iter,j) = eps; \n"+
387 static String subModel =
"Sets \n"+
389 " j distribution centers \n"+
392 " demand(j) unit demand at distribution centers \n"+
393 " price sales price \n"+
394 " wastecost cost of removal of overstocked products \n"+
395 " received(j) first stage decision units received \n"+
397 "$if not set datain $abort 'datain not set' \n"+
398 "$gdxin %datain% \n"+
399 "$load i j demand price wastecost \n"+
401 "* Benders' subproblem \n"+
404 " sales(j) sales (actually sold) \n"+
405 " waste(j) overstocked products \n"+
406 " zsub objective variable of sub problem \n"+
407 "Positive variables sales, waste \n"+
410 " subobj subproblem objective function \n"+
411 " selling(j) part of received is sold \n"+
412 " market(j) upperbound on sales \n"+
416 " zsub =e= sum(j, price*sales(j)) - sum(j, wastecost*waste(j)); \n"+
418 "selling(j).. sales(j) + waste(j) =e= received(j); \n"+
420 "market(j).. sales(j) =l= demand(j); \n"+
422 "model subproblem /subobj,selling,market/; \n"+
424 "* Initialize received \n"+
425 "received(j) = demand(j); \n"+
432 public Wrapper(T value) { _value = value; }
433 public T
get() {
return _value; }
434 public void set(T anotherValue) { _value = anotherValue; }
443 Map<String, Double> _item3;
444 public Tuple(String item1, Double item2, Map<String, Double> item3) {
449 public String getItem1() {
return _item1; }
450 public Double getItem2() {
return _item2; }
451 public Map<String, Double> getItem3() {
return _item3; }