Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Question

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations.

But do you know if a pure cutting-plane method can be used for very small Mixed Integer Linear Program like 20 constraints * 20 variables ?

I cannot figure out why branch-and-bound is numerically stable unlike cutting-plane.

Thanks

Answer 1

I think you're generalizing the numerical instability of Gomory's fractional cutting plane method too much. If you have a problem for which you can efficiently generate numerically stable cutting planes (with integral coefficients for instance) then it's quite possible that that a pure cutting plane method will work quite well for your problem.

However on the other hand, if you are using a cutting plane method based on Gomory cuts, then the fractional coefficients in the cuts can often lead to numerical instability. In essence you'll end up adding a lot of cuts with weird fractional coefficients which will result in really inefficient LP relaxation solves and slow convergence to the integer optimal solution.

Pure branch and bound is stable (or at least as stable as the original problem) because it doesn't add any constraints.

You might want to look at this paper, for some good info and references on numerical instability of Gomory's fractional cutting plane algorithm.