Re: [Help-glpk] Building set of sets from plain set - efficient implementation

[Andrew Makhorin]

Hi Xypron,

> three different types of definitions could occur:

> 1) Multiline forward definition:
> e.g.
> set T{a in A}:= B[a];
> set B{a in A};
> Forward definition is not allowed in GLPK.

This is not needed until you use a recursive definition like follows:

set T{a in A} := ...something that depends on B[a]...
set B{a in A} := ...something that depends on T[a]...

However, such recursive definition may be modeled as follows:

set S{a in A, case in 1..2} :=
   if case = 1 then
      ...something that depends on S[a,2]...
   else
      ...something that depends on S[a,1]...

where S[a,1] means T[a] and S[a,2] means B[a].

> 2) Single line recursive definition
> e.g.
> set T{a in A} := if {a == min{b in A}b } then {a} else {a} union T[a-1];

Such definitions are allowed.

> In this case the elements of T have to be initialized one by one. Your
> algorithm is necessary:
>>> procedure T(k in K, i in I)
>>> {   find T[k,i] in T array;
>>>     if T[k,i] is not found then
>>>     {  T[k,i] := setof{(i,j,k,l,m) in S} (j,m,l);
>>>        add T[k,i] to T array;
>>>     }
>>>     return T[k,i];
>>> }

Yes, procedure T will call itself recursively.

> 3) No recursion, only backward definitions
> e.g.
> set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l); 

> In this case the whole set T can be initialized at once when the first
> element of T is requested as I proposed.

Sometimes this is undesired. For example, you may write:

set T{k in 1..1000000} := ... ;

and then use, say, only T[3] and T[5]. In Mathprog subscripted sets
and parameters are more like procedures rather than arrays.

> Essentially this is what you describe as:
>>> My idea is to use S to create fake data ...

> Still I do not see any need for as special syntax. When parsing a set
> statement you could flag it as recursive or not.

>>> Do you know if there is a similar operation in the sql language?
> As SQL is not object oriented the result set of a query is always a flat
> table.

Sorry for inexactness. I meant operations used in the relational
algebra like left outer join, projection, etc.


Andrew Makhorin