Article ID: | iaor2002444 |
Country: | Netherlands |
Volume: | 99 |
Issue: | 1 |
Start Page Number: | 95 |
End Page Number: | 122 |
Publication Date: | Dec 2000 |
Journal: | Annals of Operations Research |
Authors: | Mitchell John E., Ramaswamy Srinivasan |
Keywords: | cutting plane algorithms |
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(