BPMPD
Home Page
This page is devoted to the interior point solver called
BPMPD. The solver is developed by Csaba
Mészáros at the MTA SZTAKI,
Computer and Automation Research Institute, Hungarian Academy of Sciences
, Budapest
, Hungary .
ABOUT BPMPD
Newest version: 2.21 (June, 1998)
New features:

New sparsity heuristics

More efficient presolve

Convex QP extension

Warmstart
BPMPD is a stateoftheart implementation of a primaldual
interior point algorithm, written in C programming language. Recent version
is 2.21. You can find a performance comparison of differnent IPM packages
(including BPMPD) on the pages of Decision
Tree for Optimization Software. Press here
to view the BPMPD readme file. There is a downloadable
Windows95/NT executable
and DLL
version of the recent release.
The standard BPMPD package has the following features:

Standard MPS input

Advanced presolve, which:

removes empty rows/columns

removes singleton rows

eliminates free (or implied free) singleton columns

removes redundant constraints and fixes variables based on
minimum/maximum constraints activity

does the above on the dual problem

substitutes duplicated variables

removes redundant bounds on variables

eliminates free (or implied free) variables

makes the constraint matrix sparser

Sophisticated heuristic to make decision between normal equation
and augmented system approach

Advanced sparsity analyzer for sparse quadratic problems

Scaling the problem for better numerical properties

Advanced symbolic ordering for normal equations approach

Leftlooking supernodal factorization algorithm with loop
unrolling

Supernodal backsolve with loop unrolling

Increased numerical robustness (Iterative refinement, PCG,
QMR)
The above techniques make BPMPD very reliable and fast to
solve wide variety of linear and convex quadratic programming problems.
The solver can handle special structures automatically (e.g. dense columns)
as well as free variables explicitely.
You can obtain a Windows95/NT executable
and DLL
version of the new release. Feel free to get in touch with me
if you have questions about the package.
You can find the following papers about BPMPD:

Mészáros,
Cs.: The efficient implementation of interior point methods for linear
programming and their applications, PHD Thesis, Eötvös
Loránd University of Sciences, 1996.

Mészáros,
Cs.: Fast Cholesky Factorization for Interior Point Methods of Linear Programming.
Computers & Mathematics with Applications Vol. 31. No.4/5 (1996)
pp. 4951.

Mészáros,
Cs.: The augmented system variant of IPMs in twostage stochastic linear
ptogramming computation, European Journal of Operations Research
Vol. 101/2, (1997)

Mészáros,
Cs.: The "inexact" minimum local fillin ordering algorithm. ACM Transactions
on Mathematical Software (submitted)

Mészáros,
Cs.: On free variables in interior point methods. Optimization Methods
and Software Vol.9, pp. 121139, 1998.

Maros I.,
Mészáros Cs.: The Role of the Augmented System in Interior
Point Methods. European Journal of Operations Research 107, pp.
720736, 1998.

Mészáros
Cs.: Steplengths in infeasible primaldual interior point algorithms of
convex quadratic programming. Departmental Tech. Rep. DOC 97/7, Imperial
College, London, UK. (1997)

Mészáros
Cs.: On a property of the Cholesky factorization and its consequences in
interior piont methods", WP 987, Computer and Automation Research
Institute, Hungarian Academy of Sciences, Budapest, 1998.

Mészáros
Cs.: On the sparsity issues of interior point methods for quadratic programming,
WP 984, Computer and Automation Research Institute, Hungarian Academy
of Sciences, Budapest, 1998.

Mészáros
Cs.: The separable and nonseparable formulations of convex quadratic
problems in interior point methods, WP 983, Computer and Automation
Research Institute, Hungarian Academy of Sciences, Budapest, 1998.

Mészáros
Cs.: The BPMPD interior point solver for convex quadratic problems, WP
988, Computer and Automation Research Institute, Hungarian Academy of
Sciences, Budapest, 1998..
Linear Programming Test Problems
I'm collecting linear programming problems (in MPS format,
formulated as minimization) for testing. You can find them in the following
subdirectories of http://www.sztaki.hu/~meszaros/public_ftp/lptestset:

NETLIB,
contains the "usual" NETLIB LP
problems.

KENNINGTON,
contains the "Kennington" collection, also available from NETLIB.

INFEAS,
infeasible LP problems (most of them are available from NETLIB).

STOCHLP,
deterministic equvivalent of stochastic linear programming problems (mostly
2stage models).

MISC,
in which you can find a number of different LP problems not available from
NETLIB.

PROBLEMATIC,
in which you can find "problematical" problems. These problems are, usually
the results of wrong modelling. In the README file you can find a short
explanation about the modelling mistakes.

QPDATA,
where you can find sets of convex quadratic testproblems. See the
README
for more details.
NETLIB.
The problems are compressed in two levels. To uncompress
them, you have to gunzip the files and then use the empc
utility to create the MPS file. Please let you submit
me your problems (if you have an interesting one) by sending me a mail
message.
I would like to emphasize my sincerely thanks to those people who helped
me to extend the MISC collection, namely to

Prof. G. Mitra at the Brunel University ,

Prof. T. Terlaky at the University of Technology Delft,

E.D. Andersen at the Univeristy Odensee.
Csaba Mészáros,
MTA SZTAKI,
Budapest, Hungary
1997