HOPDM

Primal-Dual Method for Linear Programming, using Higher-Order Correctors

HOPDM is a reliable LP solver based on a Higher Order Primal-Dual Method. Although it is a (public domain) research code, it offers exceptionally high efficiency, competitive to that of commercial products.

HOPDM is a modularly structured library of routines. It has been designed to satisfy two complementary goals:

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

The code is written in standard ANSI FORTRAN 77 so it is easily portable to any machine.

HOPDM implements a primal-dual logarithmic barrier interior point method with an (automatically chosen) number of centrality correctors. The code contains several useful options, including a sophisticated presolve routine and a fast sparsity-exploiting Cholesky decomposition, that are carefully documented in the references below.

Need more info?

Visit HOPDM's Web Site, where the latest version of the code (version 2.12, September, 1995) is available for downloading. Several papers that describe the solver can also be found at this site.

An older version (version 2.11 of April, 1995) is available from Netlib's opt directory. The URL is

ftp://netlib.att.com/netlib/opt/hopdm.shar.Z

For more information, contact the author:

   Jacek Gondzio 
   Systems Research Institute, 
   Polish Academy of Sciences, 
   Newelska 6, 01-447 Warsaw, Poland 
   E-mail:  gondzio@ibspan.waw.pl

Reference:

Gondzio J., Splitting dense columns of constraint matrix in interior point methods for large scale linear programming, Optimization 24 (1992), pp. 285-297.

Gondzio J., Implementing Cholesky factorization for interior point methods of linear programming, Optimization 27 (1993), pp 121-140.

Gondzio J., Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method, Technical Report 1994.3, Department of Management Studies, University of Geneva, Switzerland, February 1994, revised in December 1994, to appear in ORSA Journal on Computing.

Gondzio J., Multiple Centrality Corrections in a Primal-Dual Method for Linear Programming, Technical Report 1994.22, Department of Management Studies, University of Geneva, Switzerland, November 1994, revised in May 1995, to appear in Computational Optimization and Applications.

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), pp. 221-225.

[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]