User Tools

Site Tools


gams:efficient_processing_of_tuples

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.

 set  I  /i001 * i250/   rows ;
 set  J  /j000001 * j300000/  columns ;

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.

 set ij(i,j)
 /
 i007.j000001
 i052.j000001
 i146.j000001
 i239.j000001
 i003.j000002
 .
 .
 .
 i202.j300000
 i237.j300000
 / ;

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:

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;
gams/efficient_processing_of_tuples.txt · Last modified: 2007/09/27 02:46 (external edit)