Very large optimization problems (LPs, QPs or NLPs) with millions
of constraints and decision variables often display some special
structure.
OOPS is the parallel interior point code
that exploits any special structure in the Hessian and Jacobian
matrices. The solver is an implementation of the primal-dual interior
point method with multiple centrality correctors.
The solver is implemented using object-oriented programming
techniques. It solves linear (LP), quadratic (QP) and nonlinear (NLP)
problems. The sequential code compares favourably with commercial
packages and the parallel code shows perfect speed-ups.
OOPS has beed developed by
Jacek Gondzio,
Andreas Grothey and
Robert Sarkissian.
In May 2005 OOPS was used to solve a QP problem with 109 variables.
The following papers describe OOPS and address its various applications:
- J. Gondzio and R. Sarkissian,
Parallel Interior Point Solver for Structured Linear Programs,
Mathematical Programming
96 (2003) No 3, 561-584.
- J. Gondzio and A. Grothey,
Reoptimization with the Primal-Dual Interior Point Method,
SIAM Journal on Optimization
13 (2003) No 3, pp. 842-864.
- J. Gondzio and A. Grothey,
Parallel Interior Point Solver for Structured Quadratic Programs:
Application to Financial Planning Problems,
Annals of Operations Research
152 (2007) No 1, pp. 319-339.
- J. Gondzio and A. Grothey,
Solving Nonlinear Portfolio Optimization Problems
with the Primal-Dual Interior Point Method,
European Journal of Operational Research
181 (2007) No 3, pp. 1019-1029.
- J. Gondzio and A. Grothey,
Exploiting Structure in Parallel Implementation
of Interior Point Methods for Optimization,
Computational Management Science, 6 (2009) pp. 135–160.
- J. Gondzio and A. Grothey,
Direct Solution of Linear Systems of Size 109
Arising in Optimization with Interior Point Methods,
R. Wyrzykowski, J. Dongarra, N. Meyer and J. Wasniewski (eds.),
Parallel Processing and Applied Mathematics PPAM 2005,
Lecture Notes in Computer Science, 3911,
Springer-Verlag, Berlin, 2006, pp 513-525.
(abstract, PDF).
- J. Gondzio and A. Grothey,
Solving Distribution Planning Problems
with the Interior Point Method,
Technical Report MS-06-001, School of Mathematics,
The University of Edinburgh, February 18, 2006, revised May 25, 2006.
(abstract, PDF).
- J. Gondzio and A. Grothey,
Solving Nonlinear Financial Planning Problems
with 109 Decision Variables
on Massively Parallel Architectures,
M. Costantino, C.A. Brebbia (eds.),
Computational Finance and its Applications II,
WIT Transactions on Modelling and Simulation,
43, WIT Press, 2006.
(abstract, PS, PDF).
- M. Colombo, J. Gondzio and A. Grothey,
A Warm-Start Approach for Large-Scale Stochastic Linear Programs,
Mathematical Programming 127 (2011) 371-397.
- J. Gondzio and A. Grothey,
A New Unblocking Technique to Warmstart Interior Point Methods
based on Sensitivity Analysis,
SIAM Journal on Optimization
19 (2008) No 3, pp. 1184-1210.
A convenient access to OOPS is provided through
Structured Modelling Language (SML) described in the paper:
- M. Colombo, A. Grothey, J. Hogg, K. Woodsend and J. Gondzio,
A Structure-conveying Modelling Language
for Mathematical and Stochastic Programming,
Mathematical Programming Computation 1 (2009) pp 223–247.
A baby demo version of OOPS is available with
SML
software.
Robert gave two talks about the design of OOPS:
- INFORMS, Cincinnati, May 3-5, 1999.
- SIAM, Atlanta, May 10-12, 1999.
Andreas talked about it at several occasions:
- NA, Dundee, 24-27 June, 2003.
- ISMP, Copenhagen, August 18-22, 2003.
- NA, Dundee, 28-30 June, 2005.
Jacek talked about it at several occasions:
- IFIP, Cambridge, July 12-16, 1999.
- APMOD, London, April 17-19, 2000.
- ISMP, Atlanta, August 7-11, 2000
(talk00.pdf).
- ISMP, Copenhagen, August 18-22, 2003
(talk03.pdf).
Benchmarks on PCs.
Comparison with Cplex 7.0 Solver (SUN workstation):
(PDF file, 612 kB) (April, 2003).
Comparison with Cplex 9.1 Solver (Linux PC):
(PDF file, 394 kB) (February, 2006).
Return to
Jacek Gondzio's page.