On the Number of Degenerate Simplex Pivots
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915889889148928 |
|---|---|
| author | Kukharenko, Kirill Sanità, Laura |
| author_facet | Kukharenko, Kirill Sanità, Laura |
| contents | The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that one can employ any improving feasible direction at an extreme point to limit the number of consecutive degenerate pivots that the simplex algorithm performs to $n-m-1$, where $n$ is the number of variables and $m$ is the number of equality constraints of a given LP in standard equality form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15799 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Number of Degenerate Simplex Pivots Kukharenko, Kirill Sanità, Laura Optimization and Control Combinatorics 90C05 (Primary), 90C08 (Secondary) F.2.2 The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that one can employ any improving feasible direction at an extreme point to limit the number of consecutive degenerate pivots that the simplex algorithm performs to $n-m-1$, where $n$ is the number of variables and $m$ is the number of equality constraints of a given LP in standard equality form. |
| title | On the Number of Degenerate Simplex Pivots |
| topic | Optimization and Control Combinatorics 90C05 (Primary), 90C08 (Secondary) F.2.2 |
| url | https://arxiv.org/abs/2311.15799 |