Permutations in the Factorization of Simplex Bases
| Autor: | Laurent Poirrier, Ricardo Fukasawa |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
050210 logistics & transportation
021103 operations research Current (mathematics) Simplex Basis (linear algebra) Linear programming 05 social sciences MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies General Engineering 02 engineering and technology Column (database) Combinatorics Factorization Simplex algorithm 0502 economics and business Mathematics |
| Zdroj: | INFORMS Journal on Computing. 31:612-632 |
| ISSN: | 1526-5528 1091-9856 |
| DOI: | 10.1287/ijoc.2018.0862 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|