Linear Programming and MIP... Let's start something huge !

[Nathann Cohen]

Hello everybody !!!!

I have already sent a few messages about this and complained for a
while. The only way for the moment to solve Linear Programs (
http://en.wikipedia.org/wiki/Linear_programming ) is CVXOPT, a library
focused on convex optimization, and we need much, much more than this.

There are three softwares that I know which can solve Linear
Programs :

- GLPK ( http://www.gnu.org/software/glpk/ )
http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit
Totally Free, can be merged into SAGE


- COIN-OR ( http://www.coin-or.org/ )
http://en.wikipedia.org/wiki/COIN-OR
GPL-Uncompatible

- CPLEX http://www.ilog.fr/products/cplex/
http://en.wikipedia.org/wiki/CPLEX
Proprietary


To my knowledge, GLPK is far behind COIN-OR and CPLEX which have
similar performances. Now, GLPK is the natural choice for SAGE because
it is totally Free, and it has to be available. But COIN-OR has such
performances that it cannot be discarded just because of its license
( which is not "that far" from being GPL-Compatible, besides... ), and
I think many of the persons using SAGE at work may have some access to
CPLEX Licenses ( which lets them use it in parallel, or perhaps in a
distributed way, I do not know all about it ).

This, to say that all three should be accessible through SAGE ( GLPK
by default, COIN-OR as an optionnal package, and CPLEX if installed ),
and that we should begin to think about a common way to solve linear
programs in SAGE, and as importantly MIP ( Mixed Integer Programs
http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns
).
I am particularly interested in this feature as it would mean that a
---LOT--- of new graph-theoretic functions could be very soon, very
efficiently, and very easily added to the SAGE Library. We are missing
so many essential things that could be solved in several lines of LP
or MIP that waiting is just insane ;-)

As I have my own constraints, I had to build for myself a quick
interface between SAGE and CBC ( which belongs to the COIN-OR
Family ). It uses the command-line executable and creates dirty
temporary files, which we want to avoid in SAGE. In the end you can
access COIN-OR through SAGE with two screens of code (
http://www-sop.inria.fr/members/Nathann.Cohen/cbc.spyx ), and a
Maximum Independant Set becomes as easy as this :

g=graphs.RandomGNP(10,.5)
p=MIPSProgram(max=True)
obj={}
for i in g.vertices():
obj["V"+str(i)]=1
p.setinteger("V"+str(i))

p.setobj(obj)
for (a,b,c) in g.edges():
obj={}
obj["V"+str(a)]=1
obj["V"+str(b)]=1
obj["lt"]=1
p.addconstraint(obj)
p.solve()

I am sending this message because I would like to reach the people who
would like to have LP and MIP solvers in SAGE, and who may be
interested in writing the code we need for this. I would also like to
have your advice about what I now imagine of its implementation. I
would not like ( but this is only my advice, and "I am all ears" ) to
have the user deal with the final matrices as we have to in CVXOPT. I
like the idea of adding constraint independently from the previous
ones as I am doing in this short code for Max Independant Set. It may
not be the best way ( and please tell me what you think of it ) but I
record each linear form : 2*A + 3*B - 5*C as a dictionary {"A":2, "B":
3, "C":-5 }. I have to add "lt":1 if I want to ensure that this form
is < 1, but I think we should create a new class LinearConstraint with
proper functions associated to it. Finally, the variable have no
reason to be strings and should be general Object ( if possible ).

I hope many of you will be interested by LP and MIP in Sage and will
be willing to work on it too ! I have my version of it, so I can wait
without any problem, but SAGE --needs-- LP and MIP solvers ;-)

Have fun !

Nathann

[David Joyner]

Thanks for working on this! I agree with the points in your email.

LP solvers are an important topic where I teach so I am happy to
help. I think some of my colleagues would be very interested in
trying out whatever is developed. I'm not an operations
research person myself but would be interested in testing out
any OR software interface you have.

[William Stein]

Your strategy sounds very good to me.

1. Make a unified interface to using LP solvers, and include GLPK in
Sage by default, to provide the LP functionality.

2. Make it possible to also use COIN-OR and CPLEX by simply changing
one parameter, and speed up code.

This is very similar to what we do now with Groebner basis. The
default is Singular, but for users with Magma, they can easily use
Magma instead to computer Groebner basis.

William

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

[Robert Schwarz]

COIN-OR has a project called OSI, the open solver interface, for its own
lp solver clp but also CPLEX and GLPK (among others, see:
https://projects.coin-or.org/Osi/), so only this OSI has to be interfaced
to SAGE, to get all generality in lp solving.

In my understanding, cbc can solve mixed-integer programs, but for the
many combinatorial optimization problems (e.g. max cut in graphs) it's
better to build your own sophisticated solver, using a framework like
abacus or COIN-OR bcp.

As for license issues: It shouldn't be a problem to write interface code,
like there is with magma. Then the users would have to (optionally)
install some COIN-OR projects on their own.

There is already a list of useful software in the wiki:
http://wiki.sagemath.org/optimization

I would definitely be interested in some more code in this direction,
especially together with the graph theory already available.

--
Robert Schwarz <ma...@rschwarz.net>

Get my public key at http://rschwarz.net/key.asc

[Joachim Dahl]

If you're considering interfacing to commercial libraries,
you should definitely consider MOSEK (www.mosek.com),
which is an excellent commercial convex optimization package
that includes conic MIP.

CVXOPT also interfaces to MOSEK, which has a native Python
interface.

Joachim

On Jun 29, 3:09 pm, "Robert Schwarz" <m...@rschwarz.net> wrote:
> COIN-OR has a project called OSI, the open solver interface, for its own
> lp solver clp but also CPLEX and GLPK (among others, see:https://projects.coin-or.org/Osi/), so only this OSI has to be interfaced
> to SAGE, to get all generality in lp solving.
>
> In my understanding, cbc can solve mixed-integer programs, but for the
> many combinatorial optimization problems (e.g. max cut in graphs) it's
> better to build your own sophisticated solver, using a framework like
> abacus or COIN-OR bcp.
>
> As for license issues: It shouldn't be a problem to write interface code,
> like there is with magma. Then the users would have to (optionally)
> install some COIN-OR projects on their own.
>
> There is already a list of useful software in the wiki:http://wiki.sagemath.org/optimization
>
> I would definitely be interested in some more code in this direction,
> especially together with the graph theory already available.
>
>
>
> On Mon, June 29, 2009 13:25, David Joyner wrote:
>
> > Thanks for working on this! I agree with the points in your email.
>
> > LP solvers are an important topic where I teach so I am happy to
> > help. I think some of my colleagues would be very interested in
> > trying out whatever is developed. I'm not an operations
> > research person myself but would be interested in testing out
> > any OR software interface you have.
>

> > On Mon, Jun 29, 2009 at 7:08 AM, Nathann Cohen<nathann.co...@gmail.com>

> > wrote:
>
> >> Hello everybody !!!!
>
> >> I have already sent a few messages about this and complained for a
> >> while. The only way for the moment to solve Linear Programs (

> >>http://en.wikipedia.org/wiki/Linear_programming) is CVXOPT, a library

> >> focused on convex optimization, and we need much, much more than this.
>
> >> There are three softwares that I know which can solve Linear
> >> Programs :
>
> >> - GLPK (http://www.gnu.org/software/glpk/)
> >>  http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit
> >>  Totally Free, can be merged into SAGE
>
> >> - COIN-OR (http://www.coin-or.org/)
> >>  http://en.wikipedia.org/wiki/COIN-OR
> >>  GPL-Uncompatible
>

> >> - CPLEXhttp://www.ilog.fr/products/cplex/

> >>http://www-sop.inria.fr/members/Nathann.Cohen/cbc.spyx), and a

> Robert Schwarz <m...@rschwarz.net>
>
> Get my public key athttp://rschwarz.net/key.asc

[Nathann Cohen]

It may be a good idea to interface to OSI in order to avoid having to
interface to both CPLEX and COIN-OR, but for license reasons we can
not use OSI to interface to GLPK as OSI is GPL-Uncompatible and the
only reason we want glpk installed by default is that it is the only
gpl LP solver ;-)

Nathann

On Jun 29, 3:09 pm, "Robert Schwarz" <m...@rschwarz.net> wrote:

> COIN-OR has a project called OSI, the open solver interface, for its own
> lp solver clp but also CPLEX and GLPK (among others, see:https://projects.coin-or.org/Osi/), so only this OSI has to be interfaced
> to SAGE, to get all generality in lp solving.
>
> In my understanding, cbc can solve mixed-integer programs, but for the
> many combinatorial optimization problems (e.g. max cut in graphs) it's
> better to build your own sophisticated solver, using a framework like
> abacus or COIN-OR bcp.
>
> As for license issues: It shouldn't be a problem to write interface code,
> like there is with magma. Then the users would have to (optionally)
> install some COIN-OR projects on their own.
>
> There is already a list of useful software in the wiki:http://wiki.sagemath.org/optimization
>
> I would definitely be interested in some more code in this direction,
> especially together with the graph theory already available.
>
>
>
> On Mon, June 29, 2009 13:25, David Joyner wrote:
>
> > Thanks for working on this! I agree with the points in your email.
>
> > LP solvers are an important topic where I teach so I am happy to
> > help. I think some of my colleagues would be very interested in
> > trying out whatever is developed. I'm not an operations
> > research person myself but would be interested in testing out
> > any OR software interface you have.
>

> > On Mon, Jun 29, 2009 at 7:08 AM, Nathann Cohen<nathann.co...@gmail.com>

> > wrote:
>
> >> Hello everybody !!!!
>
> >> I have already sent a few messages about this and complained for a
> >> while. The only way for the moment to solve Linear Programs (

> >>http://en.wikipedia.org/wiki/Linear_programming) is CVXOPT, a library

> >> focused on convex optimization, and we need much, much more than this.
>
> >> There are three softwares that I know which can solve Linear
> >> Programs :
>
> >> - GLPK (http://www.gnu.org/software/glpk/)
> >>  http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit
> >>  Totally Free, can be merged into SAGE
>

> >> - COIN-OR (http://www.coin-or.org/)
> >>  http://en.wikipedia.org/wiki/COIN-OR
> >>  GPL-Uncompatible
>

> >> - CPLEXhttp://www.ilog.fr/products/cplex/

> >>http://www-sop.inria.fr/members/Nathann.Cohen/cbc.spyx), and a

[Stephen Hartke]

On Mon, Jun 29, 2009 at 10:18 AM, Nathann Cohen <nathan...@gmail.com> wrote:

It may be a good idea to interface to OSI in order to avoid having to
interface to both CPLEX and COIN-OR, but for license reasons we can
not use OSI to interface to GLPK as OSI is GPL-Uncompatible and the
only reason we want glpk installed by default is that it is the only
gpl LP solver ;-)

lp_solve is GLPv2+ and already has a Python interface; I am creating an spkg for it.

There are also a Python interface to OSI called pyOSI and Python interfaces PyGLPK and python-glpk to GLPK.

Best wishes,
Stephen

[Nathann Cohen]

Hmmm... I began to write the interface to CBC to notice that the
libraries was writtten in C++ and that I needed to wrap C++ classes
into Cython, which I do not know how to do ... I read several manuals
and end up with compilation failures I do not know how to fix :
sage: execfile("setup.py")
---------------------------------------------------------------------------
SystemExit Traceback (most recent call
last)

/auto/sop-nas2a/u/sop-nas2a/vol/home_mascotte/ncohen/sage/<ipython
console> in <module>()

/auto/sop-nas2a/u/sop-nas2a/vol/home_mascotte/ncohen/sage/setup.py in
<module>()
14 extra_link_args=["-l OsiClp -l Osi -l Clp -l
CoinUtils"], # if needed
15 # cmdclass = {'build_ext': build_ext}
16 )],
---> 17 cmdclass = {'build_ext': build_ext}
18 )

/auto/sop-nas2a/u/sop-nas2a/vol/home_mascotte/ncohen/.sagebin/local/
lib/python/distutils/core.pyc in setup(**attrs)

SystemExit: usage: sage-ipython [global_opts] cmd1 [cmd1_opts] [cmd2
[cmd2_opts] ...]
or: sage-ipython --help [cmd1 cmd2 ...]
or: sage-ipython --help-commands
or: sage-ipython cmd --help

error: option -i not recognized
Type %exit or %quit to exit IPython (%Exit or %Quit do so
unconditionally).
sage:

If anybody with skills in interfacing C++ with Sage is available, let
him appear now !

Nathann

On Jun 30, 6:54 am, Stephen Hartke <har...@gmail.com> wrote:

[William Stein]

Your best bet is to look at the many complete working examples of
wrapping substantial C++ libraries that are already in Sage. E.g., I
like the wrapper of givaro in the rings/finite_field_givaro* files.
Also, there are extensive wrappers of NTL in libs/ntl/*

William

[Nathann Cohen]

Hmmm.... Could this kind of behaviour come fro the sole fact that I do
not use a "good" version of some software ?

sage: setup()

---------------------------------------------------------------------------
SystemExit Traceback (most recent call
last)

/auto/sop-nas2a/u/sop-nas2a/vol/home_mascotte/ncohen/sage/setup.py in
<module>()

/auto/sop-nas2a/u/sop-nas2a/vol/home_mascotte/ncohen/.sagebin/local/
lib/python/distutils/core.pyc in setup(**attrs)

SystemExit: usage: sage-ipython [global_opts] cmd1 [cmd1_opts] [cmd2
[cmd2_opts] ...]
or: sage-ipython --help [cmd1 cmd2 ...]
or: sage-ipython --help-commands
or: sage-ipython cmd --help

error: option -i not recognized
Type %exit or %quit to exit IPython (%Exit or %Quit do so
unconditionally).
sage:

This setup() command seems to be useful when one tries to build
extensions, but it also seems to be in a nasty mood ;-)

Nathann

On Jul 3, 3:42 pm, William Stein <wst...@gmail.com> wrote:

[Nicolas M. Thiery]

+1

We (e.g. the Sage-Combinat people) definitely would have a use for
it. We would even love it better if the interface could be consistent
with other related problems (e.g. testing for the existence of /
counting / iterating trough the integral points of a polytope).

I don't foresee manpower from us to work on this though ...

Good luck!

Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[dmitrey]

Hi all,
I have been pointed to the discussion some time ago.

You could be interested in the approach implemented in FuncDesigner LP
model:
http://openopt.org/NumericalOptimizationForFuncDesignerModels#LP_example
Maybe in future I'll add FuncDesigner examples for MILP and some more
classes.

Let me also note - statement "COIN-OR and CPLEX which have similar
performances" is completely wrong.
First of all COIN-OR project is a set of solvers (LP, NLP, etc), not
an LP/MILP solver.
At second, it is well-known CPLEX is too far ahead of any free MILP
solver.
See for example the bench by Hans Mittelmann (one of most
authoritative), where CPLEX is 6 times faster of fastest free MILP
solver
http://forum.openopt.org/viewtopic.php?id=18

Regards, D.

On Jun 29, 2:08 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Hello everybody !!!!
>
> I have already sent a few messages about this and complained for a

> while. The only way for the moment to solve Linear Programs (http://en.wikipedia.org/wiki/Linear_programming) is CVXOPT, a library

> focused on convex optimization, and we need much, much more than this.
>
> There are three softwares that I know which can solve Linear
> Programs :
>
> - GLPK (http://www.gnu.org/software/glpk/)
>  http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit
>   Totally Free, can be merged into SAGE
>

> - COIN-OR (http://www.coin-or.org/)
>  http://en.wikipedia.org/wiki/COIN-OR
>   GPL-Uncompatible
>

> - CPLEXhttp://www.ilog.fr/products/cplex/

>  http://en.wikipedia.org/wiki/CPLEX
>   Proprietary
>
> To my knowledge, GLPK is far behind COIN-OR and CPLEX which have
> similar performances. Now, GLPK is the natural choice for SAGE because
> it is totally Free, and it has to be available. But COIN-OR has such
> performances that it cannot be discarded just because of its license
> ( which is not "that far" from being GPL-Compatible, besides... ), and
> I think many of the persons using SAGE at work may have some access to
> CPLEX Licenses ( which lets them use it in parallel, or perhaps in a
> distributed way, I do not know all about it ).
>
> This, to say that all three should be accessible through SAGE ( GLPK
> by default, COIN-OR as an optionnal package, and CPLEX if installed ),
> and that we should begin to think about a common way to solve linear

> programs in SAGE, and as importantly MIP ( Mixed Integer Programshttp://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns

> ).
> I am particularly interested in this feature as it would mean that a
> ---LOT--- of new graph-theoretic functions could be very soon, very
> efficiently, and very easily added to the SAGE Library. We are missing
> so many essential things that could be solved in several lines of LP
> or MIP that waiting is just insane ;-)
>
> As I have my own constraints, I had to build for myself a quick
> interface between SAGE and CBC ( which belongs to the COIN-OR
> Family ). It uses the command-line executable and creates dirty
> temporary files, which we want to avoid in SAGE. In the end you can

> access COIN-OR through SAGE with two screens of code (http://www-sop.inria.fr/members/Nathann.Cohen/cbc.spyx), and a

[Nathann Cohen]

Hello !

> You could be interested in the approach implemented in FuncDesigner LP
> model:http://openopt.org/NumericalOptimizationForFuncDesignerModels#LP_example
> Maybe in future I'll add FuncDesigner examples for MILP and some more
> classes.

I *AM* interested in this... Thanks for the information !!! I am
looking for ways to make LP easier in Sage ( it can be done now, but
it is far from being as easy as in the example you show... Could you
tell me how you deal with indexed variables, as x_1, ..., x_n ( and it
could have to be indexed 2 or 3 times ) ?

> Let me also note - statement "COIN-OR and CPLEX which have similar
> performances" is completely wrong.

A colleague of mine who tested them seemed to say they had similar
performances (and he is likely to have spent quite a long time on
that :-) ), and the link you gave seems to confirm the fact that
"compared to GLPK, the solvers from COIN and CPLEX are way ahead".
There seem to be another gap between COIN and CPLEX, though, you are
right, I am just being kind to a colleague who did not try to betray
me :-)

> First of all COIN-OR project is a set of solvers (LP, NLP, etc), not
> an LP/MILP solver.

I was talking about Cbc, I often do it as COIN if a bit more famous
than Cbc

> At second, it is well-known CPLEX is too far ahead of any free MILP
> solver.
> See for example the bench by Hans Mittelmann (one of most
> authoritative), where CPLEX is 6 times faster of fastest free MILP
> solverhttp://forum.openopt.org/viewtopic.php?id=18

The interface with COIN which is to be ( I hope ) one day merged to
Sage uses Osi, which also provides an interface to CPLEX. To build a
support for CPLEX, one would only need to replace the string "Cbc" by
"Cplex" in the source code, which takes O(1) time. I will be able to
do it myself pretty soon, so Sage will also be able to use CPLEX :-)

In the meantime, and even if I only talk about its graph-theoretic
applications, Sage already gained a LOT from the integration of Cbc
and GLPK... I will do what I can from now on to integrate a good
support for MIP...

Thanks a lot for your remarks !! :-)

Nathann

[dmitrey]

On Aug 26, 7:47 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Hello !
>
> > You could be interested in the approach implemented in FuncDesigner LP
> > model:http://openopt.org/NumericalOptimizationForFuncDesignerModels#LP_example
> > Maybe in future I'll add FuncDesigner examples for MILP and some more
> > classes.
>
> I *AM* interested in this... Thanks for the information !!! I am
> looking for ways to make LP easier in Sage ( it can be done now, but
> it is far from being as easy as in the example you show... Could you
> tell me how you deal with indexed variables, as x_1, ..., x_n ( and it
> could have to be indexed 2 or 3 times ) ?

Yes, you can use indexation like some_oovar[i] or some_oofun[i]
(probably with several indexes, or negative ones that are start from
array end), however, I think it should be avoided if possible (you'd
better split your oovar into several oovars).
http://www.openopt.org/FuncDesignerDoc#Some_issues_to_be_aware
As for arrays with ndim>1 they are not implemented in FuncDesigner yet
and will be hardly implemented in nearest future, for the release 0.15
I intend to focus on stability. Also, I have difficulties with
Automatic differentiation (for nonlinear functions) when ndim>1 (even
for ndim <=1 it wasn't that easy). I don't want someone to spend lots
of time and efforts for coding a FuncDesigner model and then get
"Automatic differentiation cannot be done for the model yet".
However, I think dot(some_fixed_array, some_oovar_or_oofun) will be
ready till nearest FD release with some_fixed_array.ndim <= 2.

> > Let me also note - statement "COIN-OR and CPLEX which have similar
> > performances" is completely wrong.
>
> A colleague of mine who tested them seemed to say they had similar
> performances (and he is likely to have spent quite a long time on
> that :-) ), and the link you gave seems to confirm the fact that
> "compared to GLPK, the solvers from COIN and CPLEX are way ahead".
> There seem to be another gap between COIN and CPLEX, though, you are
> right, I am just being kind to a colleague who did not try to betray
> me :-)

Maybe I have translated it wrong with my small knowledge of English.

> > First of all COIN-OR project is a set of solvers (LP, NLP, etc), not
> > an LP/MILP solver.
>
> I was talking about Cbc, I often do it as COIN if a bit more famous
> than Cbc
>
> > At second, it is well-known CPLEX is too far ahead of any free MILP
> > solver.
> > See for example the bench by Hans Mittelmann (one of most
> > authoritative), where CPLEX is 6 times faster of fastest free MILP
> > solverhttp://forum.openopt.org/viewtopic.php?id=18
>
> The interface with COIN which is to be ( I hope ) one day merged to
> Sage uses Osi, which also provides an interface to CPLEX.

I had awared of OSI, but I'm not skilled in connecting code of other
languages to Python, that's why I hadn't go for it.

> To build a
> support for CPLEX, one would only need to replace the string "Cbc" by
> "Cplex" in the source code, which takes O(1) time. I will be able to
> do it myself pretty soon, so Sage will also be able to use CPLEX :-)
>
> In the meantime, and even if I only talk about its graph-theoretic
> applications, Sage already gained a LOT from the integration of Cbc
> and GLPK... I will do what I can from now on to integrate a good
> support for MIP...

This is very nice to hear, still I think it would be better to provide
Python-OSI API instead of SAGE-OSI, it would benefit more wield
auditory (PythonXY, EPD, mere Python-scipy users etc). Of course, it's
up to you - mb you are SAGE developer at first.

Regards, D.

[Nathann Cohen]

> Yes, you can use indexation like some_oovar[i] or some_oofun[i]
> (probably with several indexes, or negative ones that are start from
> array end), however, I think it should be avoided if possible (you'd
> better split your oovar into several oovars).http://www.openopt.org/FuncDesignerDoc#Some_issues_to_be_aware

I sent a message on sage-support to know to which extent I could use
multivariate Polynomials in Sage to represent constraints and Linear
functions, but it seems to be troublesome... This said, there is no
way for me to use Linear Programming if I can not use indexed
variables... At the moment, even though the syntax could be
tremendously improved, I can use any hashable Sage object as a
variable, and most of the time in Graph theoretic function my
variables are edges, vertices, or arbitrary tuples and strings.
Anyway, most of the Linear Programs are generated from graphs and I
have to find a way to let a computer create as many variables as
possible :-/
The current syntax, though, is not nearly satisfying.

> Maybe I have translated it wrong with my small knowledge of English.

I'm french. We bear the same cross ;-)

> I had awared of OSI, but I'm not skilled in connecting code of other
> languages to Python, that's why I hadn't go for it.
>

> This is very nice to hear, still I think it would be better to provide
> Python-OSI API instead of SAGE-OSI, it would benefit more wield
> auditory (PythonXY, EPD, mere Python-scipy users etc). Of course, it's
> up to you - mb you are SAGE developer at first.

I'm sorry to give you this "cheap" an answer, but if anyone wants to
write such code, it will always be available as it is GPL-Licensed. I
am not particularly interested in LP, I just began to write these
interfaces because I thought the Graph functions I needed would be
much harder to write otherwise, and often less effective. I just wrote
a shortcut. Now, if LP can be of independent interest in Sage, why not
spending some time over it as I know how it works ?
Besides, in Sage I only have to care about the stuff that interests
me... If I need symbolics, plots, interfaces, I can ask people whose
interest lies there and they'll give me answer, sometimes solutions.
If they need anything dealing with Graphs, I'll do what I can.
Pretty naive, but so relieving :-)

Regards,

Nathann

[Jason Grout]

Nathann Cohen wrote:
>> Yes, you can use indexation like some_oovar[i] or some_oofun[i]
>> (probably with several indexes, or negative ones that are start from
>> array end), however, I think it should be avoided if possible (you'd
>> better split your oovar into several oovars).http://www.openopt.org/FuncDesignerDoc#Some_issues_to_be_aware
>
> I sent a message on sage-support to know to which extent I could use
> multivariate Polynomials in Sage to represent constraints and Linear
> functions, but it seems to be troublesome... This said, there is no
> way for me to use Linear Programming if I can not use indexed
> variables... At the moment, even though the syntax could be
> tremendously improved, I can use any hashable Sage object as a
> variable, and most of the time in Graph theoretic function my
> variables are edges, vertices, or arbitrary tuples and strings.
> Anyway, most of the Linear Programs are generated from graphs and I
> have to find a way to let a computer create as many variables as
> possible :-/
> The current syntax, though, is not nearly satisfying.
>

I should mention that at various times, people have proposed that you
could create symbolic variables x[1], x[2], etc. As far as I know,
these proposals have just been ideas and have never been implemented or
experimented with.

Maybe we could make x[1] a symbolic variable automatically. We would
have to make an indexing function for symbolic variables that would
return a symbolic variable that would be cached somewhere (so that x[1]
always referred to the same variable). That would also give us nested
indices, as x[1][1] would take a symbolic variable x, create a new one
x[1], and then x[1] would create another symbolic variable x[1][1].

Jason

[William Stein]

That sounds pretty easy to implement by defining __getitem__ for
symbolic variables, and making it cache its answer using a dictionary.
Should one only allow x[integer] or more generally x[anything
hashable]?

William

[Robert Bradshaw]

On Aug 26, 2009, at 3:47 PM, William Stein wrote:

I've advocated for this before--I think it's a great idea.

> Should one only allow x[integer] or more generally x[anything
> hashable]?

I would say x[anything symbolic]. Thus one could do

sage: var('x,a')
sage: x[a]
x[a]
sage: x[a].subs(a=1)
x[1]

I don't think x[a].subs(x=y) should be y[a], but you should be able
to sub for x[...] as a normal variable.

- Robert

[William Stein]

On Wed, Aug 26, 2009 at 7:56 PM, Robert
Bradshaw<robe...@math.washington.edu> wrote:
>>> x[1], and then x[1] would create another symbolic variable x[1][1].
>>>
>>
>> That sounds pretty easy to implement by defining __getitem__ for
>> symbolic variables, and making it cache its answer using a dictionary.
>
> I've advocated for this before--I think it's a great idea.
>
>>  Should one only allow x[integer] or more generally x[anything
>> hashable]?
>
> I would say x[anything symbolic]. Thus one could do
>
> sage: var('x,a')
> sage: x[a]
> x[a]
> sage: x[a].subs(a=1)
> x[1]
>
> I don't think x[a].subs(x=y) should be y[a], but you should be able
> to sub for x[...] as a normal variable.
>
> - Robert

Yes, this makes a lot of sense to me, since it's very common in
mathematics to have expressions like x_i, where i is some variable.
So would we have

sage: latex(x[3])
x_{3}

William

[dmitrey]

Maybe I misunderstood your question about indexed variables, you do
can create and use arrays of oovars and oofuns, eg
from FuncDesigner import *
N = 100
a = oovars(N) # create array of N oovars
b = oovars(N) # another array of N oovars
some_lin_funcs = [i*a[i]+4*i + 5*b[i] for i in xrange(N)]
f = some_lin_funcs[15] + some_lin_funcs[80]
point = {}
for i in xrange(N):
point[a[i]] = 1.5 * i**2
point[b[i]] = 1.5 * i**3
print f(point)
print a[15](point)
print some_lin_funcs[25](point)
# [ 4638755.]
# [ 337.5]
# [ 140725.]
Regards, D.

[Golam Mortuza Hossain]

Hi,

On Thu, Aug 27, 2009 at 1:00 AM, William Stein<wst...@gmail.com> wrote:
>
> On Wed, Aug 26, 2009 at 7:56 PM, Robert
> Bradshaw<robe...@math.washington.edu> wrote:
>>>> x[1], and then x[1] would create another symbolic variable x[1][1].
>>>>
>>>
>>> That sounds pretty easy to implement by defining __getitem__ for
>>> symbolic variables, and making it cache its answer using a dictionary.
>>
>> I've advocated for this before--I think it's a great idea.
>>
>

> Yes, this makes a lot of sense to me, since it's very common in
> mathematics to have expressions like x_i, where i is some variable.

Does GiNaC/pynac's native "indexed object" help here?

http://www.ginac.de/tutorial/Indexed-objects.html#Indexed-objects

If so then it may be a good idea to expose these to sage by wrapping
them suitably.

Cheers,
Golam

[Nicolas M. Thiery]

+1

> Should one only allow x[integer] or more generally x[anything
> hashable]?

+1 on anything hashable.

We (= the *-combinat people) often need to create systems of equations
with indeterminates indexed by various combinatorial objects (trees,
tableaux, permutations, ...). And in MuPAD we struggled all too often
because the various solvers did not support well such variables.