Interior point methods for large-scale linear programming

Download the paper as a pdf file or postscript file.

Authors:

K. Farwell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
farwek@rpi.edu

D. Ramsden
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
ramsdd@rpi.edu

Citation details:

Abstract:
We discuss interior point methods for large-scale linear programming, with an emphasis on methods that are useful for problems arising in telecommunications. We give the basic framework of a primal-dual interior point method, and consider the numerical issues involved in calculating the search direction in each iteration, including the use of factorization methods and/or preconditioned conjugate gradient methods. We also look at interior point column generation methods which can be used for very large scale linear programs or for problems where the data is generated only as needed.

Keywords: Interior point methods, preconditioned conjugate gradient methods, network flows, column generation.

Download the paper as a pdf file or postscript file.

Return to my list of papers.