linear programming via lp_solve in sage

81 views
Skip to first unread message

peno

unread,
Apr 11, 2009, 6:47:33 AM4/11/09
to sage-devel
I am one of the developers of lp_solve, an open-source mixed integer
linear
programming solver. See http://lpsolve.sourceforge.net/5.5/ for the
reference guide.

lp_solve has a very rich API to model and solve MILP models.
The API is contained in a library (written in C) that can be called
from
almost any language.
There are also interfaces written for some higher level packages such
as
MatLab, O-Matrix, Octave, Scilab, FreeMat, SysQuake, Python, PHP, R,
AMPL
and others in the make.
These packages all have the concept of vectors, matrices and lp_solve
can be
called from them as it is integrated in the package.
See for example the MatLab reference:
http://lpsolve.sourceforge.net/5.5/MATLAB.htm.
Vectors and matrices can directly be passed between the package and
lp_solve.

I came acros Sage a couple of days ago and I think it would be an
added
value for both Sage and lp_solve to integrate them also.

I looked in the Sage tutorial and documentation and have seen that it
is
possible to call functions from a library or even C-code, but I have 2
questions about it.

- Each time, Sage is restarted a recompilation is done. Isn't there a
way
that there is only one compilation?
- The small demo program interfaces only with a single variable. It is
possible to pass vectors and matrices to the library? How is that
done? Is
there documentation on this? There is for example the integration
between
Sage and Maxima. It it possible to the same with lp_solve?

Best regards,

Peter Notebaert

Jason Grout

unread,
Apr 11, 2009, 8:01:08 AM4/11/09
to sage-...@googlegroups.com


Every time you rebuild Sage (i.e., sage -br), a recompilation should
happen. However, it shouldn't happen every time you start up sage. Can
you post the output of what you are seeing?

> - The small demo program interfaces only with a single variable. It is
> possible to pass vectors and matrices to the library? How is that
> done? Is
> there documentation on this? There is for example the integration
> between
> Sage and Maxima. It it possible to the same with lp_solve?


Since lp_solve is a C library, probably the easiest way to interface
with it is to write a Cython interface. A Cython function would easily
be able to take a vector or matrix and pass a C array to lp_solve, for
example. I think the place to look for examples of interfaces to C
libraries is in the sage/devel/sage/sage/libs directory. Someone else
will have to chime in as to which interface might be the most ideal
example of a C library wrapper.

I also notice above that you have an interface for python. You could
(probably more immediately) just write a Sage function that calls that
python function. However, writing a Cython wrapper will probably yield
faster results in the end, and shouldn't be too hard.

Thanks for your work!

Jason

--
Jason Grout


David Joyner

unread,
Apr 11, 2009, 2:42:11 PM4/11/09
to sage-...@googlegroups.com
The paper http://www.lehigh.edu/~tkr2/research/papers/MILP04.pdf
provides a survey of "non-commercial" LP solvers. It appears
that COIN-OR's Symphany package solves a wider class of
problems by that (in one comparison at least) lp_solve is relatively
fast. Do you agree? Can you offer other comparisons with
Symphany?

Sage currently ships only with cvxopt but, AFAIK, cvxopt does not
handle MILPs.

Jason mentioned a Cython wrapper. Another possibility is a
Python wrapper (see modules in
http://hg.sagemath.org/sage-main/file/5c72dbb92d82/sage/interfaces
for examples), if the Cython gets too complicated. See also
http://www.sagemath.org/doc/developer/producing_spkgs.html

Thanks for your interest in Sage!

Robert Schwarz

unread,
Apr 11, 2009, 3:38:33 PM4/11/09
to sage-...@googlegroups.com
David Joyner wrote:
> The paper http://www.lehigh.edu/~tkr2/research/papers/MILP04.pdf
> provides a survey of "non-commercial" LP solvers. It appears
> that COIN-OR's Symphany package solves a wider class of
> problems by that (in one comparison at least) lp_solve is relatively
> fast. Do you agree? Can you offer other comparisons with
> Symphany?
>
> Sage currently ships only with cvxopt but, AFAIK, cvxopt does not
> handle MILPs.
>

See also http://wiki.sagemath.org/optimization for plans to include solvers
in Sage. I've just read a benchmark paper comparing lp_solve, glpk and
Coin-Or's clp, the last always winning by 1 or 2 orders of magnitude in
computation time, but it's from 2006, so maybe a bit dated.


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

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

signature.asc

Stephen Hartke

unread,
Apr 11, 2009, 11:25:06 PM4/11/09
to sage-...@googlegroups.com
I have made an spkg for lp_solve and posted to sage-devel a message in September 2008 about including it into Sage.  I did not receive any positive responses.  The spkg and a demo file domination.py can be downloaded at:
http://www.math.unl.edu/~shartke2/files/

Since the developers of lp_solve have already created a Python interface to the C library, I think that we should just use that.  In my experience it works quite well.

Since lp_solve is licensed under GPLv2.1, it can be included in Sage.  Both COIN (under the CPL) and GPLK (under GPLv3) have license issues.  If we want decent LP/IP capabilities in Sage without writing everything from scratch, I think that lp_solve is the best package.

Best wishes,
Stephen

David Joyner

unread,
Apr 12, 2009, 9:45:15 AM4/12/09
to sage-...@googlegroups.com
On Sat, Apr 11, 2009 at 11:25 PM, Stephen Hartke <har...@gmail.com> wrote:
> I have made an spkg for lp_solve and posted to sage-devel a message in
> September 2008 about including it into Sage.  I did not receive any positive
> responses.  The spkg and a demo file domination.py can be downloaded at:
> http://www.math.unl.edu/~shartke2/files/


I missed that. Where is a readme or something what explains the basic commands
with examples?


>
> Since the developers of lp_solve have already created a Python interface to
> the C library, I think that we should just use that.  In my experience it
> works quite well.
>
> Since lp_solve is licensed under GPLv2.1, it can be included in Sage.  Both
> COIN (under the CPL) and GPLK (under GPLv3) have license issues.  If we want


Please explain these!

Stephen Hartke

unread,
Apr 12, 2009, 12:25:36 PM4/12/09
to sage-...@googlegroups.com
On Sun, Apr 12, 2009 at 8:45 AM, David Joyner <wdjo...@gmail.com> wrote:

On Sat, Apr 11, 2009 at 11:25 PM, Stephen Hartke <har...@gmail.com> wrote:
> I have made an spkg for lp_solve and posted to sage-devel a message in
> September 2008 about including it into Sage.  I did not receive any positive
> responses.  The spkg and a demo file domination.py can be downloaded at:
> http://www.math.unl.edu/~shartke2/files/

I missed that. Where is a readme or something what explains the basic commands
with examples?

I did not create separate documentation since I think the lp_solve documentation of its Python interface is well done.  The documentation can be found here:
http://lpsolve.sourceforge.net/5.5/Python.htm

The demo file domination.py shows how to use lp_solve along with Sage's graph classes to compute the domination number of a graph.
 
> Since lp_solve is licensed under GPLv2.1, it can be included in Sage.  Both
> COIN (under the CPL) and GPLK (under GPLv3) have license issues.  If we want

Please explain these!

COIN is licensed under the Common Public License (CPL), which is deemed to be GPLv2 incompatible; see Wikipedia for a summary.
http://en.wikipedia.org/wiki/Common_Public_License

GPLK is an official GNU project and is licensed under GPLv3.  The GPLv3 is incompatible with GPLv2-only licensed projects, which Sage mostly is.  From my understanding of discussions on the mailing lists, Sage will not be incorporating GPLv3 projects.

Besides lp_solve, I do not know of any other open source LP/IP packages that have a compatible license.  Perhaps there are others that I am not aware of.

Best wishes,
Stephen

David Joyner

unread,
Apr 12, 2009, 5:13:01 PM4/12/09
to sage-...@googlegroups.com
On Sun, Apr 12, 2009 at 12:25 PM, Stephen Hartke <har...@gmail.com> wrote:
> On Sun, Apr 12, 2009 at 8:45 AM, David Joyner <wdjo...@gmail.com> wrote:
>>
>> On Sat, Apr 11, 2009 at 11:25 PM, Stephen Hartke <har...@gmail.com> wrote:
>> > I have made an spkg for lp_solve and posted to sage-devel a message in
>> > September 2008 about including it into Sage.  I did not receive any
>> > positive
>> > responses.  The spkg and a demo file domination.py can be downloaded at:
>> > http://www.math.unl.edu/~shartke2/files/


The spkg installs fine and seems to run as expected (using amd64 ubuntu).



>
> I did not create separate documentation since I think the lp_solve
> documentation of its Python interface is well done.  The documentation can
> be found here:
> http://lpsolve.sourceforge.net/5.5/Python.htm


Is the documentation http://lpsolve.sourceforge.net/5.5/index.htm
licensed GFDL or what? (Or is the user expected to have an internet connection?)
I did not see it in the download (though it says on the page
http://lpsolve.sourceforge.net/5.5/Intro.htm
that lp_solve "It contains full source, examples and manuals."


>

...

>
> Besides lp_solve, I do not know of any other open source LP/IP packages that
> have a compatible license.  Perhaps there are others that I am not aware of.

Robert Schwartz mentioned http://wiki.sagemath.org/optimization which
has a list of
several active LP projects. I missed lp_solve somehow when I drafted that
but it has just been added now. You'll see others packages listed,
such as abacus
which is LGPL.

As mentioned earlier in the thread, Sage does include cvxopt, which is GPLv3+.


>
> Best wishes,
> Stephen
>
>
> >
>

mabshoff

unread,
Apr 12, 2009, 5:23:15 PM4/12/09
to sage-devel


On Apr 12, 2:13 pm, David Joyner <wdjoy...@gmail.com> wrote:
> On Sun, Apr 12, 2009 at 12:25 PM, Stephen Hartke <har...@gmail.com> wrote:

<SNIP>

> As mentioned earlier in the thread, Sage does include cvxopt, which is GPLv3+.

While the latest release is GPL V3+ the version we ship is GPL V+.

Cheers,

Michael

peno

unread,
Apr 12, 2009, 6:13:49 PM4/12/09
to sage-devel
On http://lpsolve.sourceforge.net/5.5/, there is in the index left an
item 'Download'
That directs you to http://sourceforge.net/project/showfiles.php?group_id=145213&package_id=159735
with all downloads. Also the documentation in HTML or HTML help format
is there. The latest documentation is also on http://lpsolve.sourceforge.net/5.5/
for the users convenience.

Peter

On Apr 12, 11:13 pm, David Joyner <wdjoy...@gmail.com> wrote:
> On Sun, Apr 12, 2009 at 12:25 PM, Stephen Hartke <har...@gmail.com> wrote:
> > On Sun, Apr 12, 2009 at 8:45 AM, David Joyner <wdjoy...@gmail.com> wrote:
>
> >> On Sat, Apr 11, 2009 at 11:25 PM, Stephen Hartke <har...@gmail.com> wrote:
> >> > I have made an spkg for lp_solve and posted to sage-devel a message in
> >> > September 2008 about including it into Sage.  I did not receive any
> >> > positive
> >> > responses.  The spkg and a demo file domination.py can be downloaded at:
> >> >http://www.math.unl.edu/~shartke2/files/
>
> The spkg installs fine and seems to run as expected (using amd64 ubuntu).
>
>
>
> > I did not create separate documentation since I think the lp_solve
> > documentation of its Python interface is well done.  The documentation can
> > be found here:
> >http://lpsolve.sourceforge.net/5.5/Python.htm
>
> Is the documentationhttp://lpsolve.sourceforge.net/5.5/index.htm
> licensed GFDL or what? (Or is the user expected to have an internet connection?)
> I did not see it in the download (though it says on the pagehttp://lpsolve.sourceforge.net/5.5/Intro.htm

David Joyner

unread,
Apr 12, 2009, 6:34:50 PM4/12/09
to sage-...@googlegroups.com
On Sun, Apr 12, 2009 at 6:13 PM, peno <pen...@gmail.com> wrote:
>
> On http://lpsolve.sourceforge.net/5.5/, there is in the index left an
> item 'Download'
> That directs you to http://sourceforge.net/project/showfiles.php?group_id=145213&package_id=159735
> with all downloads. Also the documentation in HTML or HTML help format
> is there. The latest documentation is also on http://lpsolve.sourceforge.net/5.5/
> for the users convenience.


Thanks. It is the file lp_solve_5.5.0.14_doc.tar.gz. (Warning: It does
not extract into
its own subdirectory, so you have to create a subdirectory doc of lp_solve*
and copy it there before extracting it.) There is no index.html file.
The main file
appears to be contents.htm.

Uncompressed the documention is <5M. Uncompressed the source code is
<4M.


>
> Peter
>
...

>>
>> Is the documentationhttp://lpsolve.sourceforge.net/5.5/index.htm
>> licensed GFDL or what? (Or is the user expected to have an internet connection?)
>> I did not see it in the download (though it says on the pagehttp://lpsolve.sourceforge.net/5.5/Intro.htm
>> that lp_solve "It contains full source, examples and manuals."


There is no LICENSE or COPYING file or any indiction of what the distribution
license of the documentation is.


>>
>>
>>

peno

unread,
Apr 12, 2009, 6:50:02 PM4/12/09
to sage-devel
Everything of lp_solve is LGPL, so also the documentation.

And there is an index.htm

Peter

On Apr 13, 12:34 am, David Joyner <wdjoy...@gmail.com> wrote:
> On Sun, Apr 12, 2009 at 6:13 PM, peno <pen...@gmail.com> wrote:
>
> > Onhttp://lpsolve.sourceforge.net/5.5/, there is in the index left an
> > item 'Download'
> > That directs you tohttp://sourceforge.net/project/showfiles.php?group_id=145213&package_...
> > with all downloads. Also the documentation in HTML or HTML help format
> > is there. The latest documentation is also onhttp://lpsolve.sourceforge.net/5.5/

Stephen Hartke

unread,
May 3, 2009, 4:02:46 PM5/3/09
to sage-...@googlegroups.com
I have updated the lp_solve spkg to the latest version, lp_solve 5.5.0.14.  I have also included the documentation files, which I install into $SAGE_LOCAL/share/doc/lp_solve-5.5.014.  Is this the correct location for documentation files?

The updated spkg is located at
http://www.math.unl.edu/~shartke2/files/

If there is sufficient interest, I can create a trac ticket for the inclusion of this spkg into Sage.

Best wishes,
Stephen

William Stein

unread,
May 4, 2009, 12:26:06 AM5/4/09
to sage-...@googlegroups.com
+1 that's a great idea.

William

Reply all
Reply to author
Forward
0 new messages