
From:  Yaron Kretchmer 
Subject:  Re: [Helpglpk] Parsing large, sparse mathprog model takes a (very) long time 
Date:  Mon, 2 May 2011 05:29:10 0700 
This is implementation defect, that is, the mathprog translator evaluates
> I have a mathprog model which takes a long time to parse:
> The model is of a settoset routing problem There is a bipartite
> graph, and the objective is to establish connections between the two
> parts such that a length metric is minimized.
> There are ~76K nodes in each "half" of the graph (for a total of ~150K
> nodes), and a total of 500K edges between the nodes.
>
> The model has been parsing (i.e. haven't reached presolving stage yet)
> for more than an hour now. Memory consumption is increasing, but thus
> far is quite low (<200M).
>
> Is this long parse time reasonable? Are there ways of rewriting which
> would speed up parsing?
>
> Since the model is quite large, I put it on
> http://foodproj.org/set_to_set_routing.zip
>
all expressions as they are coded performing no optimization. Thus, if
you write
s.t. every_to_pin_connected_to_one {t in toset} :
sum {f in fromset :(f,t) in connection } from_connects_to[f,t] == 1;
this statement is evaluated as follows:
for {t in toset}
{ for {f in fromset}
{ if {(f,t) in connection}
...evaluate constraint expressions...
}
}
and the total evaluation time is toset * fromset * log connection
= 75887 * 75887 * 20 = VERY LONG TIME (log is because the logarithmic
search is used in innermost if).
I changed your model to make it a bit more efficient (see Version A
below). However, generating it still takes much time.
Ideally, to decrease the evaluation time you need to use two arrays of
sets, say, conn1 and conn2 declared as follows:
set conn1{f in fromset}, within toset;
set conn2{t in toset}, within fromset;
This would allow you using a more efficient construction like follows:
s.t. every_to_pin_connected_to_one {t in toset} :
sum {f in conn2[t] } from_connects_to[f,t] == 1;
However, this requires changing the data section. To avoid changing the
data section you may use an undocumented feature of mathprog, which
allows you generating set data "on the fly" as if there were appropraite
data statements. Please see Version B below; it takes less than a minute
to generate the model.
Andrew Makhorin
Version A

/* set to set routing
Copyright Yaron Kretchmer address@hidden
*/
set fromset := {0..75887};
set toset := {0..75887};
set connection dimen 2 ;
param distance{(f,t) in connection } ;
var overall_distance;
var from_connects_to {f in fromset,t in toset : (f,t) in connection},
binary ;
/* Every "To" pin is connected" to exactly one "from" pin i.e. all "to"
pins are connected */
s.t. every_to_pin_connected_to_one {t in toset} :
sum {f in fromset :(f,t) in connection } from_connects_to[f,t] == 1;
/* Every "from" pin connected to at most one "to" pin i.e. some "from"
pins might be disconnected*/
s.t. every_from_pin_connected_to_one_or_zero {f in fromset} :
sum {t in toset :(f,t) in connection } from_connects_to[f,t] <= 1;
s.t. overall_distance_def : overall_distance = sum {(f,t) in
connection } from_connects_to[f,t]*distance[f,t];
minimize overall_distance2 : sum {(f,t) in connection}
from_connects_to[f,t];
data;
. . .
Version B

/* set to set routing
Copyright Yaron Kretchmer address@hidden
*/
set fromset := {0..75887};
set toset := {0..75887};
set connection dimen 2 ;
param distance{(f,t) in connection } ;
set conn1{f in fromset}, data connection(1,2), default {};
set conn2{t in toset}, data connection(2,1), default {};
/*display conn1, conn2;*/
var overall_distance;
var from_connects_to {(f,t) in connection}, binary ;
/* Every "To" pin is connected" to exactly one "from" pin i.e. all "to"
pins are connected */
s.t. every_to_pin_connected_to_one {t in toset} :
sum {f in conn2[t] } from_connects_to[f,t] == 1;
/* Every "from" pin connected to at most one "to" pin i.e. some "from"
pins might be disconnected*/
s.t. every_from_pin_connected_to_one_or_zero {f in fromset} :
sum {t in conn1[f] } from_connects_to[f,t] <= 1;
s.t. overall_distance_def :
overall_distance = sum {(f,t) in connection }
from_connects_to[f,t]*distance[f,t];
minimize overall_distance2 :
sum {(f,t) in connection} from_connects_to[f,t];
solve ;
for {(f,t) in connection :
distance[f,t]>0&& from_connects_to[f,t]>0/**/} {
printf " %s,%s %s %s > %s",
from_connects_to[f,t],f,t,distance[f,t];printf "\n";
}
data ;
. . .
[Prev in Thread]  Current Thread  [Next in Thread] 