Opened 5 years ago
Closed 5 years ago
#18732 closed enhancement (fixed)
Add tableau query functions glp_eval_tab_row, glp_eval_tab_col to GLPK backend
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  numerical  Keywords:  LP, glpk 
Cc:  ncohen, yzh, zwang, jdemeyer  Merged in:  
Authors:  Yuan Zhou, Matthias Koeppe  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  3c0da60 (Commits)  Commit:  3c0da609a36bd5832cf6a9f11895e993971731c4 
Dependencies:  Stopgaps: 
Description
Expose the GLPK functions glp_eval_tab_row, glp_eval_tab_col in Sage's GLPKBackend class.
See GLPK manual, section 4.3 "Simplex tableau routines".
One needs these functions if one wants to implement tableau cutting planes such as Gomory's fractional cut.
Change History (23)
comment:1 Changed 5 years ago by
 Cc ncohen yzh added
comment:2 Changed 5 years ago by
 Cc zwang added
comment:3 Changed 5 years ago by
 Branch set to u/yzh/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend
comment:4 followup: ↓ 5 Changed 5 years ago by
 Commit set to 380dfb55b3966cd836fa1fbdc8325a9b3df8920e
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 5 years ago by
Bonjour Nathann,
Thanks for the reference! It says that sig_str
behaves the same as sig_on
. I just mimic the code in the GLPKBackend.solve
and GLPKBackend.row
methods.
Does one need to deallocate the memory if an Error is raised between sig_on
and sig_off
?
How to check that the pointers are not 'null'?
Yuan
comment:6 in reply to: ↑ 5 Changed 5 years ago by
Helloooooo,
Thanks for the reference! It says that
sig_str
behaves the same assig_on
.
Oh. My mistake. I did not notice sig_str
, and did not even know about it. Sorry.
Does one need to deallocate the memory if an Error is raised between
sig_on
andsig_off
?
Well, if you allocate memory somewhere and the function ends, then it is never deallocated. If you can avoid this easily, it is better to do it.
How to check that the pointers are not 'null'?
with "if my_pointer == NULL" ?
Nathann
comment:7 Changed 5 years ago by
 Commit changed from 380dfb55b3966cd836fa1fbdc8325a9b3df8920e to 1cf22a926b785affdf53e33ea30c539850ae406a
Branch pushed to git repo; I updated commit sha1. New commits:
1cf22a9  Fix memory leaks and check null pointer in eval_tab_row(), eval_tab_col().

comment:8 Changed 5 years ago by
 Status changed from new to needs_review
It now raises MIPSolverException
if GLPK returns an error message "basis factorization does not exist". Memory checks are also added. Please review.
comment:9 followup: ↓ 10 Changed 5 years ago by
 Status changed from needs_review to needs_work
+ cdef int * c_indices = <int*> sage_malloc((n+1)*sizeof(int)) + if c_indices == NULL: + raise MemoryError("failed to allocate %s bytes" % ((n+1)*sizeof(int))) + cdef double * c_values = <double*> sage_malloc((n+1)*sizeof(double)) + if c_values == NULL: + sage_free(c_indices) + raise MemoryError("failed to allocate %s bytes" % ((n+1)*sizeof(double)))
can be replaced by
+ cdef int * c_indices = <int*> sage_malloc((n+1)*sizeof(int)) + cdef double * c_values = <double*> sage_malloc((n+1)*sizeof(double)) + if c_indices == NULL or c_values == NULL: + raise MemoryError
This occurs twice.
for 0 < j <= i:
is "oldstyle", you should use "for j in range(i)" instead, which is translated into the very same C code.
Finally, this piece of code had bad sideeffects:
+ try: + sig_on() + i = glp_eval_tab_row(self.lp, k + 1, c_indices, c_values) + sig_off() + except Exception: + sage_free(c_indices) + sage_free(c_values) + raise MIPSolverException('GLPK : basis factorization does not exist')
Indeed, as it catches everything and only raises MIPSolverException, it can transform a KeyboardInterrupt? into a "GLPK: basis factorization does not exist". And of course the C function glp_eval_tab_row
cannot be expected to raise any exception.
I don't think that it is worth adding a sig_on/sig_off in this function, considering how short it is.
Nathann
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 5 years ago by
Replying to ncohen:
+ cdef int * c_indices = <int*> sage_malloc((n+1)*sizeof(int)) + if c_indices == NULL: + raise MemoryError("failed to allocate %s bytes" % ((n+1)*sizeof(int))) + cdef double * c_values = <double*> sage_malloc((n+1)*sizeof(double)) + if c_values == NULL: + sage_free(c_indices) + raise MemoryError("failed to allocate %s bytes" % ((n+1)*sizeof(double)))can be replaced by
+ cdef int * c_indices = <int*> sage_malloc((n+1)*sizeof(int)) + cdef double * c_values = <double*> sage_malloc((n+1)*sizeof(double)) + if c_indices == NULL or c_values == NULL: + raise MemoryErrorThis occurs twice.
Nathann, if the second allocation fails, your version would leak the memory of the first allocation.
for 0 < j <= i:
is "oldstyle", you should use "for j in range(i)" instead, which is translated into the very same C code.Finally, this piece of code had bad sideeffects:
+ try: + sig_on() + i = glp_eval_tab_row(self.lp, k + 1, c_indices, c_values) + sig_off() + except Exception: + sage_free(c_indices) + sage_free(c_values) + raise MIPSolverException('GLPK : basis factorization does not exist')Indeed, as it catches everything and only raises MIPSolverException, it can transform a KeyboardInterrupt? into a "GLPK: basis factorization does not exist". And of course the C function
glp_eval_tab_row
cannot be expected to raise any exception.I don't think that it is worth adding a sig_on/sig_off in this function, considering how short it is.
sig_on/sig_off catches all kinds of signals, and here it is used to catch SIGABRT, which GLPK invokes via abort() whenever there is an error.
Is there a way to distinguish which signal was caught?
comment:11 Changed 5 years ago by
 Cc jdemeyer added
comment:12 in reply to: ↑ 10 Changed 5 years ago by
Nathann, if the second allocation fails, your version would leak the memory of the first allocation.
Sorry, I wrote this yesterday evening just before going to sleep and I was exhausted:
+ cdef int * c_indices = <int*> sage_malloc((n+1)*sizeof(int)) + cdef double * c_values = <double*> sage_malloc((n+1)*sizeof(double)) + if c_indices == NULL or c_values == NULL: + sage_free(c_indices) + sage_free(c_values) + raise MemoryError
sig_on/sig_off catches all kinds of signals, and here it is used to catch SIGABRT, which GLPK invokes via abort() whenever there is an error.
Oh, okay. Sorry.
Is there a way to distinguish which signal was caught?
Just type "raise" instead of "raise <something>". It will raise what was caught. You can also use this model:
try: your_glpk_function(...) else: # only executed if everything went well <copy the C data wherever you need> finally: #whatever happens <free the memory> return <whatever you need>
Also, I don't think you should both with a loop of 'append'. Something like values = [c_values[j] for j in range(i)]
works fine.
Nathann
comment:13 Changed 5 years ago by
 Branch changed from u/yzh/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend to u/mkoeppe/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend
comment:14 Changed 5 years ago by
 Commit changed from 1cf22a926b785affdf53e33ea30c539850ae406a to 3eeebfcaf555629b3041d0ad4e10fd097365de65
Branch pushed to git repo; I updated commit sha1. New commits:
3eeebfc  Restructure with try..except..else..finally. Use list comprehension instead of append.

comment:15 Changed 5 years ago by
 Status changed from needs_work to needs_review
Thanks for the suggestions; I've made these changes. Needs review.
comment:16 followup: ↓ 18 Changed 5 years ago by
except Exception: raise
is useless, isn't it?
Could you also update the malloc blocks?
comment:17 Changed 5 years ago by
 Commit changed from 3eeebfcaf555629b3041d0ad4e10fd097365de65 to e2b25e2ace4888a84140b1f52165cea19653f9e0
comment:18 in reply to: ↑ 16 Changed 5 years ago by
Replying to ncohen:
except Exception: raise
is useless, isn't it?
You are right, of course. I've removed it.
Could you also update the malloc blocks?
Done.
comment:19 Changed 5 years ago by
 Reviewers set to Nathann Cohen
Hello !
I made some modifications, in a commit at public/18732:
 The first line of each docstring must be a short sentence describing what the function does
 Some inequations could be turned into latex formulas
 A row/col problem? Please check
 cdef int n = glp_get_num_rows(self.lp) + cdef int n = glp_get_num_cols(self.lp)
If you agree with this, you can set the ticket's status to positive_review
.
Nathann
P.S.: Please fill the 'author' field.
comment:20 Changed 5 years ago by
 Branch changed from u/mkoeppe/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend to public/18732
comment:21 followup: ↓ 22 Changed 5 years ago by
 Commit changed from e2b25e2ace4888a84140b1f52165cea19653f9e0 to 3c0da609a36bd5832cf6a9f11895e993971731c4
 Status changed from needs_review to positive_review
comment:22 in reply to: ↑ 21 Changed 5 years ago by
I have made another minor change to the docstrings to correctly reflect the type of exception that is raised.
+1
Nathann
comment:23 Changed 5 years ago by
 Branch changed from public/18732 to 3c0da609a36bd5832cf6a9f11895e993971731c4
 Resolution set to fixed
 Status changed from positive_review to closed
Hello !
Could you allocate memory *after* raising an exception? Otherwise, those exceptions trigger memory leaks.
sig_on
andsig_off
should always appear in pairs, but perhaps you should usesig_check
in this special case? http://www.sagemath.org/documentation/html/en/developer/coding_in_cython.html#interruptandsignalhandlingCan you check that the pointers you allocate are not 'null'?
Nathann
New commits:
Add tableau query functions eval_tab_row, eval_tab_col to GLPK backend.