Ilkay Boduroglu (Istanbul Technical University, Turkey)

Scalable parallel simplex algorithms for block-structured linear programming problems
Joint work with Julian Hall and Jonathan Hogg.
Wednesday 23 January 2008 at 16.00, JCMB 3218

Abstract

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.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996