Description

Keywords: mixed integer linear programming, dice designment, mathematics,
          nontransitive dice, decomposition, GAMS grid facility

Large Model of Type : MIP

Category : GAMS Model library

Main file : dicegrid.gms

$title MIP Decomposition and Parallel Grid Submission - DICE Example (DICEGRID,SEQ=330)

$onText
Keywords: mixed integer linear programming, dice designment, mathematics,
          nontransitive dice, decomposition, GAMS grid facility
$offText

$eolCom //

* Retrieve the model dice from the GAMS Model library and include the model source
$call gamslib -q dice
$set nosolve yes       // Instruct the dice model source to skip the solve statement
$include dice.gms

* Some macro definition to make the code somewhat independent of the objective direction
$set gt '>' $set cutoff 'cutlo' $set incumbentInit -INF
* Use the line below for minimization problems
*$set gt '<' $set cutoff 'cutup' $set incumbentInit +INF

$onText
File and container names
 GAMS Sub-Programs
   writeincb.gms  GAMS program called by GAMS/Cplex whenever a new incumbent
                  is found by the Cplex workers
   checkincb.gms  GAMS program frequently called by the master to see if a
                  better overall incumbent has been found by the Cplex workers.
                  In case of a new incumbent, this program communicates the
                  incumbent value as a cutoff to all Cplex workers.

 GAMS/Cplex Option files
   cplex.opt      Includes 'dumptree' option to produce decomposition
   cplex.op2      worker option file in case of sequential submit
   cplex.op3      incumbent as cutoff option (written by checkincb.gms, read by workers)
   cplex.XXX      XXX=100+userjobid (UJI) option file for worker with userjobid

 Text files
   t%UJI%.trg     trigger names that instruct the GAMS/Cplex work to read cplex.op3
   incb%UJD%.txt  current worker incumbent values
   allincb.txt    temp file to collect work incumbent values used by checkincb.gms

 GDX files
   bnd%UJI%.gdx   decomposition bound files created by 'dumptree' option
   incb.gdx       container name for incumbent value and solution values
   bchout_i%UJI%.gdx  worker incumbent solution processed by writeincb.gms
$offText

* Set number of binary variables to decompose the original one (note: 2**nsub jobs)
$set nvars 4
$eval nsub power(2,%nvars%)
Set
   s_grid    'subproblems'                   / 1*%nsub%  /
   nvars     'binary variable for scenarios' / 1*%nvars% /
   up_down   'up/down of binary variable'    / up, down  /
   bndUpdate(s_grid,nvars,up_down) 'Binary variables to fix in subproblem' / system.PowerSetRight /;
File
   flog 'file handle to write to the log'   / '' /
   fopt 'file handle to write option files' / 'cplex.opt' /;

$sTitle Parallel Submit and Solve in parallel

$onText
Create a Cplex option file for each job. This option file instructs
the GAMS/Cplex worker to call out to the GAMS program writeincb.gms
(userincbicall) to save the incumbents found by the workers. It also
tells the GAMS/Cplex jobs to look for a trigger file (iatriggerfile).
If the file exists, GAMS/Cplex will remove the trigger file and read
an option file (iafile). The time GAMS/Cplex looks for a trigger file
(iatriggertime) is set to 1 second, which is quiet small and should be
significantly increased for more difficult problems.

Because of name conflicts every communication file is postfixed with
the userjobid and postfixed with the GAMS working directory.

In previous version the GAMS/Cplex option dumptree could be used to
create a decomposition of the search space. With the new generic
callbacks in Cplex this is not possible anymore and we need to generate
a different decompostion scheme. Here we just select a number of variables
and fix them to 0 or 1 in the different scenarios.

The nsub+1 job will run on the original problem and focus on finding
good feasible solutions.
$offText

Set
   selbvar(dice,f,fp) 'selected variable to decompose on'
   bnvarmap(nvars,dice,f,fp) 'mapping between nvars and selbvar';
Scalars   
   diceOffSet, fOffSet, fpOffSet;

* Select randomly some binary variables from the model
repeat
  diceOffSet = uniformInt(0,card(dice)-1);
  fOffSet    = uniformInt(0,card(f)-1);
  fpOffSet   = uniformInt(0,card(fp)-1);
  loop((dice,f,fp)$(sameas('dice1',dice) and sameas('face1',f) and sameas('face1',fp)),
     selbvar(dice+diceOffSet,f+fOffSet,fp+fpOffSet) = yes);
until card(selbvar)>=%nvars%;
option bnvarmap(nvars:selbvar);

* Remove files so we start clean
$hiddenCall rm -f bch*.gdx t*.trg best_incumbent.gdx GMSbch*.*

Scalar cnt;
for(cnt = 1 to %nsub%+1,
   put_utility fopt 'ren' / 'cplex.' (100+cnt):0:0;
   put   'userincbicall updateincb.gms lo=2 appendLog=1'
       / 'userjobid ' cnt:0:0 
       / 'interactive 1' / 'iafile cplex.op3' / 'iatriggertime 1'
       / 'iatriggerfile t' cnt:0:0 '.trg'
       / 'mipemphasis 3';
   put$(cnt=%nsub%+1) / 'mipemphasis 1';
);
putclose fopt;

* generate a unique mutex ID
$eval mtxID round(frac(jnow)*24*60*60*1000)
$funcLibIn mtxlib mtxcclib
Function 
   create      / mtxlib.Create /
   timedLock   / mtxlib.TimedLock /
   unlock      / mtxlib.Unlock /
   delete      / mtxlib.Delete /;

abort$create(%mtxID%) 'problems creating mutex';

* Initialize the best incumbent GDX file
wnx.l = %incumbentInit%; execute_unload 'best_incumbent.gdx', wnx; wnx.l = 0;

xdice.solveLink = %solveLink.asyncGrid%; // use the GAMS grid submission

Parameter
    h(s_grid)     'job handle';

option optCr = 0, optCa = 0, solPrint = silent, mip = cplex, limRow=0, limCol = 0;
cnt = 0;
* Now submit the nsub jobs with the updated bounds asynchronously
loop(s_grid,
   cnt = cnt + 1;
   xdice.optFile = 100 + cnt;
   loop((bndUpdate(s_grid,nvars,'up')  ,bnvarmap(nvars,selbvar)), comp.fx(selbvar) = 1);
   loop((bndUpdate(s_grid,nvars,'down'),bnvarmap(nvars,selbvar)), comp.fx(selbvar) = 0);
   solve xdice using mip max wnx;
   h(s_grid) = xdice.handle;
   comp.lo(selbvar) = 0; comp.up(selbvar) = 1; // restore bounds
);

* Submit job with emphasis on finding good feasible solutions.  We do
* not wait for this job to be complete, we just use its incumbent to
* have good cutoff values early. After all sub jobs are back and the
* incumbent finding jobs still runs, we trigger the termination in the
* same way as we trigger updates to the cuttoff.
Scalar feashandle;
xdice.optFile = 100+%nsub%+1;
solve xdice using mip max wnx;
feashandle = xdice.handle;

Parameter
   rep       'report of times and solution';

* Collect
rep(s_grid,'mstat') = na;
rep(s_grid,'sstat') = na;

repeat
   loop(s_grid$handlecollect(h(s_grid)), // collect if job is completed
      rep(s_grid,'time')  = xdice.resUsd;
      rep(s_grid,'mstat') = xdice.modelStat;
      rep(s_grid,'sstat') = xdice.solveStat;
      rep(s_grid,'obj')   = xdice.objVal;
      display$handledelete(h(s_grid)) 'trouble deleting handles';
      h(s_grid) = 0;
   );
   display$sleep(card(h)*0.2) 'was sleeping for some time';
until card(h) = 0 or timeelapsed > 150;

Scalar optimal 'optimality indicator';
optimal = sum(s_grid$(rep(s_grid,'sstat')=1),1) = %nsub%;

put flog;
put$(card(h)>0)      '*** We have ' card(h):0:0 ' outstanding jobs.' /;
put$(not optimal)    '*** Some jobs returned with solver status <> 1. Optimality not guaranteed' /;
abort$timedLock(%mtxID%,1000) 'error acquiring lock for mutex';
execute_load 'best_incumbent.gdx', wnx;
abort$unlock(%mtxID%) 'error unlocking mutex';

if(not mapval(wnx.l), // not INF or -INF
   put$optimal       '*** Optimal solution found: '  wnx.l /;
   put$(not optimal) '*** Best collected solution: ' wnx.l /;
else
   put$optimal       '*** Problem infeasible' /;
   put$(not optimal) '*** No solution found' /;
 );
display rep;

* terminate job with mipemphasis=1
if(not handlecollect(feashandle),
   put_utility 'shell' / 'echo tilim 0 > cplex.op3'
   put_utility 'exec' / 'touch t' (%nsub%+1):0:0 '.trg'
   display$sleep(3) 'sleeping';
);
display$handledelete(feashandle) 'trying now to delete';
display$delete(%mtxID%) 'problems deleting mutex';

* drop the compile-time variable userjobid (perhaps set by command line) so the creation of the
* updateincb.gms has the %userjobid% verbatim and not subsituted.
$drop userjobid 
$onEcho > updateincb.gms
$title Code for worker %userjobid% to update best_incumbent.gdx
$onText
This uses the existing BCH facility. GAMS/Cplex exports the complete
incumbent in a GDX container called bchout_i%userjobid%.gdx. We only
need the objective variable. If the incumber is better than the
so far best known incumbent, we signal to all other jobs a new cutoff.
$offText

Variable wnx /L 0/, wnx_bi /L 0/;
$gdxIn bchout_i%userjobid%.gdx
$loadM wnx
$gdxIn

$funcLibIn mtxlib mtxcclib
Function 
   timedLock   / mtxlib.TimedLock /
   unlock      / mtxlib.Unlock /;
scalar cnt;         

abort$timedLock(%mtxID%,1000) 'error acquiring lock for mutex';
execute_load 'best_incumbent.gdx', wnx_bi=wnx;
if (wnx.l %gt% wnx_bi.l,
   put_utility 'log' / 'Job %userjobid% updated objective from ' wnx_bi.l:8:2 ' to ' wnx.l:8:2;
   put_utility 'exec' / 'mv -f bchout_i%userjobid%.gdx best_incumbent.gdx';
* update GAMS/Cplex option file cplex.op3 with a new cutoff value
   put_utility 'shell' / 'echo %cutoff% ' wnx.l:18:8 ' > cplex.op3';
* create the trigger files for the workers to read the new cutoff value
  for (cnt=1 to %nsub%+1,
     put_utility$(cnt<>%userjobid%) 'exec' / 'touch t' cnt '.trg'
  );
)
abort$unlock(%mtxID%) 'error unlocking mutex';
$offEcho