FINDING AN INTERIOR-POINT IN THE OPTIMAL FACE OF LINEAR-PROGRAMS

Authors
MEHROTRA S YE YY
Citation
S. Mehrotra et Yy. Ye, FINDING AN INTERIOR-POINT IN THE OPTIMAL FACE OF LINEAR-PROGRAMS, Mathematical programming, 62(3), 1993, pp. 497-515
Citations number
23
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
62
Issue
3
Year of publication
1993
Pages
497 - 515
Database
ISI
SICI code
0025-5610(1993)62:3<497:FAIITO>2.0.ZU;2-W
Abstract
We study the problem of finding a point in the relative interior of th e optimal face of a line-ar program. We prove that in the worst case s uch a point can be obtained in O(n3L) arithmetic operations. This comp lexity 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.