Finding an interior point in the optimal face of linear programs

Sanjay Mehrotra; Yinyu Ye

doi:10.1007/BF01585180

Finding an interior point in the optimal face of linear programs

Sanjay Mehrotra^*, Yinyu Ye

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

55 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(n³L) 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 language	English (US)
Pages (from-to)	497-515
Number of pages	19
Journal	Mathematical Programming, Series B
Volume	62
Issue number	1-3
DOIs	https://doi.org/10.1007/BF01585180
State	Published - Feb 1 1993

Keywords

Linear programming
optimal face
primal-dual methods
strict complementarity

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/BF01585180

Cite this

@article{a8a26e2b836746d59a83e7c79c8a6ea4,

title = "Finding an interior point in the optimal face of linear programs",

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.",

keywords = "Linear programming, optimal face, primal-dual methods, strict complementarity",

author = "Sanjay Mehrotra and Yinyu Ye",

year = "1993",

month = feb,

day = "1",

doi = "10.1007/BF01585180",

language = "English (US)",

volume = "62",

pages = "497--515",

journal = "Mathematical Programming, Series B",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - Finding an interior point in the optimal face of linear programs

AU - Mehrotra, Sanjay

AU - Ye, Yinyu

PY - 1993/2/1

Y1 - 1993/2/1

N2 - 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.

AB - 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.

KW - Linear programming

KW - optimal face

KW - primal-dual methods

KW - strict complementarity

UR - http://www.scopus.com/inward/record.url?scp=34250077538&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250077538&partnerID=8YFLogxK

U2 - 10.1007/BF01585180

DO - 10.1007/BF01585180

M3 - Article

AN - SCOPUS:34250077538

SN - 0025-5610

VL - 62

SP - 497

EP - 515

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 1-3

ER -

Finding an interior point in the optimal face of linear programs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this