[Help-glpk] Re: slow matrix generation compared to AMPL

[Andrew Makhorin]

Consider the following declaration:

#Flow in + Adds = Flow Out + Deletes
subject to BALANCE {(i,j,k,c) in LTDC: j <> EndInterval and c = 'SO'}:
        sum{(i,j,k,l,m,n,c) in LOADMOVES}LOAD[i,j,k,l,m,n,c] +
   sum{(i,j,k,l,m,n,c) in EMPTYMOVES}EMPTY[i,j,k,l,m,n,c] +
   DeleteCapacity[i,j,k,c] =
        sum{(l,m,n,i,j,k,c) in LOADMOVES}LOAD[l,m,n,i,j,k,c] +
   sum{(l,m,n,i,j,k,c) in EMPTYMOVES}EMPTY[l,m,n,i,j,k,c] +
   AddCapacity[i,j,k,c];

As I explained before the MathProg translator performs all calculations
in a straightforward way using no optimization. Thus, BALANCE is
generated as follows:

for (i,j,k,c) in LTDC do
{  s := 0;
   ...
   for (i',j',k',l,m,n,c') in EMPTYMOVES do
      if i' == i and j' == j and k' == k and c' == c then
         s := s + EMPTY[i,j,k,l,m,n,c];
   ...
}

You say that card(LTDC) = 107,991 and card(EMPTYMOVES) = 527,993; thus,
the innermost 'if' is executed 107,991 * 527,993 = 57,018,492,063 times.
You also say that the translation time is about 24 hours. Let all this
time be spent on executing the 'if': 24 hrs = 86,400 secs, so the
translator executes 57,018,492,063 / 86,400 = 659,936 'ifs' per second.
Although the actual speed is several times higher, it seems to be
very realistic that explains why the translation takes such long time.

I don't know exactly how the AMPL system manages to take only several
minutes, but it is understood that it performs some optimization before
generating BALANCE. The problem is similar to that one which arises in
optimizing queries in relational databases. For example, if EMPTYMOVES
and BALANCE were declared as follows:

set EMPTYMOVES{(i,j,k,c) in LTDC} within {(l,m,n) in ...};

subject to BALANCE {(i,j,k,c) in LTDC: j <> EndInterval and c = 'SO'}:
   ...
      sum{(l,m,n) in EMPTYMOVES[i,j,k,c]}EMPTY[i,j,k,l,m,n,c] +
   ... ;

the sum operator would be executed by the MathProg translator much more
efficiently (but this would require much more memory to store 107,991
search trees for each elemental set which EMPTYMOVES consists of).

Probably the MathProg translator in its current implementation is not
suitable for processing such huge models like yours.

Andrew Makhorin