I don't understand why all the copying goes on in mip.pyx, maybe Nathan can comment? I think the method would be much faster without deepcopy(). Just shallow copy stuff into new dicts. The coefficients of the linear functions are immutable, so its not a problem to have them linked multiple times.
There is a function Sum that one can import to speed things up. I've moved that into a method of MixedIntegerLinearProgram in my patch at http://trac.sagemath.org/13646 On Tuesday, October 23, 2012 2:42:18 PM UTC+1, Peter Mueller wrote: > > Sorry for bombing this list with my MIP problems. Here is another thing, > again in Sage 5.3: > > The following (senseless) test code > > P = MixedIntegerLinearProgram() > x = P.new_variable(binary=True) > for i in [0..29]: > c = sum(x[j]*(j-i) for j in [0..29]) > > takes about 1.6 seconds, even though there are only about 900 additions > and multiplications involved. Checking with %prun what goes wrong, I find > more than 50000 copies, deep copies and such which are responsible for this > long running time. > > Of course MIP variables are different from polynomial variables, but still > it might be worth to compare with the analogous and hence equally silly > code: > > R = PolynomialRing(QQ,"x",30) > for i in [0..29]: > c = sum(R.gen(j)*(j-i) for j in [0..29]) > > This takes just 0.023 seconds, and no kind of operation is executed more > than 930 times. > > Am I doing something wrong, or is the arithmetic with MIP variables > extremely inefficient? I came across this when I found out that the > bottleneck in a big problem was not solving the integer linear program, but > rather creating it! > > All the best, > Peter Mueller > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support?hl=en.
