Finding an interior point in the optimal face of linear programs

Sanjay Mehrotra*, Yinyu Ye

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

48 Scopus citations

Abstract

We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n3L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.

Original languageEnglish (US)
Pages (from-to)497-515
Number of pages19
JournalMathematical Programming, Series B
Volume62
Issue number1-3
DOIs
StatePublished - Feb 1 1993

Keywords

  • Linear programming
  • optimal face
  • primal-dual methods
  • strict complementarity

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Finding an interior point in the optimal face of linear programs'. Together they form a unique fingerprint.

Cite this