While analyzing why a program becomes unexpectedly slow (despite moderate
memory usage and no swapping), I found out that the time consumption of the
method add_constraint slows down if there are already many constraints.
The following simple (and silly) program displays this:
P = MixedIntegerLinearProgram(solver="Coin", maximization=False)
x = P.new_variable(real=True)
z = 0
t1 = cputime()
while True:
P.add_constraint(x[0] + random()*x[1], max = random())
z += 1
if z%10000 == 0:
t2 = cputime()
print z, t2-t1
t1 = t2
10000 0.860054
20000 1.528095
30000 2.23214
40000 3.788236
50000 4.580286
60000 7.488468
70000 15.997
80000 23.297456
90000 31.489968
100000 37.614351
110000 43.946747
120000 47.818988
So we see that adding the first 10000 constraints takes 0.86 seconds, while
adding 10000 constraints when there are already 110000 constraints takes
47.82 seconds, and things keep worsening.
Is this an implementation problem of the method add_constraint, or
something which cannot really be avoided? Considering that the available
powerful backends can solve huge systems, it would be a pity if actually
creating the linear program would be the bottleneck.
-- Peter Mueller (Wuerzburg)
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
