Add tableau query functions glp_eval_tab_row, glp_eval_tab_col to GLPK backend

[mkoeppe]

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.

CC: @nathanncohen @yuan-zhou @uduse @jdemeyer

Component: numerical

Keywords: glpk

Author: Yuan Zhou, Matthias Koeppe

Branch/Commit: 3c0da60

Reviewer: Nathann Cohen

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

[yuan-zhou]

Changed author from ncohen, yzh to none

[yuan-zhou]

Branch: u/yzh/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend

[nathanncohen]

Commit: 380dfb5

[nathanncohen]

comment:4

Hello !

Could you allocate memory after raising an exception? Otherwise, those exceptions trigger memory leaks.

sig_on and sig_off should always appear in pairs, but perhaps you should use sig_check in this special case?
http://www.sagemath.org/documentation/html/en/developer/coding_in_cython.html#interrupt-and-signal-handling

Can you check that the pointers you allocate are not 'null'?

Nathann

---

New commits:

380dfb5

Add tableau query functions eval_tab_row, eval_tab_col to GLPK backend.

[yuan-zhou]

comment:5

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

[nathanncohen]

comment:6

Helloooooo,

Thanks for the reference! It says that sig_str behaves the same as sig_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 and sig_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

[sagetrac-git]

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().

[sagetrac-git]

Changed commit from 380dfb5 to 1cf22a9

[yuan-zhou]

comment:8

It now raises MIPSolverException if GLPK returns an error message "basis factorization does not exist". Memory checks are also added. Please review.

[nathanncohen]

comment:9

+        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 "old-style", 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 side-effects:

+        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

[mkoeppe]

comment:10

Replying to @nathanncohen:

+        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.

Nathann, if the second allocation fails, your version would leak the memory of the first allocation.

for 0 < j <= i: is "old-style", 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 side-effects:

+        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?

[nathanncohen]

comment:12

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 ". 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