On Exploiting Problem Structure in a Basis Identification Procedure for Linear Programming

Published Online:https://doi.org/10.1287/ijoc.11.1.95

During the last decade, interior-point methods have become an efficient alternative to the simplex algorithm for solution of large-scale linear programming (LP) problems. However, in many practical applications of LP, interior-point methods have the drawback that they do not generate an optimal basic and nonbasic partition of the variables. This partition is required in the traditional sensitivity analysis and is highly useful when a sequence of related LP problems are solved. Therefore, in this article we discuss how an optimal basic solution can be generated from the interior-point solution. The emphasis of the article is on how problem structure can be exploited to reduce the computational cost associated with the basis identification. Computational results are presented that indicate that it is highly advantageous to exploit problem structure.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.