HOPDM is a package for solving large scale linear, convex quadratic
and convex nonlinear programming problems. The code is an implementation
of the infeasible primal-dual interior point method. It uses multiple
centrality correctors; their number is chosen appropriately for a given
problem in order to reduce the overall solution time. HOPDM automatically
chooses the most efficient factorization method for a given problem
(either normal equations or augmented system). The code compares
favourably with commercial LP, QP and NLP packages.
HOPDM has been written by
Jacek Gondzio.
An extension for convex QP has been developed together with Anna Altman.
An extension for convex NLP has been developed together with Olivier Epelly
(see NLPHOPDM).
A decomposition environment based on HOPDM has been developed together
with Pablo González-Brevis, Pedro Munari and Robert Sarkissian.
It is called
PDCGM
which stands for Primal-Dual Column Generation Method.
Special thanks go to
Marek Makowski
for help in a development of the C version of the code.
HOPDM has been designed to satisfy two complementary goals:
- to offer its user a facility of building his own interior point based
application; and
- to solve efficiently large and difficult problems (including cases
when other LP/QP/NLP optimizers fail or are unacceptably slow).
The public domain version 2.13 of HOPDM (updated till February 1996)
is an LP solver written in FORTRAN. It includes an aggressive presolve
routine and the technique of multiple centrality correctors.
Benchmarks of HOPDM 2.30 (March 1998)
LP,
From LP to QP,
Convex QP.
The new version of HOPDM has a form of a C callable library.
In consequence, embedding it into any application is a easy exercise.
Additionally, this new version contains several new options:
- two factorization techniques to choose from;
- warm start routine to optimize a sequence of similar problems
(subsequent LPs differ in the objective, in the right-hand-side,
or in the elements of the constraint matrix);
- warm start routine to optimize a sequence of restricted master problems
arising in the column generation application (subsequent LPs differ
with a possibly large set of new columns appended to the problem);
- PDCGM decomposition environment (Primal-Dual Column Generation Method);
- QP algorithm;
- NLP algorithm;
- Iterative solvers for Newton systems;
- Matrix-Free variant of IPM.
You can see
general information about HOPDM.
You can get from here, from Netlib or from ORSEP, free for any research
use source code of HOPDM, version 2.13
(this is a Fortran 77 LP solver).
Matrix-Free variant of IPM is able to solve huge-scale
problems using limited memory:
- J. Gondzio,
Matrix-Free Interior Point Method,
Computational Optimization and Applications 51 (2012) pp. 457-480.
Published online October 14, 2010: DOI 10.1007/s10589-010-9361-3.
- J. Gondzio, Interior Point Methods 25 Years Later,
European Journal of Operational Research 218 (2012) pp. 587-601.
Published online: October 8, 2011. DOI 10.1016/j.ejor.2011.09.017.
- J. Gondzio,
Convergence Analysis of an Inexact Feasible Interior Point Method
for Convex Quadratic Programming,
SIAM Journal on Optimization 23 (2013) No 3, pp. 1510-1527.
Published online: July 30, 2013. DOI. 10.1137/120886017.
Preconditioned iterative solution
methods are available in HOPDM:
- L. Bergamaschi, J. Gondzio and G. Zilli,
Preconditioning Indefinite Systems
in Interior Point Methods for Optimization,
Computational Optimization and Applications
28 (2004) No 2, pp. 149-171.
Received the 2004 COAP Best Paper Award.
- L. Bergamaschi, J. Gondzio, M. Venturin and G. Zilli,
Inexact Constraint Preconditioners
for Linear Systems Arising in Interior Point Methods,
Computational Optimization and Applications
36 (2007) No 2-3, pp. 137-147.
See
Erratum (9 June 2008) COAP 49 (2011) pp. 401-406.
- G. Al-Jeiroudi, J. Gondzio and J.A.J. Hall,
Preconditioning Indefinite Systems in Interior Point Methods
for Large Scale Linear Optimization,
Optimization Methods and Software
23 (2008) No 3, pp. 345-363.
- G. Al-Jeiroudi and J. Gondzio,
Convergence Analysis of Inexact Infeasible Interior Point Method
for Linear Optimization,
Journal of Optimization Theory and Applications. 141 (2009) pp. 231-247.
Primal-Dual Column Generation Method (PDCGM) based on IPMs:
- J. Gondzio and R. Sarkissian, Column Generation with a Primal-Dual
Method, Logilab Technical Report 96.6, Department of Management Studies,
University of Geneva, Switzerland, June 1996.
TR 96.6 (PDF file).
- J. Gondzio, P. González-Brevis, P. Munari,
New Developments in the Primal-Dual Column Generation Technique,
European Journal of Operational Research 224 (2013) 41-51.
Published online: July 31, 2012. DOI 10.1016/j.ejor.2012.07.024.
- P. Munari and J. Gondzio,
Using the Primal-Dual Interior Point Algorithm within
the Branch-Price-and-Cut Method,
Computers and Operations Research 40 (2013) No 8, pp. 2026–2036.
- J. Gondzio and P. González-Brevis,
A New Warmstarting Strategy for the Primal-Dual Column Generation Method,
Mathematical Programming A 152 (2015) 113--146.
Published online May 22, 2014.
A large LP was solved with HOPDM,
the problem with 12,5 million rows and 25 million columns:
- J. Gondzio and R. Kouwenberg,
High Performance Computing for Asset Liability Management,
Operations Research
49(2001) No 6, 879-891.
The following papers describe HOPDM:
- J. Gondzio, Presolve Analysis of Linear Programs Prior to Applying
an Interior Point Method,
INFORMS Journal on Computing
9, No 1, Winter 1997, 73-91.
- J. Gondzio, Multiple Centrality Corrections in a Primal-Dual
Method for Linear Programming,
Computational Optimization and Applications
6 (1996) No 2, 137-156.
- J. Gondzio, HOPDM (version 2.12) - A Fast LP Solver Based on
a Primal-Dual Interior Point Method,
European Journal of Operational Research
85 (1995) No 1, 221-225.
- J. Gondzio and M. Makowski, HOPDM - Modular Solver for LP Problems,
User's Guide to Version 2.12, Working Paper WP-95-50, International
Institute for Applied Systems Analysis, Laxenburg, Austria, 1995.
WP-95-50 (PS file).
- A. Altman and J. Gondzio, Regularized Symmetric Indefinite
Systems in Interior Point Methods for Linear and Quadratic Optimization,
Optimization Methods and Software
11-12 (1999) No 1-4, 275-302.
- O. Epelly, J. Gondzio and J.-P. Vial, An Interior Point Solver
for Smooth Convex Optimization with an Application
to Environmental-Energy-Economic Models, Logilab Technical
Report 2000.8, Department of Management Studies, University of Geneva,
Switzerland, July 2000. TR 2000.8 (PDF file).
- M. Colombo and J. Gondzio,
Further Development of Multiple Centrality Correctors
for Interior Point Methods,
Computational Optimization and Applications
41 (2008) No 3, pp. 277-305.
HOPDM is the first primal-dual code which contains
IPM-based warm start option:
- J. Gondzio, Warm Start of the Primal-Dual Method Applied
in the Cutting Plane Scheme,
Mathematical Programming
83 (1998) No 1, 125-143.
- J. Gondzio and J.-P. Vial,
Warm Start and Epsilon-subgradients in the Cutting Plane Scheme for
Block-angular Linear Programs,
Computational Optimization and Applications
14 (1999) No 1, 17-36.
- J. Gondzio and P. González-Brevis,
A New Warmstarting Strategy for the Primal-Dual Column Generation Method,
Mathematical Programming A 152 (2015) 113--146.
Published online May 22, 2014.
Re-optimization facility of HOPDM was applied
in the solution of large-scale optimization problems:
- J. Gondzio, R. Sarkissian and J.-P. Vial,
Parallel Implementation of a Central Decomposition Method for
Solving Large Scale Planning Problems,
Computational Optimization and Applications
19 (2001) No 1, 5-29.
- E. Fragniere, J. Gondzio and J.-P. Vial,
Building and Solving Large-scale Stochastic Programs
on an Affordable Distributed Computing System,
Annals of Operations Research
99 (2000) No 1/4, 167-187.
The following surveys address in detail
the issues of implementation of IPMs for LP/QP:
- E.D. Andersen, J. Gondzio, C. Meszaros, and X. Xu, Implementation
of Interior Point Methods for Large Scale Linear Programming, in:
Interior Point Methods in Mathematical Programming, T. Terlaky
(ed.), Chapter 6, pp. 189-252, Kluwer Academic Publisher, 1996.
See the
book and an old version of the TR 1996.3 (PS file).
- J. Gondzio and T. Terlaky, A Computational View of Interior Point
Methods for Linear Programming, in: Advances in Linear and Integer
Programming, J. Beasley (ed.), Chapter 3, pp 103-144, Oxford University
Press, Oxford, England 1996.
See the
book and an old version of the TR 1994.22 (PS file).
- J. Gondzio, Interior Point Methods 25 Years Later,
European Journal of Operational Research 218 (2012) pp. 587-601.
Published online: October 8, 2011. DOI 10.1016/j.ejor.2011.09.017.