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

[Andrew Makhorin]

I have implemented and included this operation (building array of
sets from plain set) in Mathprog. It will appear in the next release
of the package (though probably the syntax should be improved).

Running the example model shown below for different m and n
demonstrates the following times needed to generate the model:

  m      n     nz(A)   Time1    Time2
1000   2000    19906    11 s    < 1 s
2000   3000    39887    42 s    < 1 s
3000   5000    59893    92 s      1 s
4000   7000    79895   165 s      1 s

where Time1 corresponds to an inefficient version not using an
auxiliary array of sets, and Time2 corresponds to an efficient
version of the model. (It is funny that, for example, for m = 4000
and n = 7000 the solution time is about 3 s.)

Andrew Makhorin

------------------------------------------------------------------------
/* test.mod */

param m := 4000;

param n := 7000;

set A := setof{i in 1..m, 1..20} (i, 1 + floor(Uniform(0,n)));

display card(A);

param a{(i,j) in A} := Uniform(0, 60);

param b{1..m} := if Uniform(0, 1) <= 0.87 then Uniform(10, 70000);

param c{1..n} := if Uniform(0, 1) <= 0.87 then Uniform(0, 9);

var x{1..n}, >= 0;

display gmtime();

# the following statement saturates R with data from A; it is
# equivalent to: set R{i in 1..m} := setof{(i,j) in A} j;
set R{1..m}, data A(1,2);

# inefficient version: O(m * nz(A))
# s.t. r{i in 1..m}: sum{(i,j) in A} a[i,j] * x[j] <= b[i];

# efficient version: O(nz(A))
s.t. r{i in 1..m}: sum{j in R[i]} a[i,j] * x[j] <= b[i];

display gmtime();

maximize z: sum{j in 1..n} c[j] * x[j];

end;