On exploiting problem structure in a basis identifications procedure for linear programming

Erling D. Andersen

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 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 a nd is highly useful when of a sequence of related LP problems are solved. Therefo re, in this paper we discuss how an optimal basic solution can be generated from the interior-point solution. The emphasis of the paper is on how problem structure can be exploited to reduce the computational cost associated with basis identific ation. Computational results are presented which indicate it is highly advantageous to exploit problem structure.

Publications from Department of Management, Odense University, Denmark, no. 6, 19 96.

Contact: eda@busieco.ou.dk