Opened 9 years ago

Closed 9 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 ncohen)

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)

trac_9911.patch (5.3 KB) - added by ncohen 9 years ago.
9911_fix.patch (952 bytes) - added by gbe 9 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:3 Changed 9 years ago by ncohen

  • Description modified (diff)

Patch rebased on top of #10151

Nathann

comment:4 Changed 9 years ago by mvngu

  • Cc mvngu added

comment:5 Changed 9 years ago by abmasse

  • Status changed from needs_review to needs_info

Hi Nathann !

A question and a remark:

  1. 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.
  2. 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 ncohen

  • 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 ncohen

comment:7 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • 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.

comment:8 Changed 9 years ago by gbe

  • Authors changed from Nathann Cohen to Nathann Cohen, Geoffrey Ehrman

Added a small patch fixing the last two list comprehension liness.

Changed 9 years ago by gbe

comment:9 Changed 9 years ago by rlm

  • Status changed from needs_work to positive_review

Thank you!

comment:10 Changed 9 years ago by ncohen

Thanksssssss !! :-)

comment:11 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.