Finding an interior point in the optimal face of linear programs |
| |
Authors: | Sanjay Mehrotra Yinyu Ye |
| |
Affiliation: | (1) Department of Industrial Engineering and Management Sciences, Northwestern University, 60208-3119 Evanston, IL, USA;(2) Department of Management Sciences, The University of Iowa, Iowa City, IA, USA |
| |
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.Research supported in part by NSF Grant CCR-8810107, CCR-9019469 and a grant from GTE Laboratories.Research supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615 through Rice University. |
| |
Keywords: | Linear programming primal— dual methods optimal face strict complementarity |
本文献已被 SpringerLink 等数据库收录! |
|