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: [email protected]
![[DVI]](../../InteriorPoint/gif/DVI.gif)
![[PS]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)