[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] manipulating parameter indices

From: Kevin Hunter
Subject: Re: [Help-glpk] manipulating parameter indices
Date: Wed, 04 Jul 2012 15:32:51 -0400
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1

At 10:03am -0400 Wed, 04 Jul 2012, Andrew Makhorin wrote:
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

Ah, I see.  So how about a compound situation like below?

  # i.e. a generated set.  Does this get created once and then used as
  # a "first class" set?  Or does the "such that" operator get
  # evaluated for every use if setABC?
set setABC := {a in setA, b in setB, c in setC : a + b = c };

set setABCD := {(a, b, c) in setABC, d in setD : a + c = d };

s.t. C1 {(a, b, c) in setABC} :
 VarX[a, b, c] <=  sum{(a, b, c, d) in setABCD} ParamX[a, b, c, d];

s.t. C2 {(a, b, c) in setABC} :
 VarX[a, b, c] >= -sum{(a, b, c, d) in setABCD} ParamY[a, b, c, d];

So, when executing the s.t. line of C1, if setABC has not yet been used, does it get "instantiated" before C1 gets to use it, or is the code '(a, b, c) in setABC' effectively now an alias for:

{a in setA, b in setB, c in setC : a * c > 10}

such that it's use in the C2 constraint does not get the benefit of the cached result?

In a similar vein, is there a more efficient method to sum over common indices? In other words, the fact that a, b, and c are already set in the loop for '(a, b, c, d) in setABCD'? As I understand the pseudo-code above, those lines translate to something like

   s := 0
   for all (da, db, dc, d) in setABCD do {   # da = "dummy a"
      if a == da and b == db and c == dc then
         s := s + ParamX[a, b, c, d]

If this is case, would it behoove to me create my own specific cache subsets, like

  # return sets of (a,b,c) that return d in setABCD
set D_ABC{(a, b, c) in setABC} := setof{(a,b,c,d) in setABCD} d;

And then use as:

s.t. C1 {(a, b, c) in setABC} :
 VarX[a, b, c] <=  sum{d in setD_ABC[a, b, c]} ParamX[a, b, c, d];

Many thanks for your input, Andrew!


reply via email to

[Prev in Thread] Current Thread [Next in Thread]