Parallel Interior Point Solver for Structured Linear Programs

Jacek Gondzio and Robert Sarkissian

Issues of implementation of the object-oriented library for parallel interior point methods are addressed. The solver can easily exploit {\it any} special structure of the underlying optimization problem. In particular, it allows a nested embedding of structures and by this means very complicated real-life optimization problems can be modelled. The efficiency of the solver is illustrated on several problems arising in the optimization of networks. The sequential implementation outperforms the state-of-the-art commercial optimization software. The parallel implementation achieves speed-ups of about 3.1-3.9 on 4-processors parallel systems and speed-ups of about 10-12 on 16-processors parallel systems.

Technical Report MS-00-025, Department of Mathematics and Statistics, The University of Edinburgh, Scotland. December 4, 2000.