GLPK - Vote for possible inclusion in Sage

[Nathann Cohen]

Hello everybody !!!

Following this discussion ( http://groups.google.com/group/sage-devel/browse_thread/thread/9da47e06bcdfc49f
) about the availability of Linear Program Solvers and Mixed Integer
Program Solvers in Sage, I wrote a basic interface between Sage and
( GLPK, Coin-Or ). This patch is currently being reviewed ( and
corrected at the same time :-) ), but Marshall Hampton made me
remember I had completely forgotten about the voting process which is
customary is this situation, whithout which it is impossible to go
further.

So here we are !
Are you interested by LP features in Sage with GLPK as the native
solver ? ( The others would have to be optional packages but we
thought it would be smart to have a native one ).

( I have to emphasize that I would never have been able to create this
package without the help of William Stein and Mike Hansen who made the
"immediate" connection between a failure at the './configure' time and
a redefinition of Sage's shell variables. All hail their science ;-) )

Nathann

[Carlo Hamalainen]

On Sat, Aug 1, 2009 at 9:41 AM, Nathann Cohen<nathan...@gmail.com> wrote:
> Are you interested by LP features in Sage with GLPK as the native
> solver ? ( The others would have to be optional packages but we
> thought it would be smart to have a native one ).

Yes, especially if it can be used to speed up the graph colouring code
in some cases (at the moment it uses my C++ dlx solver but I'm sure
that LP etc could be useful in some other cases).

--
Carlo Hamalainen
http://carlo-hamalainen.net

[Robert]

I'd like LPs, too, of course.

By the way, do you know of the project http://pymprog.sourceforge.net/
that wraps GLPK with it's modelling language in python? Using PyGLPK,
as an additional layer, I'm pretty sure there is some relevant code
there.

On Aug 1, 12:46 pm, Carlo Hamalainen <carlo.hamalai...@gmail.com>
wrote:

[David Joyner]

I think Nathann Cohen has done a very valuable service with the GLPK and
COIN-OR-related packages.

That said, I have a "point of order" question. Is is true or false that the
process for a package to become standard we
(1) use trac to do nomination, testing, and acceptance as an optional
package,
(2) someone (William say) posts the spkg to
http://www.sagemath.org/packages/optional/,
(3) after a period of a few months, voting is done for making it standard.

In any case, I vote +1 for Nathann's GLPK spkg being moved to optional
and the currently posted GLPK spkg on experimental removed, with the
idea that it be proposed for inclusion as a standard package.

If the above process is correct then there is nothing more to say.
If not, I think someone (not me) look into this PyGLPK (I am
not an OR person and have never heard of this before). By
compare, I mean, look at the license, compare Nathann's wrappers and
docstrings to PyGLPK's, etc. Maybe there are other wrappers
on the internet (I have not done a google search, just mentioning
possibilities here.)

[Nathann Cohen]

Got it !

I knew nothing about all this, sorry :-)

I was just growing impatient because I only wrote the interface
between GLPK/Coin and Sage to add new functions to the Graph class,
whose docstrings I am currently writing... I already wrote :

def min_dominating_set(g, value_only=False):
def min_independant_dominating_set(g, value_only=False):
def min_vertex_cover(g,value_only=False):
def max_matching(g,value_only=False, use_edge_labels=True):
def max_flow(g,x,y,value_only=True,integer=False,
use_edge_labels=True):
def min_edge_cut(g,s,t,value_only=True,use_edge_labels=True):
def min_vertex_cut(g,s,t,value_only=True):
def edge_connectivity(g,value_only=True,use_edge_labels=True):
def vertex_connectivity(g,value_only=True):
def coloring(g,k=None):

and I think they may be pretty useful in the standard Sage.. ( it is
pretty easy to write them through LP, none of them is longer than 30
lines, but try to do it without... :-) )

Robert : I'll give a look to pymprog immediately, just to see what I
could add to what is already written, or if they are just ages in
advance.. But we had to write some meta-LP class to be able to use
indifferently GLPK, Coin, and CPLEX anyway... ;-)

Thank you all again !

Nathann

On Aug 1, 3:24 pm, David Joyner <wdjoy...@gmail.com> wrote:
> I think Nathann Cohen has done a very valuable service with the GLPK and
> COIN-OR-related packages.
>
> That said, I have a "point of order" question. Is is true or false that the
> process for a package to become standard we
> (1) use trac to do nomination, testing, and acceptance as an optional
> package,

> (2) someone (William say) posts the spkg tohttp://www.sagemath.org/packages/optional/,

> (3) after a period of a few months, voting is done for making it standard.
>
> In any case, I vote +1 for Nathann's GLPK spkg being moved to optional
> and the currently posted GLPK spkg on experimental removed, with the
> idea that it be proposed for inclusion as a standard package.
>
> If the above process is correct then there is nothing more to say.
> If not, I think  someone (not me) look into this PyGLPK (I am
> not an OR person and have never heard of this before). By
> compare, I mean, look at the license, compare Nathann's wrappers and
> docstrings to PyGLPK's, etc. Maybe there are other wrappers
> on the internet (I have not done a google search, just mentioning
> possibilities here.)
>

> On Sat, Aug 1, 2009 at 8:55 AM, Robert<m...@rschwarz.net> wrote:
>
> > I'd like LPs, too, of course.
>

> > By the way, do you know of the projecthttp://pymprog.sourceforge.net/

[Jason Grout]

Nathann Cohen wrote:
> Got it !
>
> I knew nothing about all this, sorry :-)
>
> I was just growing impatient because I only wrote the interface
> between GLPK/Coin and Sage to add new functions to the Graph class,
> whose docstrings I am currently writing... I already wrote :
>
> def min_dominating_set(g, value_only=False):
> def min_independant_dominating_set(g, value_only=False):
> def min_vertex_cover(g,value_only=False):
> def max_matching(g,value_only=False, use_edge_labels=True):
> def max_flow(g,x,y,value_only=True,integer=False,
> use_edge_labels=True):
> def min_edge_cut(g,s,t,value_only=True,use_edge_labels=True):
> def min_vertex_cut(g,s,t,value_only=True):
> def edge_connectivity(g,value_only=True,use_edge_labels=True):
> def vertex_connectivity(g,value_only=True):
> def coloring(g,k=None):
>

This is a fantastic addition of functionality to the Graph class.
Thanks!! I could have used some of these functions before, but had to
do without because I didn't have time to write them.

Jason

[William Stein]

On Sat, Aug 1, 2009 at 6:24 AM, David Joyner <wdjo...@gmail.com> wrote:

I think Nathann Cohen has done a very valuable service with the GLPK and
COIN-OR-related packages.

That said, I have a "point of order" question. Is is true or false that the
process for a package to become standard we
(1) use trac to do nomination, testing, and acceptance as an optional
package,
(2) someone (William say) posts the spkg to
http://www.sagemath.org/packages/optional/,
(3) after a period of a few months, voting is done for making it standard.

In any case, I vote +1 for Nathann's GLPK spkg being moved to optional
and the currently posted GLPK spkg on experimental removed, with the
idea that it be proposed for inclusion as a standard package.

Yes, this is exactly right.   So GLPK should become optional for a while before we even vote on it being standard.

NOTE: GLPK is GPLv3.  Since we need to retain the ability to release GPLv2 versions of Sage for now, this is another very good reason to make it optional for a while (so it is easy to swap out).
 
William

If the above process is correct then there is nothing more to say.
If not, I think  someone (not me) look into this PyGLPK (I am
not an OR person and have never heard of this before). By
compare, I mean, look at the license, compare Nathann's wrappers and
docstrings to PyGLPK's, etc. Maybe there are other wrappers
on the internet (I have not done a google search, just mentioning
possibilities here.)

On Sat, Aug 1, 2009 at 8:55 AM, Robert<ma...@rschwarz.net> wrote:
>
> I'd like LPs, too, of course.
>
> By the way, do you know of the project http://pymprog.sourceforge.net/
> that wraps GLPK with it's modelling language in python? Using PyGLPK,
> as an additional layer, I'm pretty sure there is some relevant code
> there.
>
> On Aug 1, 12:46 pm, Carlo Hamalainen <carlo.hamalai...@gmail.com>
> wrote:
>> On Sat, Aug 1, 2009 at 9:41 AM, Nathann Cohen<nathann.co...@gmail.com> wrote:
>> > Are you interested by LP features in Sage with GLPK as the native
>> > solver ? ( The others would have to be optional packages but we
>> > thought it would be smart to have a native one ).
>>
>> Yes, especially if it can be used to speed up the graph colouring code
>> in some cases (at the moment it uses my C++ dlx solver but I'm sure
>> that LP etc could be useful in some other cases).
>>
>> --
>> Carlo Hamalainenhttp://carlo-hamalainen.net
> >
>

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

[Nathann Cohen]

Hmmmm... There is still something I did not understand, sorry ;-)

Coin-or/Cbc is meant to be an optional package, and if approved it
will stay this way : fine
GLPK should be a standard package, but as it is customary it will be
optional for a while ( and perhaps a bit more to let us think about
license issues ^^; )

What is the future of the class numerical.MIP (cf.
http://trac.sagemath.org/sage_trac/ticket/6502 ) which uses all of
this but is totally useless without either Coin or Glpk ? Thinking
Coin may not be available, this class detects whether it is installed
and acts accordingly, but as I thought GLPK would always be installed,
it assumes it is available without any checking.
Will this class be included in the standard Sage, then ? And if so, do
I need to write some code to make it detect the presence of GLPK and
totally refuse to run otherwise ?

I just finished to write the docstrings of the function edge_coloring
( coloring() has been renamed vertex_coloring as it is better to write
a LP for edge_coloring than to use vertex_coloring on a line graph ).
All the functions I mentionned are working and documented. In the end,
when should I post a patch for them ? ;-)

Thank you for your help ! :-)

Nathann

On Aug 1, 7:59 pm, William Stein <wst...@gmail.com> wrote:

> > On Sat, Aug 1, 2009 at 8:55 AM, Robert<m...@rschwarz.net> wrote:
>
> > > I'd like LPs, too, of course.
>

> > > By the way, do you know of the projecthttp://pymprog.sourceforge.net/

[William Stein]

On Sat, Aug 1, 2009 at 1:50 PM, Nathann Cohen<nathan...@gmail.com> wrote:
>
> Hmmmm... There is still something I did not understand, sorry ;-)
>
> Coin-or/Cbc is meant to be an optional package, and if approved it
> will stay this way : fine
> GLPK should be a standard package, but as it is customary it will be
> optional for a while ( and perhaps a bit more to let us think about
> license issues ^^; )
>
> What is the future of the class numerical.MIP (cf.
> http://trac.sagemath.org/sage_trac/ticket/6502 ) which uses all of
> this but is totally useless without either Coin or Glpk ? Thinking
> Coin may not be available, this class detects whether it is installed
> and acts accordingly, but as I thought GLPK would always be installed,
> it assumes it is available without any checking.
> Will this class be included in the standard Sage, then ? And if so, do
> I need to write some code to make it detect the presence of GLPK and
> totally refuse to run otherwise ?
>
> I just finished to write the docstrings of the function edge_coloring
> ( coloring() has been renamed vertex_coloring as it is better to write
> a LP for edge_coloring than to use vertex_coloring on a line graph ).
> All the functions I mentionned are working and documented. In the end,
> when should I post a patch for them ? ;-)
>
> Thank you for your help ! :-)
>
> Nathann

I personally think GLPK will end up being standard in Sage before
long, so I think your approach right now is pretty good. It's just
that it has to be optional for a bit (a month or so), since that's
what we do.

Make glpk optional + making your patch trivial to install, and lots of
people will then easily be able to play around with it.

-- William