Using Indicators in Finite Termination Procedures
Pamela J. Williams, Amr S. El-Bakry, and Richard A. Tapia
The presence of bounded variables complicates finite termination procedures
in interior-point methods for linear programming.
In our numerical experiments, we found that satisfying the upper
bound constraints was the main obstacle to computing an exact solution of
a linear program.
To prevent the computed solution from violating the bound constraints,
one approach incorporates nearest bound information into
a projection model through an affine scaling transformation.
This works well in practice but may introduce ill-conditioning due
to the potential presence of infinitesimal weights, particularly for variables
near a bound.
In this paper, we investigate the role of Tapia indicators in
finite termination procedures. Using Tapia indicators,
we identify variables in the active set, remove them from the
subproblem, and solve a lower dimensional projection problem. Numerical
evidence suggests that using Tapia
indicators to identify variables in the active set in tandem
with an affine scaling transformation results in the fewest iterations
needed to compute an exact solution of a linear program.
Contact: pwillia@sandia.gov