Interior point methods for large-scale linear programming

John E. Mitchell (mitchjrpi.edu)
Kris Farwell (farwekrpi.edu)
Daryn Ramsden (ramsddrpi.edu)

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

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

Category 2: Applications -- OR and Management Sciences (Telecommunications )

Category 3: Network Optimization

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

Download: [Postscript][PDF]

Entry Submitted: 08/16/2004
Entry Accepted: 08/16/2004
Entry Last Modified: 08/17/2004

Modify/Update this entry