The double pivot simplex method
| Autor: | Fabio Vitor, Todd Easton |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
021103 operations research
Linear programming Basis (linear algebra) Computer science General Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Small set Running time Variable (computer science) Simplex algorithm 010201 computation theory & mathematics Benchmark (computing) Algorithm Software |
| Zdroj: | Mathematical Methods of Operations Research. 87:109-137 |
| ISSN: | 1432-5217 1432-2994 |
| DOI: | 10.1007/s00186-017-0610-4 |
| Popis: | The simplex method, created by George Dantzig, optimally solves a linear program by pivoting. Dantzig’s pivots move from a basic feasible solution to a different basic feasible solution by exchanging exactly one basic variable with a nonbasic variable. This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one. Double pivots are performed by identifying the optimal basis in a two variable linear program using a new method called the slope algorithm. The slope algorithm is fast and allows an iteration of DPSM to have the same theoretical running time as an iteration of the simplex method. Computational experiments demonstrate that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink