An interior-point approach to sensitivity analysis in degenerate linear programs

E. Alper Yildirim*, Michael J. Todd

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish
Pages (from-to)692-714
Number of pages23
JournalSiam journal on optimization
Volume12
Issue number3
DOIs
Publication statusPublished - 1 Jan 2002

Keywords

  • Degeneracy
  • Interior-point methods
  • Linear programming
  • Sensitivity analysis

Fingerprint

Dive into the research topics of 'An interior-point approach to sensitivity analysis in degenerate linear programs'. Together they form a unique fingerprint.

Cite this