Re: [Help-glpk] manipulating parameter indices

[Andrew Makhorin]

> > For a fairly small input data file (18k rows, 16k cols, 94k nz), the
> > GMPL avenue takes about 40 seconds to generate and solve on my
> > machine, while Pyomo takes about 11 seconds to generate and solve,
> > /including/ using GLPK as the solver. (This is a stable average of
> > ~10 runs.)
> 
> > Is there common wisdom on what I might be doing wrong?  If I had to
> > guess, I'd suspect I'm hitting some O(n) wall in regards to GMPL's
> > just-in-time instantiation of derived set and parameter elements.
> 
> > http://cygnus.ce.ncsu.edu/~kevin/tmp/model.zip

In the mathprog translator sparse arrays are implemented not as
efficiently as in python.

> 
> Alright, I gather speed of execution is not a thrilling topic to dive 
> into ... Are there known or common routes for diagnosing GMPL model 
> manipulations?  i.e. profiling of some sort?  I can tell by the GMPL 
> output which of my constraints are taking the longest to build, but 
> looking at the indices, it doesn't immediately strike me as to why.

In the current mathprog implementation no query optimization is
performed, that is, all intermediate and resulting objects are evaluated
literally as specified by corresponding expressions. (This is exactly
the same problem that appears in the relational database systems.) 
For example,

   param foo{i in I} := sum{j in J: (i,j) in E} x[i,j];

will be evaluated as follows:

   for all i in I do
   {  s := 0;
      for all j in J do
      {  if (i,j) in E then
            s := s + x[i,j]
      }
      foo[i] := s
   }

that will take the time |I|*|J|*log|E|, though the following plan would
be much more efficient in the case of sparse E (assuming that E is a
subset of IxJ):

   for all i in I do
      foo[i] := 0;
   for all (i,j) in E do
      foo[i] := foo[i] + x[i,j];      

> 
> After interspersing some fprintf calls into the GLPK codebase, my first 
> constraint, over a sparse, 5-dimensional set of 690 items, generates 
> 2.49 million calls to expand_tuple in glpmpl03.c.  Does that sound right?
> 

Perhaps, yes.