An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs

E. Alper Yildirim (yildirimorie.cornell.edu)
Michael J. Todd (miketoddcs.cornell.edu)

Abstract: We consider the interior-point approach to sensitivity analysis in linear programming (LP) developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special degeneracy, we show that these bounds have the same nice relationship with the optimal partition bounds as in the nondegenerate case. We prove a weaker relationship for general degenerate LPs.

Keywords: linear programming, sensitivity analysis, interior-point methods

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: SIAM Journal on Optimization 12 (2002), 692--714. Available electronically at http://www.ams.sunysb.edu/~yildirim

Download:

Entry Submitted: 01/23/2001
Entry Accepted: 01/23/2001
Entry Last Modified: 04/15/2003

Modify/Update this entry