[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Building set of sets from plain set - efficient implemen
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Building set of sets from plain set - efficient implementation |
Date: |
Sat, 13 Dec 2008 08:31:51 +0300 |
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] Building set of sets from plain set, Andrew Makhorin, 2008/12/09
- Re: [Help-glpk] Building set of sets from plain set, Andrew Makhorin, 2008/12/09
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, xypron, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, xypron, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation,
Andrew Makhorin <=
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, glpk xypron, 2008/12/13
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/13
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/13