A Parallel Variant of Karmarkar's Algorithm for Structured Linear Programming

Résumé du livre

Abstract: "In any variant of Karmarkar's algorithm, the projection step takes the bulk of the computing time. One way of speeding up this step of the algorithm when applied to linear programming is to take advantage of the special structures common in large scale problems. In this paper an extension of the standard form of Karmarkar's projective algorithm to block-angular and staircase structured linear programming is presented. Using Heath's updating algorithm for least squares, it is shown how the dual variables used in the partitioning can be efficiently computed. Numerical results are given."