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

[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

There are several versions around:

• http://www.math.uwaterloo.ca/~bico/qsopt/ex/ reports 2.6 (090408) as the latest
• https://github.com/jonls/qsopt-ex is a fork, off version 2.5.10 (this also has a Python module at:
  https://github.com/jonls/python-qsoptex). Last release tag 2.5.10.3 Apr 2015, last change July 2017.
• Debian packages something based on that version, called 2.5.10.3+ds. Info:
  • https://salsa.debian.org/med-team/qsopt-ex/blob/master/debian/README.Debian
  • https://salsa.debian.org/med-team/qsopt-ex/blob/master/debian/copyright
  • a version of QSopt_ex is also used by an exact version of the SCIP MIP solver. http://scip.zib.de/#exact (Dan Steffy advises: The exactip branch of SCIP should build with a few different version of QSopt_ex, I think the suggested one is 2.5.10, details and special installation options should be in the installation instructions.)

See also:

• Meta-ticket: Use Python optimization interfaces: CVXPY, SCIP, or-tools, PuLP, Pyomo, cylp... #26511: Meta-ticket: Use Python optimization interfaces: PuLP, Pyomo, cylp...

CC: @yuan-zhou @dimpase @nathanncohen bico@jhu.edu

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/18766

[dimpase]

comment:1

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

[dimpase]

comment:2

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.

[mkoeppe]

comment:3

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

[mkoeppe]

comment:4

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

[mkoeppe]

comment:8

Replying to @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

2020 update: this SVN is no longer accessible.