### 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*