Opened 6 years ago
Closed 6 years ago
#18685 closed enhancement (fixed)
Add basis status functions get_col_stat, get_row_stat to GLPK backend
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  numerical  Keywords:  LP, glpk 
Cc:  ncohen, yzh  Merged in:  
Authors:  Yuan Zhou  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  30eef17 (Commits)  Commit:  30eef17b1ce8cc81a6f493417a04deae8be64821 
Dependencies:  Stopgaps: 
Description
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.
Change History (19)
comment:1 Changed 6 years ago by
 Cc ncohen added
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Branch set to u/yzh/add_basis_status_functions_get_col_stat__get_row_stat_to_glpk_backend
comment:4 Changed 6 years ago by
 Commit set to e5c7095c35a0b278a4947ebd29db29d098face34
 Status changed from new to needs_review
New commits:
e5c7095  Add Sage interface for retrieving the basis status from GLPK

comment:5 Changed 6 years ago by
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#documentationstrings
Nathann
comment:6 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:7 Changed 6 years ago by
 Commit changed from e5c7095c35a0b278a4947ebd29db29d098face34 to 49dba6a5cdb32dd49cd858e8a77cdfcfe361362c
Branch pushed to git repo; I updated commit sha1. New commits:
49dba6a  get_col_stat, get_row_stat: Add docstrings

comment:8 Changed 6 years ago by
 Status changed from needs_work to needs_review
Doctests have been added; please review
comment:9 Changed 6 years ago by
 Cc yzh added
comment:10 Changed 6 years ago by
Could you protect against reading outofbounds constraints? Right now it crashes Sage. Could you also add a doctest for that?
Nathann
comment:11 followup: ↓ 12 Changed 6 years ago by
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. 
comment:12 in reply to: ↑ 11 Changed 6 years ago by
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
comment:13 Changed 6 years ago by
 Commit changed from 49dba6a5cdb32dd49cd858e8a77cdfcfe361362c to e96bce575cd072f71325eb0cbb42410e068aeeb5
Branch pushed to git repo; I updated commit sha1. New commits:
e96bce5  check bounds for get_row_stat() and git_col_stat()

comment:14 Changed 6 years ago by
Looks good! The patchbot complains that there are 'tab' characters in glpk_backend.pxd
, however.
comment:15 Changed 6 years ago by
 Commit changed from e96bce575cd072f71325eb0cbb42410e068aeeb5 to 30eef17b1ce8cc81a6f493417a04deae8be64821
Branch pushed to git repo; I updated commit sha1. New commits:
30eef17  replace tab by spaces

comment:16 followup: ↓ 18 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Gooooooood to go!
Nathann
P.S.: Please fill the "Author" field with your full name
comment:17 Changed 6 years ago by
comment:18 in reply to: ↑ 16 Changed 6 years ago by
Thanks!
comment:19 Changed 6 years ago by
 Branch changed from u/yzh/add_basis_status_functions_get_col_stat__get_row_stat_to_glpk_backend to 30eef17b1ce8cc81a6f493417a04deae8be64821
 Resolution set to fixed
 Status changed from positive_review to closed
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.