On the role of indicators in identifying zero variables in linear programming

[摘要] In this research we study the role of indicator functions in the identification and the removal of zero variables in linear programming. The definition and desired properties of the indicators are given. We investigate the behavior of the Tapia and the primal-dual indicators in the framework of the recently proposed primal-dual interior-point methods. The structure of the solution set of the linear programming problem is closely examined. We prove the interesting result that the relative interior of the solution set coincides with the set of solutions that satisfy strict complementarity. The implications of this result in the context of several indicators is studied. A procedure to identify and remove zero variables is proposed. Finally, we present numerical experiments that demonstrate the use of that procedure in saving computational work and improving the performance of the primal-dual interior-point methods.

[发布机构] Rice University