Opened 4 years ago

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

  • Authors ncohen, yzh deleted
  • Cc ncohen yzh added

comment:2 Changed 4 years ago by mkoeppe

  • Cc zwang added

comment:3 Changed 4 years ago by yzh

  • Branch set to u/yzh/add_tableau_query_functions_glp_eval_tab_row__glp_eval_tab_col_to_glpk_backend

comment:4 follow-up: Changed 4 years ago by ncohen

  • Commit set to 380dfb55b3966cd836fa1fbdc8325a9b3df8920e

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:

380dfb5Add tableau query functions eval_tab_row, eval_tab_col to GLPK backend.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by 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

comment:6 in reply to: ↑ 5 Changed 4 years ago by 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

comment:7 Changed 4 years ago by git

  • Commit changed from 380dfb55b3966cd836fa1fbdc8325a9b3df8920e to 1cf22a926b785affdf53e33ea30c539850ae406a

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

1cf22a9Fix memory leaks and check null pointer in eval_tab_row(), eval_tab_col().

comment:8 Changed 4 years ago by yzh

  • 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 follow-up: Changed 4 years ago by ncohen

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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by 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?

comment:11 Changed 4 years ago by mkoeppe

  • Cc ​jdemeyer added

comment:12 in reply to: ↑ 10 Changed 4 years ago by 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

comment:13 Changed 4 years ago by mkoeppe

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

  • Commit changed from 1cf22a926b785affdf53e33ea30c539850ae406a to 3eeebfcaf555629b3041d0ad4e10fd097365de65

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

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

comment:15 Changed 4 years ago by mkoeppe

  • Status changed from needs_work to needs_review

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

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

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

Could you also update the malloc blocks?

comment:17 Changed 4 years ago by git

  • Commit changed from 3eeebfcaf555629b3041d0ad4e10fd097365de65 to e2b25e2ace4888a84140b1f52165cea19653f9e0

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

268ecebSimplify memory allocation
e2b25e2Simplify try statements

comment:18 in reply to: ↑ 16 Changed 4 years ago by 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.

comment:19 Changed 4 years ago by ncohen

  • 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 4 years ago by mkoeppe

  • 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 follow-up: Changed 4 years ago by mkoeppe

  • Authors set to Yuan Zhou, Matthias Koeppe
  • Commit changed from e2b25e2ace4888a84140b1f52165cea19653f9e0 to 3c0da609a36bd5832cf6a9f11895e993971731c4
  • Status changed from needs_review to positive_review

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:

f5a1561trac #18732: superficial changes
3c0da60Update docstrings regarding exceptions raised

comment:22 in reply to: ↑ 21 Changed 4 years ago by ncohen

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

+1

Nathann

comment:23 Changed 4 years ago by vbraun

  • Branch changed from public/18732 to 3c0da609a36bd5832cf6a9f11895e993971731c4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.