Handbook of Optimization in Telecommunications M.G.C. Resende and P.M. Pardalos (Editors) Springer Science + Business Media, 2006.
Chapter 1
Interior point methods for large-scale linear programming
J.E. Mitchell, K. Farwell, and D. Ramsden
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.