Title: Parallel Interior Point Solver for Very Large Scale Optimization


		        Jacek Gondzio
		   School of Mathematics
                   University of Edinburgh
                   EH9 3JZ Edinburgh, Scotland
                   Email: J.Gondzio@ed.ac.uk
          Web page: http://www.maths.ed.ac.uk/~gondzio

              Author: Jacek Gondzio & Andreas Grothey


Abstract:
Very large optimization problems with millions of constraints
and decision variables display usually some special structure.
The key to efficient solution of such problems is the ability
to exploit the structure.
We have developed a structure-exploiting parallel primal-dual
interior-point solver for nonlinear programming problems.
The solver can deal with a nested embedding of structures.
Hence very complicated real-life optimization problems can be
modeled.

Its design uses object-oriented programming techniques.
Different matrix structures are implemented as subclasses
of an abstract matrix class.
This abstract matrix class contains a set of virtual
functions (methods in the object-oriented terminology) that:
(i)  provide all the necessary linear algebraic operations
     for an interior point method, and
(ii) allow self-referencing.
The program OOPS (Object-Oriented Parallel Solver:
http://www.maths.ed.ac.uk/~gondzio/parallel/solver.html)
can efficiently handle very large nonlinear problems and achieves
scalability on a number of different computing platforms.

The efficiency of the solver is illustrated with problems known
from the literature: applications arising from telecommunication
and financial engineering.  Numerical results are given for
the solution of nonlinear financial planning problems with
sizes over 50 million decision variables.