Combining Interior-Point and Pivoting Algorithms for Linear Programming

Erling D. Andersen and Yinyu Ye
Additional contact information
Erling D. Andersen: Department of Management, Odense University, DK-5230 Odense M, Denmark
Yinyu Ye: Department of Management Sciences, The University of Iowa, Iowa City, Iowa 52242

Management Science, 1996, vol. 42, issue 12, 1719-1731

Abstract: We propose a new approach to combine linear programming (LP) interior-point and simplex pivoting algorithms. In any iteration of an interior-point algorithm we construct a related LP problem, which approximates the original problem, with a known (strictly) complementary primal-dual solution pair. Thus, we can apply Megiddo's (Megiddo, N. 1991. On finding primal- and dual-optimal bases. ORSA J. Comput. 3(1) 63--65.) pivoting procedure to compute an optimal basis for the approximate problem in strongly polynomial time. We show that, if the approximate problem is constructed from an interior-point iterate sufficiently close to the optimal face, then any optimal basis of the approximate problem is an optimal basis for the original problem. If the LP data are rational, the total number of interior-point iterations to create such a sufficient approximate problem is bounded by a polynomial in the data size. We develop a modification of Megiddo's procedure and discuss several implementation issues in solving the approximate problem. We also report encouraging computational results for this combined approach.

Keywords: interior-point algorithm; simplex method; linear program (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.12.1719 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:42:y:1996:i:12:p:1719-1731

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().