Sage: Ticket #7740: Speed up MixedIntegerLinearProgram
https://trac.sagemath.org/ticket/7740
<p>
From Robert Miller :
</p>
<pre class="wiki">sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.CirculantGraph(120, [2,3,5,7])
sage: vertex_coloring(g)
</pre><p>
It takes longer to set up the constraint than to solve the problem, on my laptop.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7740
Trac 1.1.6ncohenSat, 19 Dec 2009 08:44:07 GMTsummary changed
https://trac.sagemath.org/ticket/7740#comment:1
https://trac.sagemath.org/ticket/7740#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>Spped up MixedIntegerLinearProgram</em> to <em>Speed up MixedIntegerLinearProgram</em>
</li>
</ul>
TicketncohenSun, 20 Dec 2009 17:33:35 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:2
https://trac.sagemath.org/ticket/7740#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
</ul>
<p>
Well, this time is spent as expected on the add_constraint function, which may spend time over considerations coming from symbolic computations, though I did not achieve to know where... When I am profiling your example I see :
</p>
<pre class="wiki">
25448/21366 0.529 0.000 0.695 0.000 complex_interval_field.py:257(__call__)
8642 0.427 0.000 1.136 0.000 complex_interval_field.py:330(random_element)
8642 0.106 0.000 0.117 0.000 complex_interval_field.py:325(gen)
</pre><p>
These functions are the ones responsible for the time spent defining the LP, but I could not find which line of add_constraint is calling them... If you have any idea, please tell me and I'll give it a look :-)
</p>
TicketncohenSat, 26 Dec 2009 12:21:17 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:3
https://trac.sagemath.org/ticket/7740#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
This patch adds to the file numerical.mip a class <a class="missing wiki">LinearFunction?</a> which avoid using the much more general symbolic expressions from Sage ( as we only need to define linear functions ).
</p>
<p>
Before :
</p>
<pre class="wiki">sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.CirculantGraph(120, [2,3,5,7])
sage: timeit("vertex_coloring(g)")
5 loops, best of 3: 3.94 s per loop
</pre><p>
After :
</p>
<pre class="wiki">sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.CirculantGraph(120, [2,3,5,7])
sage: timeit("vertex_coloring(g)")
5 loops, best of 3: 2.18 s per loop
</pre><p>
The next way to speed up this class would be, methinks, to cythonize it. I tried it this time but got stuck by the fact that the solving functions ( solveCoin, solveGlpk ) are not directly included in Sage and installed by the packages... The best way would really be to move these sources into Sage. It would also solve solve the problem of having to update both packages and numerical.mip t the same time .. :-/
</p>
<p>
Nathann
</p>
TicketncohenMon, 28 Dec 2009 08:45:38 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:4
https://trac.sagemath.org/ticket/7740#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketncohenMon, 28 Dec 2009 11:49:52 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:5
https://trac.sagemath.org/ticket/7740#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Before :
</p>
<pre class="wiki">sage: g = graphs.WorldMap()
sage: %timeit g.edge_connectivity()
10 loops, best of 3: 1.29 s per loop
</pre><p>
After :
</p>
<pre class="wiki">sage: g = graphs.WorldMap()
sage: %timeit g.edge_connectivity()
10 loops, best of 3: 231 ms per loop
</pre><p>
But as mentionned earlier, we will have to find other ways to improve this class ! :-)
</p>
<p>
Nathann
</p>
TicketrlmWed, 06 Jan 2010 16:17:01 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:6
https://trac.sagemath.org/ticket/7740#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Looks good to me! Aside from this typo:
"An elementary algebra algebra"
</p>
TicketncohenSat, 09 Jan 2010 08:16:31 GMTattachment set
https://trac.sagemath.org/ticket/7740
https://trac.sagemath.org/ticket/7740
<ul>
<li><strong>attachment</strong>
set to <em>trac_7740.patch</em>
</li>
</ul>
TicketncohenSat, 09 Jan 2010 08:16:44 GMTstatus changed
https://trac.sagemath.org/ticket/7740#comment:7
https://trac.sagemath.org/ticket/7740#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Here it is ! :-)
</p>
TicketrlmWed, 13 Jan 2010 11:39:54 GMTstatus changed; reviewer, resolution, merged, author set
https://trac.sagemath.org/ticket/7740#comment:8
https://trac.sagemath.org/ticket/7740#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>4.3.1.alpha2</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
positive review
</p>
TicketncohenWed, 13 Jan 2010 11:41:03 GMT
https://trac.sagemath.org/ticket/7740#comment:9
https://trac.sagemath.org/ticket/7740#comment:9
<p>
Thank you again !!! I was longing for this one :-)
</p>
<p>
Nathann
</p>
TicketmvnguWed, 13 Jan 2010 19:47:41 GMTmerged changed
https://trac.sagemath.org/ticket/7740#comment:10
https://trac.sagemath.org/ticket/7740#comment:10
<ul>
<li><strong>merged</strong>
changed from <em>4.3.1.alpha2</em> to <em>sage-4.3.1.alpha2</em>
</li>
</ul>
TicketnthieryThu, 14 Jan 2010 14:38:10 GMT
https://trac.sagemath.org/ticket/7740#comment:11
https://trac.sagemath.org/ticket/7740#comment:11
<p>
Hi Nathan,
</p>
<p>
Sorry to pop up late into the discussion. What was the rationale for not using <a class="missing wiki">CombinatorialFreeModule?</a>(whatever_ring, ZZ)?
</p>
<p>
For the record, I very much hope that <a class="missing wiki">FreeModule?</a>(ring, infinity, sparse = True) will be available sometime soon. That will be a faster alternative.
</p>
TicketncohenThu, 14 Jan 2010 14:48:31 GMT
https://trac.sagemath.org/ticket/7740#comment:12
https://trac.sagemath.org/ticket/7740#comment:12
<p>
Hello !
</p>
<p>
At first I used <a class="missing wiki">InfinitePolynomialRing?</a>, then plain "vars", then I just wondered why it was still very slow and just wondered what it would give if I were to write the symbolics myself to understand... As it was easy enough, I wrote something to try it on my computer, and ended up writing a patch to send the code.
</p>
<p>
This way, it stores the informations in a format that is optimal for what I need ( no powers --only linear functions--, sparse from the beginning, ... ). Since, I have also noticed that having my own symbolics would let me define expressions like double inequalities :
</p>
<p>
0 < a + b < 9
</p>
<p>
Which I had been missing for a long time.. :-)
The main problem I have is that in many cases, the symbolics take most of the time spent on the computation of a matching (or other LP problems), which is quite disturbing ;-)
</p>
<p>
Nathann
</p>
Ticket