Implementation of interior point methods for large scale linear programming Export

@inproceedings{citeulike:4090966, abstract = {In the past 10 years the interior point methods (IPM) for linear programming have gained extraordinary interest as an alternative to the sparse simplex based methods. This has initiated a fruitful competition between the two types of algorithms which has lead to very efficient implementations on both sides. The significant difference between interior point and simplex based methods is reflected not only in the theoretical background but also in the practical implementation. In this paper we give an overview of the most important characteristics of advanced implementations of interior point methods. First, we present the infeasible-primal-dual algorithm which is widely considered the most efficient general purpose IPM. Our discussion includes various algorithmic enhancements of the basic algorithm. The only shortcoming of the \"traditional \" infeasible-primal-dual algorithm is to detect a possible primal or dual infeasibility of the linear program. We discuss how this problem can be solved with the homogeneous and self-dual model. The IPMs practical efficiency is highly dependent on the linear algebra used. Hence, we discuss this subject in great detail. Finally we cover the related topics of preprocessing and}, author = {Andersen, Erling D. and Gondzio, Jacek and Xu, Xiaojie}, booktitle = {in Interior Point Methods in Mathematical Programming}, citeulike-article-id = {4090966}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.3933}, keywords = {article, interiorpoint}, pages = {189--252}, posted-at = {2009-02-24 03:41:51}, priority = {2}, title = {Implementation of interior point methods for large scale linear programming}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.3933}, year = {1996} }

TY - CONF ID - citeulike:4090966 L3 - citeulike-article-id:4090966 N2 - In the past 10 years the interior point methods (IPM) for linear programming have gained extraordinary interest as an alternative to the sparse simplex based methods. This has initiated a fruitful competition between the two types of algorithms which has lead to very efficient implementations on both sides. The significant difference between interior point and simplex based methods is reflected not only in the theoretical background but also in the practical implementation. In this paper we give an overview of the most important characteristics of advanced implementations of interior point methods. First, we present the infeasible-primal-dual algorithm which is widely considered the most efficient general purpose IPM. Our discussion includes various algorithmic enhancements of the basic algorithm. The only shortcoming of the "traditional " infeasible-primal-dual algorithm is to detect a possible primal or dual infeasibility of the linear program. We discuss how this problem can be solved with the homogeneous and self-dual model. The IPMs practical efficiency is highly dependent on the linear algebra used. Hence, we discuss this subject in great detail. Finally we cover the related topics of preprocessing and EP - 252 TI - Implementation of interior point methods for large scale linear programming T2 - in Interior Point Methods in Mathematical Programming SP - 189 KW - article KW - interiorpoint AU - Andersen, Erling AU - Gondzio, Jacek AU - Xu, Xiaojie PY - 1996/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.3933 ER -