Opened 4 years ago

Last modified 4 years ago

#18766 new enhancement

Add bindings, MixedIntegerLinearProgram backend to qsopt_ex, a state-of-the-art exact simplex solver

Reported by: mkoeppe Owned by:
Priority: minor Milestone: sage-6.8
Component: numerical Keywords: lp
Cc: yzh, dimpase, ncohen Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mkoeppe)

Qsopt_ex is a state-of-the-art exact simplex solver by David Applegate, William Cook, Sanjeeb Dash, and Daniel Espinoza. Paper: http://www.dii.uchile.cl/~daespino/files/exact_simplex.pdf

Not sure which version we should use:

Change History (5)

comment:1 follow-up: Changed 4 years ago by dimpase

Perhaps asking the fork author why he went with this version might make sense. The fork does not look like it is much older than the git repo, and 2.6 was already available for years...

The Python module is actually a Cython module, which is good (but it does not have the full interface, only reading/writing files).

comment:2 Changed 4 years ago by dimpase

Actually, QSoptExact.tar.bz2 with "full development version" expands into a directory QSopt_ex-2.5.10/, with many files dated as late as 2012, and so this looks like 2.6 doesn't really exist.

There is also a mentioning in README of an SVN server where all that stuff is: https://conexo.dii.uchile.cl/SVN/ESolver

There is a 2.5 branch, and a 3.0 branch (and probably old 1.0 branch). But no 2.6.

comment:3 in reply to: ↑ 1 Changed 4 years ago by mkoeppe

Replying to dimpase:

Perhaps asking the fork author why he went with this version might make sense. The fork does not look like it is much older than the git repo, and 2.6 was already available for years...

The Python module is actually a Cython module, which is good (but it does not have the full interface, only reading/writing files).

I asked the author of the fork, Jon Lund Steffensen, and he replied as follows; I'm posting it here with his permission.

It is based on 2.5.10 available here as the "full development code": http://www.math.uwaterloo.ca/~bico/qsopt/ex/ . To my knowledge this is the most recent release that includes all code. Here's the NEWS file with a quick overview of the changes I made: https://github.com/jonls/qsopt-ex/blob/master/NEWS.md . It seemed to me that the original project was no longer maintained so I created the fork.

When I started using QSopt_ex as a library I realized that it was not very usable as a library. The header files were a huge mess of internal and public interfaces mixed together. The build system was based on custom Makefiles that didn't quite work on the platforms I wanted to build the library on. I changed the build system to be based on autoconf/automake/libtool for better portability. The library had an external dependency on EGlib, another libsary that appears to be unmaintained. Since only a tiny subset of EGlib was used by QSopt_ex, I decided to simply copy the code into QSopt_ex.

The build system used a custom templating system for generating the code for different numeric types. This was extremely slow because any change to a source file would cause a regeneration of all of the templated files. I changed that to a simpler system which also removed the build dependencies on GNU sed and Exuberant ctags.

I added a Cython-based Python module to access the library, though it has moved to a separate repository on Github. Lastly, I changed the logging output to stdout/stderr from the library to go through a logging function. In an application that was using the library I was writing an output file to stdout. Since QSopt_ex would simply dump all logging output to stdout as well it would mess up my output files. I added a function to the library that allows the user to redirect the logging output to any destination.

comment:4 Changed 4 years ago by mkoeppe

The 3.0 branch on that svn server mentions a license change from GPL to LGPL:

https://conexo.dii.uchile.cl/SVN/ESolver/branches/QSopt_ex-3.0/README

comment:5 Changed 4 years ago by mkoeppe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.