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