Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.04672 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914413967048704 |
|---|---|
| author | Kitahara, Tomonari |
| author_facet | Kitahara, Tomonari |
| contents | In this paper, we analyze the simplex method with the largest distance rule and derive upper bounds on the number of different basic feasible solutions generated. The pivoting rule was proposed by Pan [10], and in some cases, it was reported to be more efficient than the renowned steepest edge rule. We show that the analytical framework developed by Kitahara and Mizuno can be extended to this rule, despite its structural differences from previously studied pivoting rules. The resulting bounds involve a geometric parameter $β$ determined by the column norms of the constraint matrix. In addition, our analysis does not require a nondegeneracy assumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04672 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule Kitahara, Tomonari Optimization and Control In this paper, we analyze the simplex method with the largest distance rule and derive upper bounds on the number of different basic feasible solutions generated. The pivoting rule was proposed by Pan [10], and in some cases, it was reported to be more efficient than the renowned steepest edge rule. We show that the analytical framework developed by Kitahara and Mizuno can be extended to this rule, despite its structural differences from previously studied pivoting rules. The resulting bounds involve a geometric parameter $β$ determined by the column norms of the constraint matrix. In addition, our analysis does not require a nondegeneracy assumption. |
| title | Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.04672 |