id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
9911 Changing the LP formulation of feedback vertex/arc set to improve the speed ncohen jason ncohen rlm "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" enhancement closed major sage-4.6.2 graph theory fixed abmasse mvngu sage-4.6.2.alpha1 Nathann Cohen, Geoffrey Ehrman Robert Miller N/A