Opened 10 years ago

Closed 10 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 10 years ago.
9911_fix.patch (952 bytes) - added by gbe 10 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 10 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

comment:3 Changed 10 years ago by ncohen

  • Description modified (diff)

Patch rebased on top of #10151

Nathann

comment:4 Changed 10 years ago by mvngu

  • Cc mvngu added

comment:5 Changed 10 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 10 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 10 years ago by ncohen

comment:7 Changed 10 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 10 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 10 years ago by gbe

comment:9 Changed 10 years ago by rlm

  • Status changed from needs_work to positive_review

Thank you!

comment:10 Changed 10 years ago by ncohen

Thanksssssss !! :-)

comment:11 Changed 10 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.