#9911: Changing the LP formulation of feedback vertex/arc set to improve the
speed
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.6
Component: graph theory | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
Old description:
> A friend of mine had the good idea to think about the MFAS problem one
> evening, and told me that the LP formulation given in GLPK's examples was
> able to return the optimal value of a particular problem in 8ms. It took
> more (I did not wait) than 2 minutes for Sage.
>
> I looked at the two formulations, and they were so clode that I still do
> not understand why the second one is faster. I will think about it for a
> while, though I can already write the corresponding patch `:-)`
>
> Before :
> {{{
> sage: %timeit
> digraphs.RandomDirectedGNP(10,.3).feedback_edge_set(value_only = True)
> ** Killed after 5 minutes **
> }}}
>
> After :
> {{{
> sage: %timeit
> digraphs.RandomDirectedGNP(10,.3).feedback_edge_set(value_only = True)
> 5 loops, best of 3: 21.8 ms per loop
> }}}
>
> Nathann
New description:
A friend of mine had the good idea to think about the MFAS problem one
evening, and told me that the LP formulation given in GLPK's examples was
able to return the optimal value of a particular problem in 8ms. It took
more (I did not wait) than 2 minutes for Sage.
I looked at the two formulations, and they were so clode that I still do
not understand why the second one is faster. I will think about it for a
while, though I can already write the corresponding patch `:-)`
Before :
{{{
sage: %timeit
digraphs.RandomDirectedGNP(10,.3).feedback_edge_set(value_only = True)
** Killed after 5 minutes **
}}}
After :
{{{
sage: %timeit
digraphs.RandomDirectedGNP(10,.3).feedback_edge_set(value_only = True)
5 loops, best of 3: 21.8 ms per loop
}}}
Requires : #10151
Nathann
--
Comment(by ncohen):
Patch rebased on top of #10151
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9911#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
