User Tools

Site Tools


gams:efficient_processing_of_tuples

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

gams:efficient_processing_of_tuples [2007/09/27 04:46] (current)
Line 1: Line 1:
 +====== Efficient processing of tuples ======
 +Q: // The essence of our problem is very simple, but size matters. ​ Call it a set covering model, and say it has only 250 rows but 300,000 columns. There are from 1 to 9 nonzero entries (ones) per column, with let's say
 +an average of 6 per column.
  
 +It takes a delightfully short time to solve this cover model but an annoyingly long time to generate it.  Here are the parts that matter for addressing my question. //
 +<​code>​
 + ​set ​ I  /i001 * i250/   rows ;
 + ​set ​ J  /j000001 * j300000/ ​ columns ;
 +</​code>​
 +No kidding. ​ These are the dimensions. ​ The row count can't grow too  much, but if we get aggressive, the column count can grow.  A lot.
 +<​code>​
 + set ij(i,j)
 + /
 + ​i007.j000001
 + ​i052.j000001
 + ​i146.j000001
 + ​i239.j000001
 + ​i003.j000002
 + .
 + .
 + .
 + ​i202.j300000
 + ​i237.j300000
 + / ;
 +</​code>​
 +//These tuples, all 1.8 million (= 300,000 * 6) of them, are generated ​ outside of GAMS and put into an include file.  The tuples are ordered ​ with index i varying faster than j. (I used to remember whether this is  called row-major order or column-major order but you know what I mean.)
 + All the time is taken up domain-checking set ij and generating equation ​ cover.
 +
 +QUESTION: If we want GAMS to generate the model faster, is there a better way to order the indices i and j, to order the tuples ij, or to  write the cover equations?//​
 +
 +
 +This solution below uses the UNIX utility awk to reverse the indices of the input file, let GAMS read the include file (so we catch duplicated, domain violation and other errors in the usual way) and then uses the "​option <" statement to do the reversing in GAMS. We ship a couple of UNIX utilities for the GAMS Windows system including awk since 20.6, so you don't need to download anything with this solution. But there are also some drawbacks to this solution: You still need a recent version of GAMS (>=21.3) for the "​option <" operation. Moreover, the call of the awk utility is
 +somewhat cryptic (that'​s why it's called awk :). Anyway, here is the piece of code that would do the trick:
 +<​code>​
 +Set i /i1*i237/, j /​j1*j300000/,​
 +    ij(i,j), ji(j,i) /
 +$offlisting
 +$call awk -F. -vOFS=. "​{print $2,​$1}"​ ij.txt > ji.txt
 +$include ji.txt
 +$onlisting
 +/;
 +option ij<ji;
 +* Free the memory for ji
 +option kill=ji;
 +</​code>​
IMPRESSUM / LEGAL NOTICEPRIVACY POLICY gams/efficient_processing_of_tuples.txt ยท Last modified: 2007/09/27 04:46 (external edit)