Abstract
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 in 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 109 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Altman A, Gondzio J (1999) Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim Methods Softw 11(12): 275–302
Andersen ED, Gondzio J, Mészáros C, Xu X (1996) Implementation of interior point methods for large scale linear programming. In: Terlaky T (eds) Interior point methods in mathematical programming. Kluwer Academic Publishers, New York, pp 189–252
Arioli M, Duff IS, de Rijk PPM (1989) On the augmented system approach to sparse least-squares problems. Numerische Mathematik 55: 667–684
Benson S, McInnes LC, Moré JJ (2001) TAO users manual. Tech. Rep. ANL/MCS-TM-249, Argonne National Laboratory
Birge J, Dempster M, Gassmann H, Gunn E, King A, Wallace S (1987) A standard input format for multiperiod stochastic linear programs. Comm Algorithms Newslett 17: 1–19
Birge JR, Qi L (1988) Computing block-angular Karmarkar projections with applications to stochastic programming. Manage Sci 34: 1472–1479
Blomvall J (2003) A mulitstage stochastic programming algorithm suitable for parallel computing. Parallel Comput 29: 431–445
Blomvall J, Lindberg PO (2002) A Riccati-based primal interior point solver for multistage stochastic programming. Eur J Oper Res 143: 452–461
Colombo M, Gondzio J, Grothey A (2006) A warm-start approach for large-scale stochastic linear programs. Technical Report MS-06-004, School of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland, UK, August
Cristianini N, Shawe-Taylor J (2000) An introduction to support vector machines and other kernel based learning methods. Cambridge University Press, London
De Leone V., Murli A., Pardalos P., Toraldo G (eds) (1998) High performance algorithms and software in nonlinear optimization. Kluwer Academic Publisher, New York
Duff IS, Erisman AM, Reid JK (1987) Direct methods for sparse matrices. Oxford University Press, New York
Ferris MC, Munson TS (2003) Interior point methods for massive support vector machines. SIAM J Optim 13: 783–804
George A, Liu JWH (1989) The evolution of the minimum degree ordering algorithm. SIAM Rev 31: 1–19
Gertz EM, Wright SJ (2003) Object-oriented software for quadratic programming. ACM Trans Math Softw 29: 58–81
Gondzio J, Grothey A (2003) Reoptimization with the primal–dual interior point method. SIAM J Optim 13: 842–864
Gondzio J, Grothey A (2006a) Direct solution of linear systems of size 109 arising in optimization with interior point methods. In: Wyrzykowski R (eds) Parallel Processing and Applied Mathematics. vol 3911. Lecture Notes in Computer Science, Springer, pp 513–525
Gondzio J, Grothey A (2006b), Solving distribution planning problems with the interior point method. Technical Report MS-06-001, School of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland, UK, February
Gondzio J, Grothey A (2007a) Parallel interior point solver for structured quadratic programs: Application to financial planning problems. Ann Oper Res 152: 319–339
Gondzio J, Grothey A (2007a) Solving nonlinear portfolio optimization problems with the primal–dual interior point method. Eur J Oper Res 181: 1019–1029
Gondzio J, Sarkissian R (2003) Parallel interior point solver for structured linear programs. Math Program 96: 561–584
Grigoriadis MD, Khachiyan LG (1996) An interior point method for bordered block-diagonal linear programs. SIAM J Optim 6: 913–932
Grothey A, Hogg J, Woodsend K, Colombo M, Gondzio J (2009) A structure-conveying parallelisable modelling language for mathematical programming. In: Ciegis R, Henty D, Kågström B, Žilinskas J (eds) Parallel scientific computing and optimization: advances and applications. Springer optimization and its applications, vol 27. Springer, Berlin, pp 147–158
Linderoth J, Wright SJ (2003) Decomposition algorithms for stochastic programming on a computational grid. Comput Optim Appl 24: 207–250
Lustig IJ, Li G (1992) An implementation of a parallel primal–dual interior point method for multicommodity flow problems. Comput Optim Appl 1: 141–161
Meza J, Oliva R, Hough P, Williams P (2007) OPT++: An object oriented toolkit for nonlinear optimization. ACM Transactions on Mathematical Software 33, p. 12. Article 12, 27 pages
Migdalas A, Toraldo G, Kumar V (2003) Parallel computing in numerical optimization. Parallel Comput 29: 373–373
Steinbach M (2000) Hierarchical sparsity in multistage convex stochastic programs. In: Uryasev S, Pardalos PM (eds) Stochastic optimization: algorithms and applications. Kluwer Academic Publishers, New York, pp 363–388
Vanderbei RJ (1995) Symmetric quasidefinite matrices. SIAM J Optim 5: 100–113
Wright SJ (1997) Primal–dual interior-point methods. SIAM, Philadelphia
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gondzio, J., Grothey, A. Exploiting structure in parallel implementation of interior point methods for optimization. Comput Manag Sci 6, 135–160 (2009). https://doi.org/10.1007/s10287-008-0090-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-008-0090-3