Adaptive Use of Iterative Methods in Interior Point Methods for Linear
Programming
Adaptive Use of Iterative Methods in Interior Point Methods for Linear
Programming
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Wang, Weichung
O'Leary, Dianne P.
Advisor
Citation
DRUM DOI
Abstract
In this work we devise efficient algorithms for finding the search
directions for interior point methods applied to linear programming
problems. There are two innovations. The first is the use of updating of
preconditioners computed for previous barrier parameters. The second is an
adaptive automated procedure for determining whether to use a direct or
iterative solver, whether to reinitialize or update the preconditioner,
and how many updates to apply. These decisions are based on predictions of
the cost of using the different solvers to determine the next search
direction, given costs in determining earlier directions. These ideas are
tested by applying a modified version of the OB1-R code of Lustig,
Marsten, and Shanno to a variety of problems from the NETLIB and other
collections. If a direct method is appropriate for the problem, then our
procedure chooses it, but when an iterative procedure is helpful,
substantial gains in efficiency can be obtained.
(Also cross-referenced as UMIACS-TR-95-111)