Sunday, June 15, 2008

Rolling horizon implementation in GAMS

A rolling horizon algorithm can be used to speed up finding a good integer solution. Instead of solving the model for all time periods at once we split the horizon into slices. To mitigate end-of-horizon effects, we can overlap the slices. Here is a picture of a power planning model:




(click to enlarge). Instead of solving for all periods at once we solve here in 5 steps. In each step the green part indicates binary variables are relaxed (continuous between zero and one). The yellow part indicates integer variables that are being solved for. The blue part indicates integer variables fixed to their previously found solution. Optionally we can try to improve the solution using a complete model (this is the grey part in the picture).

The GAMS code to implement this can look like:



sets
subiter 'rolling horizon iteration' /iter1*iter5/
relaxed(subiter,yr) /
iter1.(2018*2037)
iter2.(2023*2037)
iter3.(2028*2037)
iter4.(2033*2037)
/
fixed(subiter,yr) /
iter2.(2007*2012)
iter3.(2007*2017)
iter4.(2007*2022)
iter5.(2007*2027)
/
;

* Solve GEM:
gem.optfile=1;
gem.reslim=1000;
gem.optcr=0;
gem.optca=0;
loop(subiter,
GENBLDINT.prior(s,yr) = 1;
loop(relaxed(subiter,yr),
GENBLDINT.prior(s,yr) = INF;
);
loop(fixed(subiter,yr),
GENBLDINT.fx(s,yr) = GENBLDINT.L(s,yr);
);
SOLVE GEM USING MIP MINIMIZING TOTALCOST ;
gem.optfile=2;
);
gem.optfile=3;
gem.reslim=10000;
GENBLDINT.prior(s,yr) = 1;
GENBLDINT.lo(s,yr) = 0;
GENBLDINT.up(s,yr) = 1;
SOLVE GEM USING MIP MINIMIZING TOTALCOST ;


Here we use the trick that X.PRIOR=INF means that X is relaxed. The final model uses the Cplex MIPSTART option to branch towards the solution found by the rolling horizon algorithm.