close
Skip to main content
Springer Nature Link
Log in

Exploiting structure in parallel implementation of interior point methods for optimization

  • Original Paper
  • Published:
Save article
View saved research
Computational Management Science Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Arioli M, Duff IS, de Rijk PPM (1989) On the augmented system approach to sparse least-squares problems. Numerische Mathematik 55: 667–684

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Birge JR, Qi L (1988) Computing block-angular Karmarkar projections with applications to stochastic programming. Manage Sci 34: 1472–1479

    Article  Google Scholar 

  • Blomvall J (2003) A mulitstage stochastic programming algorithm suitable for parallel computing. Parallel Comput 29: 431–445

    Article  Google Scholar 

  • Blomvall J, Lindberg PO (2002) A Riccati-based primal interior point solver for multistage stochastic programming. Eur J Oper Res 143: 452–461

    Article  Google Scholar 

  • 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

    Google Scholar 

  • De Leone V., Murli A., Pardalos P., Toraldo G (eds) (1998) High performance algorithms and software in nonlinear optimization. Kluwer Academic Publisher, New York

    Google Scholar 

  • Duff IS, Erisman AM, Reid JK (1987) Direct methods for sparse matrices. Oxford University Press, New York

    Google Scholar 

  • Ferris MC, Munson TS (2003) Interior point methods for massive support vector machines. SIAM J Optim 13: 783–804

    Article  Google Scholar 

  • George A, Liu JWH (1989) The evolution of the minimum degree ordering algorithm. SIAM Rev 31: 1–19

    Article  Google Scholar 

  • Gertz EM, Wright SJ (2003) Object-oriented software for quadratic programming. ACM Trans Math Softw 29: 58–81

    Article  Google Scholar 

  • Gondzio J, Grothey A (2003) Reoptimization with the primal–dual interior point method. SIAM J Optim 13: 842–864

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Article  Google Scholar 

  • Gondzio J, Grothey A (2007a) Solving nonlinear portfolio optimization problems with the primal–dual interior point method. Eur J Oper Res 181: 1019–1029

    Article  Google Scholar 

  • Gondzio J, Sarkissian R (2003) Parallel interior point solver for structured linear programs. Math Program 96: 561–584

    Article  Google Scholar 

  • Grigoriadis MD, Khachiyan LG (1996) An interior point method for bordered block-diagonal linear programs. SIAM J Optim 6: 913–932

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Linderoth J, Wright SJ (2003) Decomposition algorithms for stochastic programming on a computational grid. Comput Optim Appl 24: 207–250

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Vanderbei RJ (1995) Symmetric quasidefinite matrices. SIAM J Optim 5: 100–113

    Article  Google Scholar 

  • Wright SJ (1997) Primal–dual interior-point methods. SIAM, Philadelphia

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, University of Edinburgh, Edinburgh, UK

    Jacek Gondzio & Andreas Grothey

Authors
  1. Jacek Gondzio
    View author publications

    Search author on:PubMed Google Scholar

  2. Andreas Grothey
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Andreas Grothey.

Rights and permissions

Reprints 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

Download citation

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10287-008-0090-3

Keywords