A Short-Cut Potential Reduction Algorithm for Linear Programming
针对变量远多于约束的大规模线性规划，提出一种分解技术来减少内点算法中昂贵的矩阵运算，并在随机运输问题上验证了其实际效果。
As most interior point algorithms iterate, they repeatedly perform costly matrix operations, such as projections, on the entire constraint matrix. For large-scale linear programming problems, such operations consume the great majority of the computation time required. However, for problems where the number of variables far exceeds the number of constraints, operations over the entire constraint matrix are unnecessary. We will examine and extend decomposition techniques which greatly reduce the amount of work required by such interior point methods as the dual affine scaling and the dual potential reduction algorithms. In an effort to judge the practical viability of the decompositioning, we compare the performance of the dual potential reduction algorithm with and without decompositioning over a set of randomly generated transportation problems. Accompanying a theoretical justification of these techniques, we focus on the implementation details and computational results of one such technique.