J. Gondzio and A. Grothey
Abstract
Solution methods for very large scale optimization problems
are addressed in this paper. Interior point methods are
demonstrated to provide unequalled efficiency in this context.
They need a small (and predictable) number of iterations
to solve a problem. A single iteration of interior point
method requires the solution of indefinite system of equations.
This system is regularized to guarantee the existence
of triangular decomposition. Hence the well-understood
parallel computing techniques developed for positive definite
matrices can be extended to this class of indefinite matrices.
A parallel implementation of an interior point method is described
in this paper. It uses object-oriented programming techniques
and allows for exploiting different block-structures of matrices.
Our implementation outperforms the industry-standard optimizer,
shows very good parallel efficiency on massively parallel architecture
and solves problems of unprecedented sizes reaching 109 variables.
Key words: Very Large Scale Optimization, Interior Point Methods, Exploiting Structure, Parallel Computing.