Computing an Exact Solution in Interior-Point Methods for Linear
Programming
Pamela J. Williams, Amr S. El-Bakry, and Richard A. Tapia
To compute an exact solution of a linear program with an interior-point
algorithm, finite termination
procedures must be added to the algorithmic framework. In a finite number
of steps, finite termination procedures advance from an interior-point iterate
which is sufficiently close to the solution set to a point on the optimal face.
A finite termination procedure consists of a mathematical model
to compute an exact solution and indicators to identify the
active set of a linear program.
In this paper we present a survey of optimal face identification
models and solution techniques, introduce a new indicator to identify
the active set of a linear
program in primal-dual interior-point methods and provide some insight
on how to construct a numerically efficient finite termination procedure.
Contact: pwillia@sandia.gov