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

John Mitchell () and Srinivasan Ramaswamy ()

Annals of Operations Research, 2000, vol. 99, issue 1, 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. Copyright Kluwer Academic Publishers 2000

Keywords: cutting plane; path following; analytic center; linear programming; convex programming (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1019288816566 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:99:y:2000:i:1:p:95-122:10.1023/a:1019288816566

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1019288816566

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().