Combining Interior-Point and Pivoting Algorithms for Linear Programming
提出一种新方法，将线性规划的内点算法与单纯形旋转算法结合，通过构造近似问题并利用Megiddo过程在强多项式时间内找到最优基，适用于有理数数据且迭代次数多项式有界。
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.