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;
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
