Exploiting Structure in Parallel Implementation
of Interior Point Methods for Optimization

Technical Report MS 2004-004

J. Gondzio and A. Grothey

OOPS is an object oriented parallel solver using the primal-dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present is truly large-scale optimization problems such as those appearing in Stochastic Programming. This is achieved by treating the building blocks of the structured matrices as objects, that can use their inherent linear algebra implementations to efficiently exploit their structure both in a serial and parallel environment. Virtually any nested block-structure can be exploited by representing the matrices defining the problem as a tree build from these objects. OOPS can be run on a wide variety of architectures and has been used to solve a financial planning problem with over $10^9$ decision variables.
We give details of supported structures and their implementations. Further we give details of how parallelisation is managed in the object-oriented framework.

Key words: Interior Point Methods, Exploiting Structure, Parallel Computing.

PDF MS04-004.pdf.

Written: December 18, 2004, revised July 4, 2005 and November 15, 2007.
Computational Management Science. 6 (2009) pp 135–160.
Appeared in electronic form in December, 2008.

Related Software:
OOPS Object-Oriented Parallel Solver.