On the facet pivot simplex method for linear programming
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918477547175936 |
|---|---|
| author | Yang, Yaguang |
| author_facet | Yang, Yaguang |
| contents | Dantzig's vertex pivot simplex method has been published for more than seven decades. Amazingly, it remains one of the most efficient methods to solve linear programming (LP) problem after numerous efforts trying to find some better methods. In this paper, we propose a facet pivot simplex method and demonstrate by numerical testing that the new method is very promising compared to the vertex pivot method. Since there is no polynomial pivot simplex algorithm for linear programming problems after many decades of effort, we hope that this new type of pivot algorithm will give us some hope to find a polynomial pivot simplex method for linear programming problems. A Matlab implementation of the facet pivot algorithm and Netlib benchmark test problems are available in Matlab file exchange website. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_08468 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On the facet pivot simplex method for linear programming Yang, Yaguang Optimization and Control 90C05 90C49 Dantzig's vertex pivot simplex method has been published for more than seven decades. Amazingly, it remains one of the most efficient methods to solve linear programming (LP) problem after numerous efforts trying to find some better methods. In this paper, we propose a facet pivot simplex method and demonstrate by numerical testing that the new method is very promising compared to the vertex pivot method. Since there is no polynomial pivot simplex algorithm for linear programming problems after many decades of effort, we hope that this new type of pivot algorithm will give us some hope to find a polynomial pivot simplex method for linear programming problems. A Matlab implementation of the facet pivot algorithm and Netlib benchmark test problems are available in Matlab file exchange website. |
| title | On the facet pivot simplex method for linear programming |
| topic | Optimization and Control 90C05 90C49 |
| url | https://arxiv.org/abs/2107.08468 |