Pivoting rules for the revised simplex algorithm
| Autor: | Nikolaos Samaras, Nikolaos Ploskas |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Mathematical optimization
Linear programming Basis (linear algebra) linear programming revised simplex method Management Science and Operations Research Set (abstract data type) Variable (computer science) Revised simplex method Simplex algorithm lcsh:T58.6-58.62 pricing pivoting rules Benchmark (computing) lcsh:Management information systems Queue Algorithm Mathematics |
| Zdroj: | Yugoslav Journal of Operations Research, Vol 24, Iss 3, Pp 321-332 (2014) |
| ISSN: | 1820-743X 0354-0243 |
| DOI: | 10.2298/yjor140228016p |
| Popis: | Pricing is a significant step in the simplex algorithm where an improving nonbasic variable is selected in order to enter the basis. This step is crucial and can dictate the total execution time. In this paper, we perform a computational study in which the pricing operation is computed with eight different pivoting rules: (i) Bland?s Rule, (ii) Dantzig?s Rule, (iii) Greatest Increment Method, (iv) Least Recently Considered Method, (v) Partial Pricing Rule, (vi) Queue Rule, (vii) Stack Rule, and (viii) Steepest Edge Rule; and incorporate them with the revised simplex algorithm. All pivoting rules have been implemented in MATLAB. The test sets used in the computational study are a set of randomly generated optimal sparse and dense LPs and a set of benchmark LPs (Netliboptimal, Kennington, Netlib-infeasible). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|