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:

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

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

Matrix-Free variant of IPM is able to solve huge-scale problems using limited memory:

Preconditioned iterative solution methods are available in HOPDM:

Primal-Dual Column Generation Method (PDCGM) based on IPMs:

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

The following papers describe HOPDM:

HOPDM is the first primal-dual code which contains IPM-based warm start option: Re-optimization facility of HOPDM was applied in the solution of large-scale optimization problems: The following surveys address in detail the issues of implementation of IPMs for LP/QP: