[Help-glpk] Using a Virtual File System to produce data 'on-the-fly' for GLPK

[Nigel Galloway]

The attached file glpk_vfs.rb demonstrates using a Virtual File System to 
produce input files for GLPK without the files being physically present on 
disk. This approach has been used for frontending SQL databases and obtaing 
data from the internet. Of course at the moment I'm more interested in large 
numbers of random integers. 

Andrew, if you feel this technique is of interest you may of course add 
glpk_vfs.rb to the examples directory.

I want to compare the uniformity of glpk's random number generator with an 
external random number generator. I want 1.5 million externally generated 
random numbers but I don't want to store a file with 1.5 million numbers on 
disk. The following achieves this.

It require the ruby extension fusefs.rb, which of course requires ruby and 
FUSE. Most 2.6 kernals already include FUSE, if not or you want to use 2.4 it 
must be downloaded compiled and modprobed in.

A simple implementation of the virtual file system is attachd.

First mount the virtual file system using 1500000 random number to test:

address@hidden:~/myGLPK$ ruby glpk_vfs.rb glpk_vfs 1500000&
[1] 24590

Check that the virtual file system is mounted:

address@hidden:~/myGLPK$ mount
/dev/sda8 on / type ext3 (rw,relatime,errors=remount-ro)
proc on /proc type proc (rw,noexec,nosuid,nodev)
/sys on /sys type sysfs (rw,noexec,nosuid,nodev)
varrun on /var/run type tmpfs (rw,noexec,nosuid,nodev,mode=0755)
varlock on /var/lock type tmpfs (rw,noexec,nosuid,nodev,mode=1777)
udev on /dev type tmpfs (rw,mode=0755)
devshm on /dev/shm type tmpfs (rw)
devpts on /dev/pts type devpts (rw,gid=5,mode=620)
lrm on /lib/modules/2.6.24-16-generic/volatile type tmpfs (rw)
securityfs on /sys/kernel/security type securityfs (rw)
binfmt_misc on /proc/sys/fs/binfmt_misc type binfmt_misc 
(rw,noexec,nosuid,nodev)
gvfs-fuse-daemon on /home/nigel/.gvfs type fuse.gvfs-fuse-daemon 
(rw,nosuid,nodev,user=nigel)
/dev/fuse on /home/nigel/myGLPK/glpk_vfs type fuse (rw,nosuid,nodev,user=nigel)

The last line indicate that it is. Let's list the directory and mathprog file 
we have:

address@hidden:~/myGLPK$ ls glpk_vfs
randomtest.data  randomtest.mathprog
address@hidden:~/myGLPK$ cat glpk_vfs/randomtest.mathprog 
/*Arithmetic Mean of a large number of random Integers
   between 1 and 9 inclusive should be 5. The sum of each
   (random Integer - 5) should be 0, is it for glpk's psudo random generator?
  - or - another excuse to solve a very large constraint matrix
         over 1.75 million rows and columns with 2GB of memory.
  address@hidden
  July 18th., 2008.
*/

set Sample;
param RI {x in Sample},integer;
param Mean := 5;
var E {x in Sample},integer;

/* Mean + variance[n] = Sample[n] */
variances{z in Sample}: Mean + E[z] = RI[z];

solve;

printf "%d", sum{x in Sample} E[x];

data;

param:
Sample:   RI :=
  1       9
  2       8
  3       7
  4       6
  5       5
  6       4
  7       3
  8       2
  9       1
  ; 
end;
address@hidden:~/myGLPK$ 

Let's try with the test data in the mathprog file:

address@hidden:~/myGLPK$ /opt/glpk/bin/glpsol --math 
glpk_vfs/randomtest.mathprog 
Reading model section from glpk_vfs/randomtest.mathprog...
Reading data section from glpk_vfs/randomtest.mathprog...
36 lines were read
Generating variances...
Model has been successfully generated
glp_simplex: original LP has 9 rows, 9 columns, 9 non-zeros
Objective value = 0
OPTIMAL SOLUTION FOUND BY LP PRESOLVER
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
+     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (124933 bytes)
0
Model has been successfully processed
address@hidden:~/myGLPK$ 

Time to go for broke, the closer to zero the result, probably, the better:

address@hidden:~/myGLPK$ /opt/glpk/bin/glpsol --math 
glpk_vfs/randomtest.mathprog --data glpk_vfs/randomtest.data
Reading model section from glpk_vfs/randomtest.mathprog...
glpk_vfs/randomtest.mathprog:22: warning: data section ignored
22 lines were read
Reading data section from glpk_vfs/randomtest.data...
1500005 lines were read
Generating variances...
Model has been successfully generated
glp_simplex: original LP has 1500000 rows, 1500000 columns, 1500000 non-zeros
Objective value = 0
OPTIMAL SOLUTION FOUND BY LP PRESOLVER
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
+     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   6.1 secs
Memory used: 2148.1 Mb (2252399336 bytes)
-1241
Model has been successfully processed

and again? why not?

address@hidden:~/myGLPK$ /opt/glpk/bin/glpsol --math 
glpk_vfs/randomtest.mathprog --data glpk_vfs/randomtest.data
Reading model section from glpk_vfs/randomtest.mathprog...
glpk_vfs/randomtest.mathprog:22: warning: data section ignored
22 lines were read
Reading data section from glpk_vfs/randomtest.data...
1500005 lines were read
Generating variances...
Model has been successfully generated
glp_simplex: original LP has 1500000 rows, 1500000 columns, 1500000 non-zeros
Objective value = 0
OPTIMAL SOLUTION FOUND BY LP PRESOLVER
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
+     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   5.9 secs
Memory used: 2148.1 Mb (2252399336 bytes)
222
Model has been successfully processed
address@hidden:~/myGLPK$ 

Using random numbers generated by glpk:

address@hidden:~/myGLPK$ /opt/glpk/bin/glpsol --math randomtest.mathprog
Reading model section from randomtest.mathprog...
22 lines were read
Generating variances...
Model has been successfully generated
glp_simplex: original LP has 1500000 rows, 1500000 columns, 1500000 non-zeros
Objective value = 0
OPTIMAL SOLUTION FOUND BY LP PRESOLVER
Integer optimization begins...
+     0: mip =     not found yet >=              -inf        (1; 0)
+     0: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (1; 0)
+     0: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   5.4 secs
Memory used: 1825.8 Mb (1914476223 bytes)
-4730
Model has been successfully processed
address@hidden:~/myGLPK$ 





-- 
_______________________________________________
Surf the Web in a faster, safer and easier way:
Download Opera 9 at http://www.opera.com

Powered by Outblaze

glpk_vfs.rb
Description: Binary data

randomtest.mathprog
Description: Binary data