J. Gondzio and A. Grothey
Abstract
Many practical large-scale optimization problems are not only sparse,
but also display some form of block-structure such as primal or dual
block angular structure. Often these structures are nested:
each block of the coarse top level structure is block-structured itself.
Problems with these characteristics appear
frequently in stochastic programming but also in other areas such as
telecommunication network modelling.
We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra.
The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems.
Key words: Quadratic Programming, Financial Planning Problems, Interior Point Methods, Parallel Computing, Object-Oriented Programming.