Polynomial interior point cutting plane methods

John E. Mitchell (mitchjrpi.edu)

Abstract: Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the relaxation. Typically, these cutting plane methods can be developed so as to exhibit polynomial convergence. The volumetric cutting plane algorithm achieves the theoretical minimum number of calls to a separation oracle. Long-step versions of the algorithms for solving convex optimization problems are presented.

Keywords: cutting plane, column generation, interior point, polynomial convergence

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Department of Mathematical Sciences Rensselaer Polytechnic Institute Troy, NY 12180 USA July 16, 2001. http://www.rpi.edu/~mitchj/papers/logvolcuts.html

Download:

Entry Submitted: 07/24/2001
Entry Accepted: 07/27/2001
Entry Last Modified: 07/23/2002

Modify/Update this entry