Analysis of a cutting plane method that uses weighted analytic center and multiple cuts

Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We consider the analytic center cutting plane (or column generation) algorithm for solving general convex problems defined by a separation oracle. The oracle is called at an approximate analytic center of a polytope which contains the solution set and is given by the intersection of the linear inequalities previously generated from the oracle. If the approximate center is not in the solution set, separating hyperplanes will be placed through the approximate center, and a new approximate analytic center will be found for the shrunken polytope. In this paper, we consider using approximate weighted analytic centers in the cutting plane method and show that the method, with multiple cuts added in each step, has a complexity of O(ηm2/∈2), where η is the maximum number of cuts that can be added in each step and m is the dimension of the problem.

Original languageEnglish (US)
Pages (from-to)697-716
Number of pages20
JournalSIAM Journal on Optimization
Volume7
Issue number3
DOIs
StatePublished - Aug 1997

Keywords

  • Analytic center
  • Column generation
  • Convex feasibility problem
  • Cutting planes
  • Potential reduction

Fingerprint

Dive into the research topics of 'Analysis of a cutting plane method that uses weighted analytic center and multiple cuts'. Together they form a unique fingerprint.

Cite this