Complexity analysis of the analytic center cutting plane method that uses multiple cuts
Ye, Yinyu

Data: 1997
Resum: We analyze the complexity of the analytic center cutting plane or column 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 intersection of the linear inequalities previously generated from the oracle. If the center is not in the solution set, separating hyperplanes will be placed through the center to shrink the containing polytope. While the complexity result has been recently established for the algorithm when one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actually is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane methods. In this paper, we show that the analytic center cutting plane algorithm, with multiple cuts added in each iteration, still is a fully polynomial approximation algorithm. .
Drets: Tots els drets reservats
Llengua: Anglès
Document: article ; recerca ; Versió publicada
Matèria: Convex feasibility problem ; Analytic center ; Potential reduction ; Column generation ; Cutting planes
Publicat a: Mathematical Programming, vol. 78 n. 1 (1997) p. 85-104, ISSN 0025-5610

20 p, 569.1 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2021-07-24

   Favorit i Compartir