Sunday, July 21, 2013

Speeding up SMAX

The following GAMS code was very slow:

ACCRLRLY(B,BA,Y,U)$SUM((H,T,UR), XSB7(B,BA,"NP",H,Y,T,U,UR))
                             = ACRLRLY(BA,Y, U) *
SMAX((H,T,UR), XSB7(B,BA,"NP"
,H,Y,T,U,UR));

Note that the $ condition on the left is correct: it makes sure we don’t take the SMAX of an empty set. This is really needed as SMAX over an empty set is unreliable (see:http://yetanothermathprogrammingconsultant.blogspot.com/2008/05/gams-smin-bug.html).

However the SMAX will not skip zeros like a SUM, making this operation very slow. A possible fix is:

ACCRLRLY(B,BA,Y,U)$SUM((H,T,UR), XSB7(B,BA,"NP",H,Y,T,U,UR))
    = ACRLRLY(BA,Y, U) *
SMAX((H,T,UR)$XSB7(B,BA,"NP",H,Y,T,U,UR), XSB7(B,BA,"NP"
,H,Y,T,U,UR));

The difference in timing is very large:

Original 75 seconds
New version 0.9 seconds

This only works if it is safe to skip zeros. I.e. if there are positive elements in each smax. We can check for this e.g. by using an abort$(cond) statement.

No comments:

Post a Comment