dparo/master-thesis

Improve running time of `GSEC` integral separation, and fractional separation of GLM, and `RCI`

dparo opened this issue · 0 comments

dparo commented

What

When separating these cuts, it requires a Theta(N^2) complexity to generate the index and value array and only later we check if the cut is violated.

How

Fix these cuts by generating the index and value array only when absolutely needed.
Try to short circuit the separation function as early as possible, by determining if any cut is going to be violated. If no cut is going to be violated, there's no point paying for the Theta(N^2) iteration generating the index and value array that will never be used.

This should also improve cache locality.

NOTE: it is already partially fixed in GSEC fractional separation but not for the integral separation