The APOS linear programming solver : an implementation of the homogeneous algorithm

The purpose of this work is to present the APOS linear programming (LP) solver intended for solution of large-scale sparse LP problems. The solver is based on the homogeneous interior- point algorithm which in contrast to the primal-dual algorithm detects a possible primal or dual infeasibility reliably. It employs advanced (parallelized) linear algebra, it handles dense columns in the constraint matrix efficiently, and it has a basis identification procedure. Moreover, recently the solver has been incorporated into the commercially available XPRESS-MP software. This paper discusses in details the algorithm and linear algebra employed by the APOS LP solver. In particular the homogeneous algorithm is emphasized. Furthermore, extensive com- putational results are reported. These results include comparative results for the XPRESS-MP simplex and barrier code and the freely available BPMPD code developed by Cs. M?esz?aros. Finally, computational results are presented to demonstrate the possible speed-up, when using a parallelized version of the APOS LP solver on a Silicon Graphics Challenge computer.