Add glp_exact to Sage's GLPK bindings

[mkoeppe]

The function glp_exact provides access to an implementation of the simplex method in exact rational arithmetic (using GMP).

The only access to data is via double-precision floats, however. It reconstructs rationals from doubles and provides results as doubles using the standard API functions of GLPK.

On the Sage side, since the combinatorial basis information is available via get_col_stat, get_row_stat, one could then reconstruct the rational solution. See #18735.

(Direct access, using GMP rationals, would be possible through the header file glpssx.h; see ticket #18765.)

[dimpase]

copying from a comment on another ticket:

I don't think using non-public non-documented features is a good idea. Next version would break them, and we'd be stuck with maintaining a fork... Perhaps we have to find a way first to make GLPK folks finally address the public need of making these things public?

[mkoeppe]

Hi Dima,

Replying to dimpase:

copying from a comment on another ticket:

I don't think using non-public non-documented features is a good idea. Next version would break them, and we'd be stuck with maintaining a fork... Perhaps we have to find a way first to make GLPK folks finally address the public need of making these things public?

I share your concern about the non-public functions, which is valid for the other ticket (#18765), but *not* for this ticket.

glp_exact is a documented API function.

There's just no way to feed the problem using exact data, or to retrieve the solution using exact data. However, if the problem can be expressed using small integers (<= 53 bits) that are represented exactly by double floats, then the rational reconstruction that GLPK does should be exact. The Sage code could refuse, or warn, if this is violated.

And we can access the combinatorial information about the basis on the Sage side and compute the basic solution using exact arithmetic.

[mkoeppe]

Needs review.

---

New commits:

​1ec429b

Have solve call glp_exact if requested by solver parameter simplex_or_intopt

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a210797

Have solve call glp_exact if requested by solver parameter simplex_or_intopt

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​288d33a

Add a discussion of simplex, followed by exact simplex to docstrings

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​37fbc4a

Update docsting of solve_parameter()

[dimpase]

OK, looks good

[vbraun]

Reviewer name

[dimpase]

I plan to learn some trac internals, and perhaps I'll be able to implement automatic filling of fields ;-)