Permutations in the Factorization of Simplex Bases
Ricardo Fukasawa, Laurent Poirrier
INFORMS Journal on Computing · 2019 · Volume 31 · Issue 3
Abstract
The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current linear programming solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known for performing the update, most prominently the Forrest–Tomlin method. We present an alternative algorithm for the special case where the update can be performed purely by permuting rows and columns of the factors. In our experiments, this occurred for about half of the basis updates, and the new algorithm provides a modest reduction in computation time for the dual simplex method.
Keywords
linear programming, simplex method, basis factorization, factorization update
Enable JavaScript for citation tools and additional paper interactions.