Re: [Help-glpk] Parsing large, sparse mathprog model takes a (very) long time

[Andrew Makhorin]

> 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 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 ;
. . .