Augmented Simplex: A Modified and Parallel Version of Simplex Method Based on Multiple Objective and Subdifferential Optimization Approach

In the perspective of parallel computations, new versions of basic optimization algorithms are needed. The paper presents a concept of such coarse-grained parallelization, based on a parametric imbedding into a family of problems or parametrically diversified algorithms. This general idea is exemplified for the case of the simplex algorithm of linear programming, where a linear optimization problem can be imbedded into a multiple-objective family which introduces diversified directions of search cutting through the interior of original admissible set. To improve the effectiveness of such algorithms, an initial phase of directional feasibility search by subdifferential optimization is added. The resulting augmented simplex algorithm, even without parallelization, might be competitive with interior point methods for a certain, broad class of linear programming problems. Necessary theoretical foundations, some algorithmic details and results of preliminary tests are presented