Hello everybody !!!! I have been thinking for a while about different ways to build something great from the support for Linear Programming in Sage. There's one idea I would like to explore, and I need to know if some of you would be : - Interested in using it - Interesting in helping me to write it
It may have to deal with a new "type" of symbolics in Sage, I do not know yet, and you're all so full of experience I will probable keep asking questions for the next month... ;-) Here is what I thought about : I wanted to write an algorithm in Sage for the Minimum Feedback Vertex Set problem ( http://en.wikipedia.org/wiki/Feedback_vertex_set ). This problem is the following : given a graph G, what is a vertex subset S of minimum cardinality such that the graph minus S is a forest ( contains no cycle ). It is very easy to say it, a bit harder ( at least for me ) to write it as a linear program. I know which function I want to minimize, but I do not know how to write a linear program testing that "there is no cycle in the graph". I know, though, how to write a linear program GIRTH computing the smallest cycle ( girth ) of the graph. What I need, then, to ensure that a graph is cycle free "smallest cycle in the graph" is to ensure that the DUAL of the GIRTH program can be at least the size of the graph+1. So this is what I think we need in Sage : first, a way to compute duals (but this I can write pretty quickly), and a way to merge programs one into the other to build bigger ones. In the lab I work in, people are constantly trying to build networks of minimum cost under very specific constraint ( some multiflow is feasible, the graph is k-connected, etc, etc ... ). They --always-- have to rewrite all the LP programs, name the variables, into a looong Linear Program. And this, as a coder, I can not stand :-) Linear Programming needs a way to merge programs, to obtain duals without more than a call to a .dual() method, and a big database of Linear Programs from where other ones can be easily defined. I do not know much of what can be done in GLPK, Ampl, Cplex, Coin-Or, and a lot of other LP-related softwares I have no clues about, which you may perfectly know.... Is it something you have already seen somewhere, in which case I could try to give it a look to spare some time, or is it new and does it need to be built from scratch ? More importantely, do you think it is -- useful -- ? Thank you for your help !!! Nathann --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
