《《1995 A fast LP solver based on a primal-dual interior point method》.pdf

HOPDM version A fast LP solver based on a primaldual interior p oint metho d Jacek Gondzio Systems Research Institute Polish Academy of Sciences Newelska Warsaw Poland email gondzioibspanwawpl May Keywords Large scale linear programming interior point method primaldual algorithm multiple centrality correctors Hardware information Any computer with a FORTRAN compiler Software information FORTRAN Intro duction HOPDM is an implementation of the primaldual interior point method for solving large scale linear programming LP problems HOPDM stands for Higher Order Primal Dual Method Its newest version of May is a robust and ecient code that compares favourably with the up to date commercial LP solvers The development of HOPDM started from our joint work with Anna Altman in version of the code was made public domain through the ORSEP Since then the code has been independently developed in two dierent directions Motivated with a real life application Altman extended it to handle separable convex quadratic programs while Gondzio concentrated on improving robustness and eciency of the basic LP algorithm Fundamentals The algorithm implemented in HOPDM is a new variant of a primaldual method The basic primaldual algorithm has been developed independently by Megiddo and Kojima Mizuno and Yoshise Its implementation armed with the predictorcorrector technique of Mehrotra proved to be very ecient and became the computational state of the art for a couple of years More details of the development of the primaldual method are found in the survey and the references therein The development of the HOPDM software greatly b eneted from a few