Parallel network dual simplex method on a shared memorymultiprocessor

摘要

We present a parallel algorithm for solving the dual transshipmentproblem. The traditional dual simplex method does not offer much scopefor parallelization, because it moves from one basic feasible solutionto another, performing one pivot operation at a time. We present a newmethod called modified network dual simplex method which uses concurrentpivots. This departure from the traditional LP approach raises severalissues such as the need to convert a non-basic feasible solution to abasic feasible solution. We present our strategies to handle theseissues as well as the corresponding parallel algorithms. We also presentresults of testing this algorithm on large graphs to solve theintegrated layout compaction and wire balancing problem