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

53 Scopus citations


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
Issue number1-3
StatePublished - Feb 1 1993


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

ASJC Scopus subject areas

  • Software
  • General Mathematics


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