COMPLEXITY ANALYSIS OF THE ANALYTIC CENTER CUTTING PLANE METHOD THAT USES MULTIPLE CUTS

We analyze the complexity of the analytic center cutting plane or colu mn generation algorithm for solving general convex problems defined by a separation oracle. The oracle is called at the analytic center of a polytope, which contains a solution set and is given by the intersect ion of the linear inequalities previously generated from the oracle. I f the center is not in the solution set, separating hyperplanes will b e placed through the center to shrink the containing polytope. While t he complexity result has been recently established for the algorithm w hen one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actu ally is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane method s. In this paper, we show that the analytic center cutting plane algor ithm, with multiple cuts added in each iteration, still is a fully pol ynomial approximation algorithm. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.