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
, Hungary .
Newest version: 2.21 (June, 1998)
New sparsity heuristics
More efficient presolve
Convex QP extension
BPMPD is a state-of-the-art implementation of a primal-dual
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
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
Left-looking supernodal factorization algorithm with loop
Supernodal backsolve with loop unrolling
Increased numerical robustness (Iterative refinement, PCG,
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
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:
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.
Cs.: Fast Cholesky Factorization for Interior Point Methods of Linear Programming.
Computers & Mathematics with Applications Vol. 31. No.4/5 (1996)
Cs.: The augmented system variant of IPMs in two-stage stochastic linear
ptogramming computation, European Journal of Operations Research
Vol. 101/2, (1997)
Cs.: The "inexact" minimum local fill-in ordering algorithm. ACM Transactions
on Mathematical Software (submitted)
Cs.: On free variables in interior point methods. Optimization Methods
and Software Vol.9, pp. 121-139, 1998.
Mészáros Cs.: The Role of the Augmented System in Interior
Point Methods. European Journal of Operations Research 107, pp.
Cs.: Steplengths in infeasible primal-dual interior point algorithms of
convex quadratic programming. Departmental Tech. Rep. DOC 97/7, Imperial
College, London, UK. (1997)
Cs.: On a property of the Cholesky factorization and its consequences in
interior piont methods", WP 98-7, Computer and Automation Research
Institute, Hungarian Academy of Sciences, Budapest, 1998.
Cs.: On the sparsity issues of interior point methods for quadratic programming,
WP 98-4, Computer and Automation Research Institute, Hungarian Academy
of Sciences, Budapest, 1998.
Cs.: The separable and non--separable formulations of convex quadratic
problems in interior point methods, WP 98-3, Computer and Automation
Research Institute, Hungarian Academy of Sciences, Budapest, 1998.
Cs.: The BPMPD interior point solver for convex quadratic problems, WP
98-8, 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:
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
contains the "usual" NETLIB LP
contains the "Kennington" collection, also available from NETLIB.
infeasible LP problems (most of them are available from NETLIB).
deterministic equvivalent of stochastic linear programming problems (mostly
in which you can find a number of different LP problems not available from
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.
where you can find sets of convex quadratic testproblems. See the
for more details.
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.