MIP variables arithmetic very slow?

[Peter Mueller]

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

[Volker Braun]

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

[Volker Braun]

Profiling info:

sage: P = MixedIntegerLinearProgram()

sage: x = P.new_variable(binary=True)

sage: %prun for i in [0..29]: c = sum(x[j]*(j-i) for j in [0..29])

         608747 function calls (554747 primitive calls) in 0.430 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

54900/900    0.136    0.000    0.406    0.000 copy.py:145(deepcopy)

    26100    0.056    0.000    0.056    0.000 {getattr}

    13050    0.053    0.000    0.105    0.000 copy.py:234(_deepcopy_tuple)

    54030    0.036    0.000    0.046    0.000 copy.py:267(_keep_alive)

    13050    0.033    0.000    0.200    0.000 copy.py:306(_reconstruct)

    13050    0.019    0.000    0.019    0.000 {method '__reduce_ex__' of 'object' objects}

   121980    0.017    0.000    0.017    0.000 {method 'get' of 'dict' objects}

      900    0.013    0.000    0.403    0.000 copy.py:253(_deepcopy_dict)

   136830    0.010    0.000    0.010    0.000 {id}

       30    0.010    0.000    0.425    0.014 {sum}

[...]

sage: %prun for i in [0..29]: c = P.sum(x[j]*(j-i) for j in [0..29])

         2357 function calls in 0.024 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)

      930    0.017    0.000    0.017    0.000 <string>:1(<genexpr>)

       30    0.003    0.000    0.020    0.001 {method 'sum' of 'sage.numerical.mip.MixedIntegerLinearProgram' objects}

       62    0.002    0.000    0.002    0.000 sequence.py:86(Sequence)

       31    0.001    0.000    0.004    0.000 misc.py:1319(ellipsis_range)

       31    0.001    0.000    0.002    0.000 misc.py:1051(srange)

       62    0.000    0.000    0.000    0.000 sequence.py:463(__init__)

      372    0.000    0.000    0.000    0.000 {isinstance}

        1    0.000    0.000    0.024    0.024 <string>:1(<module>)

       31    0.000    0.000    0.000    0.000 {method 'range' of 'sage.rings.integer_ring.IntegerRing_class' objects}

       62    0.000    0.000    0.000    0.000 {sage.structure.element.canonical_coercion}

       93    0.000    0.000    0.000    0.000 {range}

       62    0.000    0.000    0.000    0.000 quotient_ring.py:257(is_QuotientRing)

      310    0.000    0.000    0.000    0.000 {len}

       62    0.000    0.000    0.000    0.000 sequence.py:780(universe)

       62    0.000    0.000    0.000    0.000 {sage.rings.polynomial.multi_polynomial_ring_generic.is_MPolynomialRing}

       31    0.000    0.000    0.000    0.000 {method 'index' of 'list' objects}

       31    0.000    0.000    0.000    0.000 {method 'pop' of 'list' objects}

       62    0.000    0.000    0.000    0.000 {sage.structure.element.parent}

       31    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}

        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

[Peter Mueller]

Dear Volker,

importing Sum from sage.numerical.mip and replacing all occurrences of sum with Sum fixed the problem of the long running times, thanks a lot!

Such important information should be in the docs, a naive user like I am never would have found that out!

All the best

Peter Mueller

[Volker Braun]

On Tuesday, October 23, 2012 3:45:56 PM UTC+1, Peter Mueller wrote:

importing Sum from sage.numerical.mip and replacing all occurrences of sum with Sum fixed the problem of the long running times, thanks a lot

Such important information should be in the docs, a naive user like I am never would have found that out

Well ideally addition wouldn't be glacially slow to start with ;)