Re: Fwd: Re: [Help-glpk] Mathprog question

[Andrew Makhorin]

Hi Xypron,

> currently in GMPL there is no way to retrieve an element of a
> symbolic set by a logical condition. In the example below
> I am able to sort the values x{I}, but I am unable to 
> output the indices sorted by the values.

> One way to add such a functionality would be functions
> Max{ domain } tuple
> Min{ domain } tuple

> Then I could write
> param a, symbolic := Max{ i in I : x[i] = 3 } i;
> to retrieve a special element of a set.

Probably you mean something like argmax{(i,j,k) in IJK} x[i,j,k]
which should return some tuple (i,j,k), don't you?

The problem is that the glpk mathprog implementation is quite
naive. The translator performs evaluation of model objects exactly
in the same way as written. For example, the statement:

s.t. y{i in I} := sum{(i,j) in S: a[i,j] >= 0} a[i,j] * x[j];

is evaluated as follows:

for i in I do
{  y[i] := 0;
   for (i,j) in S do
   {  if a[i,j] >= 0 then
         y[i] := y[i] + a[i,j] * x[j];
   }
}

that needs to scan entire S in the innermost loop. If S is large
and sparse, it'd be much more efficient to evaluate as follows:

for i in I do
   y[i] := 0;
for (i,j) in S do
{  if a[i,j] >= 0 then
      y[i] := y[i] + a[i,j] * x[j];
}

However, in the current implementation it is impossible to
optimize the bytecode by changing the order of operations, creating
some additional indices for indexed objects, etc.

> Or the following restricition could be removed:
> "implementation restriction; in/within setof{} not allowed".

This would require evaluation of setof{} every time the condition
is checked. It is impossible to implement this efficiently.


Andrew Makhorin