The two major goals in the design and implementation of parallel algorithms are scalability and portability. Obviously, one also has to take into account the following three goals of the sequential algorithm domain: taking advantage of sparsity, reducing the number of iterations and attaining numerical stability.
The design and implementation of a scalable parallel simplex algorithm for Block-Diagonal LP Problems are described from the point of view of these five goals. One application of this algorithm is the well-known Multicommodity Network Flow Problem, which is widely used in large-scale transportation and communication systems.
The programming language that we use is Fortran. Communications are handled with MPI. We use an unspecified number of parallel processors and employ parallelism at the data level instead of the instruction level. We will present computational results from both a distributed memory and a shared memory architecture.
This implementation is based upon the 1965 (sequential) compact-inverse simplex algorithm of Kaul. We have also incorporated the 1975 tableau-based approximate steepest-edge pivot rule of Crowder and Hattingh to reduce the number of iterations. Note that these are old and unpopular algorithms that were introduced when sequential processors were the only choice of computation. Now that we have High Performance Computing, these older and wiser algorithms show more potential than the current algorithms, which were initially tailored for sequential computers and then parallelized. Actually, if and when this project reaches our ultimate goal, it may become a viable alternative to the seminal Dantzig-Wolfe algorithm for Block-Diagonal LP problems. This is mainly because the Dantzig-Wolfe algorithm fails when the number of blocks is increased and our implementation does not.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
