On solution-containing ellipsoids in linear programming |
| |
| Authors: | I. C. Choi D. Goldfarb |
| |
| Affiliation: | (1) Department of Industrial Engineering, Wichita State University, Wichita, Kansas;(2) Department of Industrial Engineering and Operations Research, Columbia University, New York, New York |
| |
| Abstract: | Ellipsoids that contain all optimal dual slack solutions and those that contain all optimal primal solutions and that are independent of the algorithm used are derived. Based upon these ellipsoids, two criteria each for detecting optimal basic and nonbasic variables prior to optimality in interior-point methods are obtained. Using these results, we then derive a sufficient condition for a linear program to be feasible.This research was supported in part by NSF Grant DMS-85-12277, DMS-91-06195, CDR-84-21402 and ONR Contract N00014-87-K-0214. |
| |
| Keywords: | Linear programming interior point methods containing ellipsoids optimal basic and nonbasic variables |
| 本文献已被 SpringerLink 等数据库收录！ |
|
