New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Speed up MixedIntegerLinearProgram #7740
Comments
comment:2
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 :
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 :-) |
comment:3
This patch adds to the file numerical.mip a class LinearFunction which avoid using the much more general symbolic expressions from Sage ( as we only need to define linear functions ). Before :
After :
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 .. :-/ Nathann |
comment:5
Before :
After :
But as mentionned earlier, we will have to find other ways to improve this class ! :-) Nathann |
comment:6
Looks good to me! Aside from this typo: |
Attachment: trac_7740.patch.gz |
comment:7
Here it is ! :-) |
Author: Nathann Cohen |
Merged: 4.3.1.alpha2 |
comment:8
positive review |
Reviewer: Robert Miller |
comment:9
Thank you again !!! I was longing for this one :-) Nathann |
Changed merged from 4.3.1.alpha2 to sage-4.3.1.alpha2 |
comment:11
Hi Nathan, Sorry to pop up late into the discussion. What was the rationale for not using CombinatorialFreeModule(whatever_ring, ZZ)? For the record, I very much hope that FreeModule(ring, infinity, sparse = True) will be available sometime soon. That will be a faster alternative. |
comment:12
Hello ! At first I used InfinitePolynomialRing, 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. 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 : 0 < a + b < 9 Which I had been missing for a long time.. :-) Nathann |
From Robert Miller :
It takes longer to set up the constraint than to solve the problem, on my laptop.
CC: @rlmill
Component: numerical
Author: Nathann Cohen
Reviewer: Robert Miller
Merged: sage-4.3.1.alpha2
Issue created by migration from https://trac.sagemath.org/ticket/7740
The text was updated successfully, but these errors were encountered: