A Long Step Cutting Plane Algorithm That Uses the Volumetric Barrier

John E. Mitchell and Srinivasan Ramaswamy

A cutting plane method for linear/convex programming is described. It is based on the volumetric barrier, introduced by Vaidya. The algorithm is a long step one, and has a complexity of O(n^{1.5}L) Newton steps. This is better than the O(n\sqrt{m}L) complexity of non-cutting plane long step methods based on the volumetric barrier, but it is however worse than Vaidya's original O(nL) result (which is not a long step algorithm). Major features of our algorithm are that when adding cuts we add them right through the current point, and when seeking progress in the objective, the duality gap is reduced by a constant factor (not true for Vaidya's original algorithm). Further, we generate primal as well as dual iterates, making this applicable in the column generation context as well, and allowing early termination. Vaidya's algorithm has been used as a subroutine to obtain the best complexity for several combinatorial optimization problems -- e.g, the Held-Karp lower bound for the Traveling Salesperson Problem. While our complexity result is weaker, this long step cutting plane algorithm is likely to be computationally more promising on such combinatorial optimization problems with an exponential number of constraints. We also discuss a multiple cuts version --- where upto p<=n `selectively orthonormalized' cuts are added through the current point at each stage where cuts are identified by the oracle. This has a complexity of O(n^{1.5}L p log p) quasi Newton steps.

[POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]