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

New features:

• New sparsity heuristics
• More efficient presolve
• Convex QP extension
• Warm-start

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 Windows95/NT  executable  and  DLL  version of the recent release.

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

• 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. 49-51.
• Mészáros, Cs.: The augmented system variant of IPMs in two-stage stochastic linear ptogramming computation, European Journal of Operations Research Vol. 101/2, (1997)
• Mészáros, Cs.: The "inexact" minimum local fill-in 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. 121-139, 1998.
• Maros I., Mészáros Cs.: The Role of the Augmented System in Interior Point Methods. European Journal of Operations Research 107, pp. 720-736, 1998.
• Mészáros Cs.: Steplengths in infeasible primal-dual 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 98-7, 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 98-4, Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, 1998.
• Mészáros 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.
• Mészáros 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:

• 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 2-stage 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.

• Prof. G. Mitra at the Brunel University ,
• Prof. T. Terlaky at the University of Technology Delft,
• E.D. Andersen at the Univeristy Odensee.