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

• From LP to QP (PS file, 73 kB).

• Convex QP (PS file, 79 kB).

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.

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, Technical Report MS-02-002, Department of Mathematics and Statistics, The University of Edinburgh, July 26, 2002, revised March 18, 2003 and in August 29, 2003. MS-02-002 (PS file).
  Accepted for publication in: Computational Optimization and Applications.

A large LP was solved with HOPDM, the problem with 12,5 million rows and 25 million columns:

• Gondzio J. and R. Kouwenberg, High Performance Computing for Asset Liability Management, Operations Research 49(2001) No 6, 879-891. MS-99-004 (PS file).

The following papers describe HOPDM:

• Gondzio, J., Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method, INFORMS Journal on Computing 9, No 1, Winter 1997, 73-91. TR 1994.3 (PS file).

• Gondzio, J., Multiple Centrality Corrections in a Primal-Dual Method for Linear Programming, Computational Optimization and Applications 6 (1996) 137-156. TR 1994.20 (PS file).

• Gondzio J., HOPDM (version 2.12) - A Fast LP Solver Based on a Primal-Dual Interior Point Method, European Journal of Operational Research 85 (1995) 221-225. TR 1995 (PS file).

• Gondzio J. 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).

• Altman A. and J. Gondzio, Regularized Symmetric Indefinite Systems in Interior Point Methods for Linear and Quadratic Optimization, Optimization Methods and Software 11-12 (1999) 275-302. TR 98.6 (PS file).

• Epelly O., 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).

• Gondzio J., Warm Start of the Primal-Dual Method Applied in the Cutting Plane Scheme, Mathematical Programming 83 (1998) No 1, 125-143. TR 96.3 (PS file).

• Gondzio J. 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).

• Gondzio J. 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) 17-36. TR 97.1 (PS file).

• Gondzio J., 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) 5-29. TR 98.1 (PS file).

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

• Andersen E.D., 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).

• Gondzio J. 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).