7 views

Skip to first unread message

Aug 1, 2009, 3:41:55 AM8/1/09

to sage-devel

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

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

Aug 1, 2009, 6:46:51 AM8/1/09

to sage-...@googlegroups.com

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 ).

> 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

Aug 1, 2009, 8:55:36 AM8/1/09

to sage-devel

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:

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:

Aug 1, 2009, 9:24:06 AM8/1/09

to sage-...@googlegroups.com

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.)

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.)

Aug 1, 2009, 12:01:03 PM8/1/09

to sage-devel

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/,

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,

> (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.)

>

>

> 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/
>

> > I'd like LPs, too, of course.

>

Aug 1, 2009, 1:39:42 PM8/1/09

to sage-...@googlegroups.com

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):

>

> 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

Aug 1, 2009, 1:59:03 PM8/1/09

to sage-...@googlegroups.com

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

Aug 1, 2009, 4:50:32 PM8/1/09

to sage-devel

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:

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/
>

> > > I'd like LPs, too, of course.

>

Aug 1, 2009, 5:08:05 PM8/1/09

to sage-...@googlegroups.com

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
>

> 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

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu