zbMATH — the first resource for mathematics

Combining interior-point and pivoting algorithms for linear programming. (English) Zbl 0893.90130
Summary: 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 pivoting procedure [see N. Megiddo, ORSA J. Comput. 3, No. 1, 63-65 (1991; Zbl 0755.90056)] 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.

90C05 Linear programming
Full Text: DOI