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 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:

1. to offer its user a facility of building his own interior point based application; and
2. to solve efficiently large and difficult problems (including cases when other LP/QP/NLP optimizers fail or are unacceptably slow).

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:

1. two factorization techniques to choose from;
2. 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);
3. 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);
4. PDCGM decomposition environment (Primal-Dual Column Generation Method);
5. QP algorithm;
6. NLP algorithm;
7. Iterative solvers for Newton systems;
8. 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).

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 the Erratum (9 June 2008): MS05-002erratum.pdf to appear in COAP.

• 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.

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.

Matrix-Free variant of IPM allows 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.
  

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 (PS 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.
  

• 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 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 (PS file).
  
• 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, 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.
  

• 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. TR 1996.3 (PS file) (see also the whole book).
  
• 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. TR 1994.22 (PS file) (see also the whole book).