**A Long-Step, Cutting Plane Algorithm for Linear and Convex
Programming**

**Download the paper**,
postscript or pdf.
**John E. Mitchell**

Mathematics Department,

Rensselaer Polytechnic Institute,

Troy, NY 12180.

email: mitchj@rpi.edu

**Srinivasan Ramaswamy**

Information Services Division,

Research and Development,

United Airlines,

1200 E. Algonquin Road,

Elk Grove Village, IL 60007.

email: Srini.Ramaswamy@ual.com

Annals of OR,
Volume 99, 2000, pages 95-122.

**Abstract:**
A cutting plane method for linear programming is described.
This method is an extension of Atkinson and Vaidya's algorithm, and
uses the central trajectory. The logarithmic
barrier function is used
explicitly, motivated partly by the successful implementation
of such algorithms.
This makes it possible to maintain primal
and dual iterates, thus allowing termination at will, instead of
having to solve to completion. This algorithm has the same
complexity ($O(nL^2)$ iterations)
as Atkinson and Vaidya's algorithm, but improves
upon it in that it is a `long-step' version, while theirs is
a `short-step' one in some sense. For this reason, this algorithm is
computationally much more promising as well.
This algorithm can be of use in solving combinatorial optimization
problems with large numbers of constraints, such as the Traveling
Salesman Problem.

**Download the paper**,
postscript or pdf.

Return to my list of papers.