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.

[ncohen]

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.

[yzh]

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

[ncohen]

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

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

[yzh]

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

[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 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]

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

[ncohen]

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

[git]

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

​3eeebfc

Restructure with try..except..else..finally. Use list comprehension instead of append.

[mkoeppe]

Thanks for the suggestions; I've made these changes. Needs review.

[ncohen]

except Exception: raise is useless, isn't it?

Could you also update the malloc blocks?

[git]

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

​268eceb	Simplify memory allocation
​e2b25e2	Simplify try statements

[mkoeppe]

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.

[ncohen]

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.

[mkoeppe]

I agree with your changes. Thanks!

I have made another minor change to the docstrings to correctly reflect the type of exception that is raised.

---

New commits:

​f5a1561	trac #18732: superficial changes
​3c0da60	Update docstrings regarding exceptions raised

[ncohen]

I have made another minor change to the docstrings to correctly reflect the type of exception that is raised.

+1

Nathann