Opened 4 years ago

Closed 4 years ago

#18764 closed enhancement (fixed)

Add glp_exact to Sage's GLPK bindings

Reported by: mkoeppe Owned by:
Priority: minor Milestone: sage-6.8
Component: numerical Keywords: lp
Cc: yzh, dimpase, ncohen Merged in:
Authors: Matthias Koeppe, Yuan Zhou Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 37fbc4a (Commits) Commit: 37fbc4a584357929e60af73e16af81abea225303
Dependencies: Stopgaps:

Description (last modified by 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.)

Change History (15)

comment:1 follow-up: Changed 4 years ago by 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?

comment:2 in reply to: ↑ 1 Changed 4 years ago by 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.

comment:3 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/add_glp_exact_to_sage_s_glpk_bindings

comment:4 Changed 4 years ago by mkoeppe

  • Commit set to 1ec429b9715686740a905465a7d1f6a0def5f899
  • Description modified (diff)
  • Status changed from new to needs_review

Needs review.


New commits:

1ec429bHave solve call glp_exact if requested by solver parameter simplex_or_intopt

comment:5 Changed 4 years ago by git

  • Commit changed from 1ec429b9715686740a905465a7d1f6a0def5f899 to a2107971bbc31ca00d655ccc18d623cba2aa9ee4

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

a210797Have solve call glp_exact if requested by solver parameter simplex_or_intopt

comment:6 Changed 4 years ago by git

  • Commit changed from a2107971bbc31ca00d655ccc18d623cba2aa9ee4 to 288d33a226f9b3504418e072e51a0f1083af2503

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

288d33aAdd a discussion of simplex, followed by exact simplex to docstrings

comment:7 Changed 4 years ago by mkoeppe

  • Authors set to Matthias Koeppe

comment:8 Changed 4 years ago by yzh

  • Branch changed from u/mkoeppe/add_glp_exact_to_sage_s_glpk_bindings to u/yzh/add_glp_exact_to_sage_s_glpk_bindings

comment:9 Changed 4 years ago by git

  • Commit changed from 288d33a226f9b3504418e072e51a0f1083af2503 to 37fbc4a584357929e60af73e16af81abea225303

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

37fbc4aUpdate docsting of solve_parameter()

comment:10 Changed 4 years ago by mkoeppe

  • Authors changed from Matthias Koeppe to Matthias Koeppe, Yuan Zhou

comment:11 Changed 4 years ago by dimpase

  • Status changed from needs_review to positive_review

OK, looks good

comment:12 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name

comment:13 Changed 4 years ago by mkoeppe

  • Reviewers set to Dmitrii Pasechnik
  • Status changed from needs_work to positive_review

comment:14 Changed 4 years ago by dimpase

  • Reviewers changed from Dmitrii Pasechnik to Dima Pasechnik

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

comment:15 Changed 4 years ago by vbraun

  • Branch changed from u/yzh/add_glp_exact_to_sage_s_glpk_bindings to 37fbc4a584357929e60af73e16af81abea225303
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.