Opened 9 years ago
Closed 8 years ago
#9911 closed enhancement (fixed)
Changing the LP formulation of feedback vertex/arc set to improve the speed
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | graph theory | Keywords: | |
Cc: | abmasse, mvngu | Merged in: | sage-4.6.2.alpha1 |
Authors: | Nathann Cohen, Geoffrey Ehrman | Reviewers: | Robert Miller |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
Attachments (2)
Change History (13)
comment:1 Changed 9 years ago by
- Description modified (diff)
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 Changed 9 years ago by
- Cc mvngu added
comment:5 Changed 9 years ago by
- Status changed from needs_review to needs_info
Hi Nathann !
A question and a remark:
- If I understand correctly, your ticket is improving the speed of the minimum feedback vertex/arc set problems by providing another LP formulation. Could you detail where you took the first formulation (I assume you're the one who coded it) and where you got the new one? This could help in the review process to compare and make sure the two methods are equivalent.
- I a bunch of lines where lists are created without being used, such as in:
[p.add_constraint(d[v],min=n) for v in self]
Wouldn't it be better to replace it with a loop?for v in self: p.add_constraint(d[v], min=n)
I think it's useless to create a list that will be thrown to the garbage collector right away :) Moreover, the number of characters is exactly the same, so it's not a waste of space :)
comment:6 Changed 9 years ago by
- Status changed from needs_info to needs_review
Hello !!!
You are totally right about these lists.. That's just how I coded LP at first, but it wasn't a good idea after all. You will find the "modern LP code" easier to read :-D
About the formulations... Well, the first one was just the one I came up with when I first wanted to solve MFAS problems, and the other one was given to me by a friend who was reading glpk's examples. You will find this file there :
http://stuff.mit.edu/afs/athena/software/glpk/examples/mfasp.mod
Note that even though the speed improvement is great, I wrote #9923 some time later and wondered whether I should remove this patch because of it : there is no comparison possible between this LP formulation and #9923, which will be (when it will be merged) the default way to solve MFAS problems. This formulation will just stay as a backup, or to check both algorithms' correctness (unless people do not want it of course, but that's what I had in mind when writing #9923)...
(patch updated)
Nathann
Changed 9 years ago by
comment:7 Changed 9 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
- Reviewers set to Robert Miller
- Status changed from needs_review to needs_work
You're still using the list syntax for constraint addition loops at the end of the patch:
[p.add_constraint(d[u]-d[v]+n*(b[u]+b[v]),min=1) for (u,v) in self.edges(labels=None)] [p.add_constraint(d[u],max=n) for u in self]
Other than that, this patch looks good. All long tests pass against sage-4.6.1.rc1 and I'm otherwise happy. Fix the one issue, ping me and I'll set this to positive review.
Changed 9 years ago by
comment:10 Changed 9 years ago by
Thanksssssss !! :-)
comment:11 Changed 8 years ago by
- Merged in set to sage-4.6.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Patch rebased on top of #10151
Nathann