[Bug-glpk] Re: generating LP from mathprog models

[Andrew Makhorin]

>I ran a test for reading a very simple LP model in the new mathprog language 
>that looks like:
>"""
>set t := 1..T;
>var x{time};
>minimize y:
>        sum { t in time } x[t];
>data;
>end;
>"""
>where I replaced T by different values and noticed an increase in generation 
>time which looks exponential in T:

>Is it a "bug" ?
>Is there a solution for avoiding this increase in time ?

Sebastien, thanks very much for your report! This is not a bug, however,
you have detected an essential defect in the implementation.

Explanation of the phenomenon is the following. On evaluating the sum
of two linear forms the standard technique is used, namely, non-zero
terms of the first operand are copied in the dense array, then non-zero
terms of the second operand are added, and then resulting non-zero terms
are fetched from the array. Such implementation allows reducing
identical terms and provides complexity O(nz1+nz2), where nz1 and nz2
are numbers of non-zero terms in the first and second linear forms, resp.
In your example the sum is computed as follows

   s := 0;
   for t in time do s := s + x[t];

where s is a partially evaluated linear form, i.e. in order to add next
term x[t] all previously evaluated terms of s should be processed, due
to that complexity of the iterated summation in your example is O(nz*nz)!
Although not exponential, but quadratic, that is not much better if
the linear form has thousands of terms.

To eliminate this defect reducing identical terms must be performed
only once after the entire linear form for constraint/objective has been
evaluated. This allows improving complexity to theoretical minimum
O(nz*log(nz)) (log appears due to binary search used for subscripted
objects), i.e. the time would be the same as if x were a parameter,
not a variable (I tried that: for T = 20000 the time was less than a
second). I hope to make necessary changes in the next release of glpk.

Andrew Makhorin