U.Würker : Parallelization approaches to the simplex method

Author(s) :

U.Würker

Title :

Parallelization approaches to the simplex method

Preprint series

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 98-21, 1998

Mathematics Subject Classification :

90C05 [ Linear programming ]

65Y05 [ Parallel computation (numerical methods) ]

Abstract :

The main computational work in the simplex method is spread unevenly over a number of main substeps. therefore, the usual parallelization approaches seems to be not very effective, especially in the case of unstructures nonsymmetric large-scaled constraints.

In the paper we discuss a number of alternative modifications for the simplex algorithm, which are very inefficient in case of sequential computatio, but give the opportunity for a high-level paralleliziation. So a primal problem and its dual can be solved independently at the same time, some different starting points and/or selection rules can be used simultaneously, and a preview technique (calculation of the improvement over two iterations) is implementable. In all cases, the independent computing threads exchange information about meanwhile obtaind partial results, from which each thread may draw conclusions valuable for the own solution process.

The approaches may also be applied analogously to other algorithms such as interior point methods or hybrid algorithms, for which even better results may be obtained.

Keywords :

Linear programming, simplex method, parallel computation, optimization, decomposition

Language :

english

Publication time :

9/1998