Opened 5 years ago

Closed 5 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: sage-6.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 5 years ago by ncohen

  • Cc ncohen added

comment:2 Changed 5 years ago by ncohen

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.

comment:3 Changed 5 years ago by yzh

  • Branch set to u/yzh/add_basis_status_functions_get_col_stat__get_row_stat_to_glpk_backend

comment:4 Changed 5 years ago by mkoeppe

  • Commit set to e5c7095c35a0b278a4947ebd29db29d098face34
  • Status changed from new to needs_review

New commits:

e5c7095Add Sage interface for retrieving the basis status from GLPK

comment:5 Changed 5 years ago by ncohen

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

comment:6 Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:7 Changed 5 years ago by git

  • Commit changed from e5c7095c35a0b278a4947ebd29db29d098face34 to 49dba6a5cdb32dd49cd858e8a77cdfcfe361362c

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

49dba6aget_col_stat, get_row_stat: Add docstrings

comment:8 Changed 5 years ago by mkoeppe

  • Status changed from needs_work to needs_review

Doctests have been added; please review

comment:9 Changed 5 years ago by mkoeppe

  • Cc yzh added

comment:10 Changed 5 years ago by ncohen

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

Nathann

comment:11 follow-up: Changed 5 years ago by mkoeppe

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 sigon() / sigoff() 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.
------------------------------------------------------------------------
Version 1, edited 5 years ago by mkoeppe (previous) (next) (diff)

comment:12 in reply to: ↑ 11 Changed 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 49dba6a5cdb32dd49cd858e8a77cdfcfe361362c to e96bce575cd072f71325eb0cbb42410e068aeeb5

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

e96bce5check bounds for get_row_stat() and git_col_stat()

comment:14 Changed 5 years ago by ncohen

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

comment:15 Changed 5 years ago by git

  • Commit changed from e96bce575cd072f71325eb0cbb42410e068aeeb5 to 30eef17b1ce8cc81a6f493417a04deae8be64821

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

30eef17replace tab by spaces

comment:16 follow-up: Changed 5 years ago by ncohen

  • 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 5 years ago by yzh

  • Authors set to Yuan Zhou

comment:18 in reply to: ↑ 16 Changed 5 years ago by yzh

Thanks!

comment:19 Changed 5 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.