Modifications and implementation of the ellipsoid algorithm for linear programming
Modifications and implementation of the ellipsoid algorithm for linear programming
复制标题
线性规划椭球算法的修改和实现
作者：
D. Goldfarb;M. Todd
我们给出了线性规划的椭球算法的一些修改，并描述了一个数值稳定的实现。我们关心的是通常可以提供用户提供的边界的实际问题。我们的实现允许丢弃约束并更新最优值的界限，并且应该能够在适度的迭代次数中以不可行的指示或具有可证明良好的可行解来终止。
We give some modifications of the ellipsoid algorithm for linear programming and describe a numerically stable implementation. We are concerned with practical problems where user-supplied bounds can usually be provided. Our implementation allows constraint dropping and updates bounds on the optimal value, and should be able to terminate with an indication of infeasibility or with a provably good feasible solution in a moderate number of iterations.