Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule
Tomonari Kitahara · 2025
Read Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule by Tomonari Kitahara (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04672.txt.
Introduction
Tomonari Kitahara bounds how many distinct corner solutions the simplex method can visit under a recently proposed pivot rule. The simplex method walks between basic feasible solutions of a linear program, and the pivot rule steers the walk. The largest distance rule, proposed by Pan, sometimes beats the famed steepest edge rule in practice. Theory had not caught up.
Kitahara extends an analytical framework developed with Mizuno to this structurally different rule. The resulting bounds hinge on a geometric parameter built from the constraint matrix's column norms. No nondegeneracy assumption is required, a common crutch removed. Pivot rules are usually compared empirically; worst-case guarantees like these explain when a rule's speed is real. The paper adds the largest distance rule to the small set of rules with proven iteration bounds.
Catalog record
| CREATOR | Tomonari Kitahara |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-04672
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bounds for the number of basic feasible solutions generated by the simplex method with the largest distance rule Tomonari Kitahara Abstract In this paper, we show bounds for the number of different basic solutions generated by the simplex method with the largest distance rule. The pivoting rule was recently proposed, and in some cases, it was reported to be more efficient than the renowned steepest edge rule. If the problem is nondegenerate, these results provide bounds on the number of iterations. As far as we know, they are the first theoretical bounds for the largest distance rule. 1 Introduction 1.1 Background The simplex method is one of the most efficient algorithms for solving linear programming problems (LPs). Its efficiency is greatly affected by a pivoting rule. There are some important pivoting rules from a practical and theoretical viewpoint. Dantzig’s rule (or the most negative coefficient rule) [ 3 ] is the oldest and the best-known pivoting rule. When the problem in consideration is degenerate, the simplex method might encounter a phenomenon known as cycling, in which the algorithm visits the same set of bases infinitely. Bland’s rule [ 1 ] is the first countermeasure for cycling. Similarly, the shadow pivoting rule is also important from a theoretical standpoint. Borgwardt [ 2 ] showed that for random LPs, the expected value of the number of iterations is strongly polynomial in the number of facets of the feasible region and the number of variables. Furthermore, Spielman and Teng [ 12 ] obtained, by their smoothed analysis, the best upper bound for the expected value of the number of iteration of the shadow simplex method. From a practical view point, it has been widely observed that the steepest edge rule shows superior performance to other pivoting rules [ 9 ] . Recently, a new pivoting rule, called the largest distance rule was proposed by Pan [ 10 ] . Geometrically speaking, this pivoting rule chooses, as an entering variable, a nonbasic variable whose corresponding dual constraint has the largest unit violation. Through his computational experiments, Pan [ 11 ] showed that a variant of the largest distance rule shows better performance than the steepest edge rule. To assess deterministic complexity of the simplex method, Kitahara and Mizuno [ 7 ] analyzed the number of basic feasible solutions (BFSs) generated by the simplex method. They showed upper bounds for the number of different BFSs generated by the simplex method with Dantzig’s rule, namely \left\lceil\frac{m\gamma}{\delta}\log\left(\frac{\rule{0.0pt}{10.76385pt}c^{\top}x^{0}-z^{*}}{\rule{0.0pt}{10.76385pt}c^{\top}\bar{x}-z^{*}}\right)\right\rceil\quad\mathrm{and}~(n-m)\left\lceil\frac{m\gamma}{\delta}\log\left(\frac{m\gamma}{\delta}\right)\right\rceil, where m is the number of constraints, n is the number of variables, c is the coefficient vector of the objective function, x^{0} is an initial BFS, \bar{x} is a BFS with the second smallest objective value, z^{*} is the optimal value, and \gamma and \delta are the maximum and minimum positive elements, respectively, in all BFSs 1 1 1 In the original paper, the latter bound is n\left\lceil\frac{m\gamma}{\delta}\log\left(\frac{m\gamma}{\delta}\right)\right\rceil . But this can be slightly improved to (n-m)\left\lceil\frac{m\gamma}{\delta}\log\left(\frac{m\gamma}{\delta}\right)\right\rceil by a trivial observation. See the proof of Theorem 3.2 . . Assuming nondegenerate LPs, these bounds become upper bounds for the number of iterations of the simplex methods with Dantzig’s rule. Inspired by these results, Tano et al. [ 13 ] showed bounds for the number of iterations of the simplex method with the steepest edge rule when it is applied to a nondegenerate LP. The bounds are \left\lceil m^{\frac{3}{2}}\frac{\gamma^{2}}{\delta^{2}}\log\left(\frac{\rule{0.0pt}{10.76385pt}c^{\top}x^{0}-z^{*}}{\rule{0.0pt}{10.76385pt}c^{\top}\bar{x}-z^{*}}\right)\right\rceil~\mathrm{and}~(n-m)\left\lceil m^{\frac{3}{2}}\frac{\gamma^{2}}{\delta^{2}}\log\left(\frac{m\gamma}{\delta}\right)\right\rceil. 1.2 Main contributions First deterministic bounds for the largest distance rule As the largest distance rule is relatively new, little is known about its theoretical aspects. In this study, we show that when the simplex method with this rule is applied to an LP which has an optimal solution, the number of different BFSs generated is at most \left\lceil\frac{m\gamma}{\beta\delta}\log\left(\frac{\rule{0.0pt}{10.76385pt}c^{\top}x^{0}-z^{*}}{\rule{0.0pt}{10.76385pt}c^{\top}\bar{x}-z^{*}}\right)\right\rceil~\mathrm{and}~(n-m)\left\lceil\frac{m\gamma}{\beta\delta}\log\left(\frac{m\gamma}{\delta}\right)\right\rceil, where \beta is the minimum norm of the column vectors of the constraint matrix divided by the maximum norm of them. If the problem is nondegenerate, these become bounds for the number of iterations. As far as we know, these are the first theoretical results for an efficient, relatively new pivoting rule. No need for nondegeneracy assumption As explained above, Tano et al. [ 13 ] showed iteration bounds for the steepest edge rule, which has been widely known as a practically efficient pivoting rule. It is important to note that their analysis relies on the nondegeneracy assumption. This assumption is essential for their analysis, and so far we have not been able to modify their analysis to obtain a bound for different BFSs generated without nondegeracy assumption. On the contrary, we do not need nondegeneracy assumption to obtain the bounds for the number of different BFSs. If the problem is nondegenerate, our bounds become ones for the number of iterations. 1.3 Notations and the structure of the paper We use 0 both for a number and a zero vector. We believe the distinction is clear from context. For a vector v , v_{i} means the i th element of v . For a vector or a matrix v , v^{\top} represents the transpose of v . For vectors v,w\in\mathbb{R}^{n} , v=w means v_{i}=w_{i} for all i\in\{1,2\dots,n\} . Also, v\geq w means v_{i}\geq w_{i} for all i\in\{1,2\dots,n\} . For a real number r , \lceil r\rceil is the minimum integer greater than r . This paper is organized as follows. In Section 2, we give preliminaries for the analysis in this paper. We also explain existing research related to the topic of this paper. In Section 3, we analyze the simplex method with the largest distance rule and obtain the above two bounds for the number of different BFSs. Finally in Section 4, we conclude the paper. 2 Preliminaries and existing research 2.1 Linear programming and the simplex method Let m<n be positive integers. We consider an LP with n nonnegative variables and m constraints: \begin{array}[]{ll}\min&c^{\top}x,\\ \text{subject to}&Ax=b,\\ &x\geq 0,\end{array} (1) where A\in\mathbb{R}^{m\times n} , b\in\mathbb{R}^{m} , and c\in\mathbb{R}^{n} are given data and x\in\mathbb{R}^{n} is a variable vector. In this paper, we assume \mathrm{rank}(A)=m . We will summarize assumptions of this paper in Section 2.4 . The dual of problem ( 1 ) is expressed as \begin{array}[]{ll}\min&b^{\top}y,\\ \text{subject to}&A^{\top}y+s=c,\\ &s\geq 0,\end{array} (2) where y\in\mathbb{R}^{m} and s\in\mathbb{R}^{n} are variable vectors. Next, we define a dictionary. Let B\subset\{1,2\dots,n\} and N=\{1,2,\dots,n\}\setminus B . According to B and N , we split A , c , and x as follows: A=\begin{bmatrix}A_{B}&A_{N}\end{bmatrix},~c=\begin{bmatrix}c_{B}\\ c_{N}\end{bmatrix},~x=\begin{bmatrix}x_{B}\\ x_{N}\end{bmatrix}. By using these splits, problem ( 1 ) is written as \begin{array}[]{ll}\min&c_{B}^{\top}x_{B}+c_{N}^{\top}x_{N},\\ \text{subject to}&A_{B}x_{B}+A_{N}x_{N}=b,\\ &x=(x_{B},x_{N})\geq 0.\end{array} (3) When |B|=m and A_{B} is nonsingular, B and N are called a basis and a nonbasis, respectively. In this case, problem ( 3 ) is transformed by multiplying the equality constraint by A_{B}^{-1} from the left and rearranging appropriately: \begin{array}[]{ll}\min&c_{B}^{\top}A_{B}^{-1}b+\bar{c}_{N}^{\top}x_{N},\\ \text{subject~to}&x_{B}=A_{B}^{-1}b-\bar{A}_{N}x_{N},\\ &x=(x_{B},x_{N})\geq 0,\end{array} (4) where \bar{c}_{N}=c_{N}-A_{N}^{\top}(A_{B}^{\top})^{-1}c_{B} and \bar{A}_{N}=A_{B}^{-1}A_{N} . Formulation ( 4 ) is called a dictionary for a basis B . The vector \bar{c}_{N} is called a reduced cost vector and \bar{A}_{N} is called a nonbasic matrix. A basic solution is a solution x such that (x_{B},x_{N})=(A_{B}^{-1}b,0) in dictionary ( 4 ). The elements of x_{B} are basic variables and those of x_{N} are nonbasic variables. A basic solution x is called a basic feasible solution (BFS) if x_{B}\geq 0 . A basis B