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

[Meketon, Marc]

 This "data " statement seems very useful.  Could you please provide a couple 
of paragraphs on how the "data" statement works?

Also, is there any need to use the "binary" modifier?  Using the simplex 
algorithm on a network flow problem (which this is) guarantees integrality.

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Monday, May 02, 2011 5:40 AM
To: Yaron Kretchmer
Cc: address@hidden
Subject: Re: [Help-glpk] Parsing large, sparse mathprog model takes a (very) 
long time


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


_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

This e-mail and any attachments may be confidential or legally privileged. If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 
Thank you for your cooperation.