Block-angular LP problems arise in many important applications, from finance to animal feed formulation. This talk introduces Kaul's algorithm, an old but little known variant of the simplex method for block-angular LP problems. When implemented using dense data structures, it can be viewed as a hybrid of the standard and revised simplex method, restricting the dense matrix algebra to arrays with at most one dimension equal to that of the LP problem. This offers significant scope for efficient parallel implementation. However, unlike the standard simplex method, this would not be achieved by starting from a serial performance that is so wholly uncompetitive with that of a good revised simplex solver. A sparsity-exploiting implementation of Kaul's algorithm would correspond to the revised simplex method with the structure of the original LP exploited by the basis matrix inverse. This variant and the scope for its parallel implementation will be described.
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
