Hi Andrew This works very well. The parsing time drops from 6 hours to 25 seconds.
Thanks a lot! Yaron On Mon, May 2, 2011 at 2:40 AM, Andrew Makhorin <[email protected]> wrote: > > > I have a mathprog model which takes a long time to parse: > > The model is of a set-to-set 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 > > > > This is implementation defect, that is, the mathprog translator evaluates > 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 [email protected] > > */ > > 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 [email protected] > > */ > > 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 ; > . . . > >
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
