Add basis status functions get_col_stat, get_row_stat to GLPK backend

[mkoeppe]

Expose the GLPK functions get_col_stat, get_row_stat in Sage's GLPKBackend class.

These functions are essential for any serious linear programming.
For example, if one wants to extract the exact rational basic solution from the dictionary, one needs the information returned by these functions.

CC: @nathanncohen @yuan-zhou

Component: numerical

Keywords: glpk

Author: Yuan Zhou

Branch/Commit: 30eef17

Reviewer: Nathann Cohen

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

[nathanncohen]

comment:2

I am curious to know how you would use it in Sage, but you will not have any problem exposing them. That's easy Cython.

[yuan-zhou]

Branch: u/yzh/add_basis_status_functions_get_col_stat__get_row_stat_to_glpk_backend

[mkoeppe]

Commit: e5c7095

[mkoeppe]

New commits:

e5c7095

Add Sage interface for retrieving the basis status from GLPK

[nathanncohen]

comment:5

Your code needs documentation and doctests. You can mimic what is done on the other functions of the same file, and will find some documentation here:

http://doc.sagemath.org/html/en/developer/coding_basics.html#documentation-strings

Nathann

[sagetrac-git]

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

49dba6a

get_col_stat, get_row_stat: Add docstrings

[sagetrac-git]

Changed commit from e5c7095 to 49dba6a

[mkoeppe]

comment:8

Doctests have been added; please review

[nathanncohen]

comment:10

Could you protect against reading out-of-bounds constraints? Right now it crashes Sage. Could you also add a doctest for that?

Nathann

[mkoeppe]

comment:11

I am not sure if this ticket is the right place to introduce bounds checking for these functions.
Other GLPK backend functions don't do that either (below is an example) -- after all, GLPK does check the bounds; it only chooses to terminate the process with abort()....

Does this rather need to be handled with sig_on() / sig_off() somehow?

sage: lp.add_linear_constraint(zip([0, 1, 2], [8, 6, 1]), None, 48)
sage: lp.add_linear_constraint(zip([0, 1, 2], [4, 2, 1.5]), None, 20)
sage: lp.add_linear_constraint(zip([0, 1, 2], [2, 1.5, 0.5]), None, 8)
sage: lp.set_objective([60, 30, 20])
sage: import sage.numerical.backends.glpk_backend as backend
sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only)
sage: lp.solve()
sage: lp.get_variable_value(-1)
glp_get_col_prim: j = 0; column number out of range
Error detected in file glpapi06.c at line 739
------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Sage will now terminate.
------------------------------------------------------------------------

[nathanncohen]

comment:12

I am not sure if this ticket is the right place to introduce bounds checking for these functions.

If you are ready to pay for a Python function call, you may as well avoid segfaults.

Other GLPK backend functions don't do that either (below is an example)

Oh. Right. Well, that's because we hardly ever use this function by giving it integers, I'd say. We always give it symbolic LP variable, for which it is not a problem. You can fix both here if you like, but you should at least make the one you introduce check for this.

Does this rather need to be handled with sig_on() / sig_off() somehow?

No, sig_on/sig_off is only meant to handle KeyboardInterrupt.

Nathann

[sagetrac-git]

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

e96bce5

check bounds for get_row_stat() and git_col_stat()

[sagetrac-git]

Changed commit from 49dba6a to e96bce5

[nathanncohen]

comment:14

Looks good! The patchbot complains that there are 'tab' characters in glpk_backend.pxd, however.

[sagetrac-git]

Changed commit from e96bce5 to 30eef17

[sagetrac-git]

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

30eef17

replace tab by spaces

[nathanncohen]

comment:16

Gooooooood to go!

Nathann

P.S.: Please fill the "Author" field with your full name

[nathanncohen]

Reviewer: Nathann Cohen

[yuan-zhou]

Author: Yuan Zhou

[yuan-zhou]

comment:18

Thanks!

[vbraun]

Changed branch from u/yzh/add_basis_status_functions_get_col_stat__get_row_stat_to_glpk_backend to 30eef17