Combining Interior-Point and Pivoting Algorithms for Linear Programming

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.