---
abstract: 'In this paper, a double-pivot simplex method is proposed. Two upper bounds of iteration numbers are derived. Applying one of the bounds to some special linear programming (LP) problems, such as LP with a totally unimodular matrix and Markov Decision Problem (MDP) with a fixed discount rate, indicates that the double-pivot simplex method solves these problems in a strongly polynomial time. A variant of Klee-Minty cube is used to show that the estimated bounds of the iteration numbers are very tight. Numerical test on three variants of Klee-Minty cubes is performed for the problems with sizes as big as $200$ constraints and $400$ variables. Dantzig’s simplex method cannot handle Klee-Minty cube problem with $200$ constraints because it needs about $2^{200} \approx 10^{60}$ iterations. But the proposed algorithm performs extremely good for all three variants.'
author:
- 'Yaguang Yang[^1]'
title: 'A double-pivot simplex algorithm and its upper bounds of the iteration numbers'
---

[**Keywords:**]{} Double-pivot algorithm, simplex method, linear programming.

Introduction
============

Since Dantzig invented the simplex method in 1940s [@dantzig49], its complexity has been a topic attracted many researchers. Since simplex methods search the optimizer among vertices which are defined by the linear constraints, the iterate moves from one vertex to the next vertex along an edge of the polytope. Therefore, the diameter of a polytope, defined as the shortest path or the least number of edges between any two vertices of the polytope, is the smallest number of iterations that the best simplex algorithm can possibly achieve. Hirsch in 1957 [@dantzig63] conjectured that the diameter of the polytope is $m-n$ for the polytope $P=\{ \x\in \R^n: \A\x \le \b \}$ where $\A \in \Z^{m \times n}$ and $m>n$. This conjecture was disapproved by Santos [@santos12] after $50$ years worth of efforts of many experts. Now, some experts, for example Santos [@santos12a], believe that the diameter of the convex polytope can be bounded by a polynomial of $(m-n)n$. This new conjecture of the bound for the diameter of the convex polytope is far away from the best-known quasi-polynomial upper bounds which are due to Kalai and Kleitman [@kalai92], Todd [@todd14], and Sukegawa [@sukegawa17]. In a recent effort [@yang18], this author showed that for a given polytope, the diameter is bounded by $\mathcal{O} \left( \frac{n^3 \Delta}{\det(\A^*)} \right)$, where $\Delta$ is the largest absolute value among all $(n-1) \times (n-1)$ sub-determinants of $\A$ and ${\det(\A^*)}$ is the smallest absolute value among all nonzero $n \times n$ sub-determinants of $\A$.

Finding the diameter of convex polytopes provides only a surmised lowest iteration number for which an optimal pivot rule may achieve. Finding actually such a pivot rule (the way to choose the next neighbor vertex) is also a difficult problem. Researchers proposed many pivot rules with the hope that they may achieve the number of iterations (in the worst case) bounded by a polynomial (see [@tz93] and references therein). However, since Klee and Minty [@km72] constructed a cube and showed that Dantzig’s rule needs an exponential number of iterations in the worst case to solve the Klee and Minty cube problem, people have showed similar results for almost every popular pivot rule [@friedmann11; @gs79; @jeroslow73; @psz08]. It is now believed that finding a pivot rule that will solve all linear programming problems in the worst case in polynomial time is a very difficult problem [@smale99].

Existing pivot rules consider one of many merit criteria to select an entering variable, such as the most negative index in the reduced cost vector (Dantzig’s rule), the best improvement rule, Bland’s least index pivoting rule, the steepest edge simplex rule, Zadeh’s rule, among others [@tz93]. Each merit criterion has its own appealing feature. However, existing simplex algorithms cannot use multiple merits at the same time because each of these algorithms updates only one variable at a time. In a slightly different view, a merit criterion may be a good choice in most scenarios but may be a poor choice in some spacial case, such as the Klee-Minty cube. Therefore, randomized pivot rules [@ghz98; @kp06] that randomly select an entering variable from the set of possible entering variables that will improve the objective function have been proposed and proved to be able to find an optimizer in a polynomial time on average [@kp06]. This shows that using a combination of merits in the selection of pivot can be beneficial.

In this paper, we consider a novel simplex algorithm for linear programming problem. This algorithm is different from all existing simplex algorithms in that it updates two variables at one iteration. This strategy looks two pivots ahead instead of focus only on the next step. We believe that this strategy is better than all existing pivot rules because it looks longer term benefit instead of a short-sighted one-step achievement. Since the proposed algorithm updates two variables at a time, it can use multiple merits in the selection of pivots at the same time in a deterministic way which is different from the randomized rules. We wish that these features give us some hope to find some strong polynomial algorithms to solve linear programming problems. We may extend the proposed algorithm to select more than two entering variables, but there is a trade-off between reducing iteration numbers and reducing the cost of each iteration.

In this paper, we use small letters with bold font for vectors and capital letters with bold font for matrices. The remainder of the paper is organized as follows. Section 2 describes the proposed algorithm. Section 3 analyzes the iteration numbers of the algorithm. Section 4 provides the information on the numerical test for three variants of Klee-Minty cubes. The concluding remarks are in Section 5.

The proposed algorithm
======================

We consider the primal linear programming problem in the standard form: $$\begin{aligned}
\begin{array}{cl}
\min  &  \c^{\T}\x, \\ 
\mbox{\rm subject to} 
&  \A\x=\b, \hspace{0.1in} \x \ge \0,
\end{array}
\label{LP}\end{aligned}$$ where $\A \in {\R}^{m \times n}$, $\b \in {\R}^{m}$, $\c \in {\R}^{n}$ are given, and $\x \in {\R}^n$ is the vector to be optimized. Associated with the linear programming is the dual programming that is also presented in the standard form: $$\begin{aligned}
\begin{array}{cl}
\max   &   \b^{\T}\y, \\
\mbox{\rm subject to}   &  
\A^{\T}\y +\s=\c, \hspace{0.1in} \s \ge \0,
\end{array}
\label{DP}\end{aligned}$$ where dual variable vector $\y \in {\R}^{m}$, and dual slack vector $\s \in {\R}^{n}$.

A feasible solution of the linear program satisfies the conditions of $\A \x =\b$ and $\x \ge \0$. We will denote by $B \subset \{ 1, 2, \ldots, n \}$ the index set with cardinality $| B | = m$ and $N = \{ 1, 2, \ldots, n \} \setminus B$ with cardinality $| N |=n-m$ the complementary set of $B$ such that matrix $\A$ and vector $\x$ can be partitioned as $\A=[ \A_B, \A_N]$ and $\x =[\x_B^{\Tr}, \x_N^{\Tr}]^{\Tr}$, moreover the columns of $\A_B$ are linearly independent and $\A_B \x_B = \b$, hence $\x_N=\0$. We call this $\x=[\x_B,\0]$ as the basic feasible solution. Similarly, we can partition $\c$ and $\s$ as follows: $$\c = \left[ \begin{array}{c}
\c_B \\  \c_N
\end{array} \right], \hspace{0.2in}
\s = \left[ \begin{array}{c}
\s_B \\  \s_N
\end{array} \right].$$ We denote by $\mathcal{B}$ the set of all bases $B$. In the discussion below, we make the following assumptions:

-   $rank(\A) = m$.

-   The primal problem (\[LP\]) has an optimal solution.

-   Initial basic feasible solution $\x^0$ is given and is not an optimizer.

-   All basic feasible solutions are bounded above and below, more specifically, for all $i \in B \subset \mathcal{B}$, $ \delta \le x_i \le \gamma$.

The first three assumptions are standard. The last assumption implies that the primal problem (\[LP\]) is not degenerate. We also denote by $\x^*= (\x_{B^*}, \x_{N^*})$ the optimal basic solution of (\[LP\]) with $\x_{B^*}=\A_{B^*}^{-1} \b \ge \0$ and $\x_{N^*}=\0$, by $(\y^*, \s^*)$ the optimal basic solution of the dual problem (\[DP\]) with $\y^*=\A_{B^*}^{-\Tr} \c_{B^*}$, $\s_{B^*}=\0$, and $\s_{N^*}=\c_{N^*}-\A_{N^*}^{\Tr}\A_{B^*}^{-\Tr}\c_{B^*}$, by $z^* = \c^{\Tr} \x^* = \b^{\T}\y^*$ the optimal value. Using $B-N$ partition, we can write the primal problem as $$\begin{aligned}
\begin{array}{cl}
\min &  \c_B^{\T}\x_B + \c_N^{\T}\x_N,  \\
\mbox{\rm subject to} 
&  \A_B\x_B + \A_N\x_N=\b, 
\hspace{0.1in} \x_B \ge \0, \hspace{0.1in}  \x_N \ge \0.
\end{array}
\label{LP1}\end{aligned}$$ Since $\A_B$ is non-singular, we can rewrite (\[LP1\]) as $$\begin{aligned}
\begin{array}{cl}
\min & \c_B^{\T}\A_B^{-1} \b 
+ (\c_N - \A_N^{\T} \A_B^{-\Tr} \c_B)^{\Tr} \x_N, \\
\mbox{\rm subject to} 
& \x_B = \A_B^{-1} \b - \A_B^{-1}\A_N\x_N, 
\hspace{0.1in} \x_B \ge \0, \hspace{0.1in}  \x_N \ge \0.
\end{array}
\label{LP2}\end{aligned}$$ Let superscript $k$ represent the $k$th iteration, the matrices and vectors in the $k$th iteration are then denoted by $\A_{B^k}$, $\A_{N^k}$, $\c_{B^k}$, $\c_{N^k}$, $\x_{B^k}$, $\x_{N^k}$, $\s_{B^k}$, and $\s_{N^k}$, where $\x^k=[\x_{B^k},\x_{N^k}]$ is the basic feasible solution of (\[LP\]) with $\x_{B^k} > \0$ and $\x_{N^k}= \0$. It is worthwhile to note that the partition of $(B^k,N^k)$ keeps updating and it is different from the partition $(B^*,N^*)$ before an optimizer is found. Let $$\bar{\c}_{N^k}^{\Tr} =( \c_{N^k} - \A_{N^k}^{\Tr} 
\A_{B^k}^{-\Tr} \c_{B^k} )^{\Tr}
\label{cNbar}$$ be the reduced cost vector. Clearly, if $\bar{\c}_{N^k} \ge \0$, an optimizer is found; if $\bar{c}_{j^k} <0$ for some $j^k \in N^k$, then the entering variable $x_{\jmath^k}$ in the next vertex is chosen from the set of $\{ j^k ~|~ \bar{c}_{j^k} <0 \}$ because by increasing $x_{\jmath^k}$, the objective function $\c^{\Tr} \x=\c_{B^k}^{\T}\x_{B^k}+\bar{c}_{\jmath^k}x_{\jmath^k}$ will be reduced. Many different ways have been developed for the selection of the entering variable $x_{\jmath^k}$ under the constraint: $$\jmath^k \in \{ j^k ~|~ \bar{c}_{j^k} <0 \}.$$ Once the entering variable is selected, existing pivot rules determine the leaving variable using the following method: Denote $\bar{\b} = \A_{B^k}^{-1} \b$ and $\bar{\a}_{\jmath^k} = \A_{B^k}^{-1} \A_{\jmath^k}$, $\jmath^k \in N^k$ corresponding to the entering variable, the leaving variable $x_{\imath}$, ${\imath} \in B^k$, is determined by the following condition. $$\begin{aligned}
x_{\imath} = \min_{i \in \{ 1,\ldots,m \}} 
\bar{b}_i / \bar{a}_{\jmath^k,i},   
\hspace{0.1in}  \mbox{subject to}  
\hspace{0.1in} \bar{a}_{\jmath^k,i}>0.
\label{outVar}\end{aligned}$$ The corresponding step-size is given by $$\begin{aligned}
\min_{i \in  \{ 1,\ldots,m \}} 
\bar{b}_i / \bar{a}_{\jmath^k,i},  
\hspace{0.1in} \mbox{subject to}
\hspace{0.1in}  \bar{a}_{\jmath^k,i}>0  .
\label{stepsize}\end{aligned}$$

As we pointed out above, our strategy is to select, in a deterministic way, two entering variables from the set of non-basic variables that will reduce the objective function. According to some extensive computational experience, for example [@ps14], Dantzig’s rule is the most efficient on average among all popular pivot rules (even though Dantzig’s rule needs exponentially many pivots to find the optimal solution for Klee-Minty cubes in the worst case), therefore, we select the first entering variable $x_{\jmath_1^k}$ using Dantzig’s rule: $${\jmath_1^k} :=\{ {\jmath_1^k} ~|~ \bar{c}_{\jmath_1^k} 
= \min_{j^k \in N^k} \bar{\c}_{j^k}  \}.
\label{enteringVar}$$ Kitahara and Mizuno [@km13] showed that the number of iterations in existing pivot rules is significantly affected by the minimum values of all the positive elements of primal basic feasible solutions. Carefully studying Klee-Minty cube and its variants [@greenberg97; @km11; @ibrahima13] indicates that the other entering variable should be determined by taking the variable among all $j^k \in N^k$ with $\bar{c}_{j^k}<0$ such that a particular $\jmath_2^k$ will maximize the step-size, i.e., $$x_{\jmath_2^k} = \max_{\bar{\c}_{j^k}<0}
\Big\{
\min_{i \in  \{ 1,\ldots,m \}} \bar{b}_i / \bar{a}_{j^k,i},
\hspace{0.1in} \mbox{subject to}
\hspace{0.1in}    \bar{a}_{j^k,i}>0
\Big\}.
\label{iniVar2}$$ This strategy will be justified again in the proof of Theorem \[thm2\] and in the discussion of Remark \[longestStep\]. If ${\jmath_2^k}={\jmath_1^k}$ (which means that the most negative rule will generate the longest step), then we take the second entering variable $x_{\jmath_2^k}$ which has the second largest step-size.

Now we discuss how to choose the leaving variables. To make our notation simple, we drop the iteration index $k$ if it does not cause confusion. Let $\bar{\A}_{(\jmath_1,\jmath_2)} = 
\A_B^{-1} \A_{(\jmath_1,\jmath_2)}$ where $\A_{(\jmath_1,\jmath_2)}$ is composed of the $\jmath_1$ and $\jmath_2$ columns of $\A_N$, and $\bar{\c}_{(\jmath_1,\jmath_2)} < \0$ be the two corresponding elements in $\bar{\c}_N$. For two entering indices $(\jmath_1,\jmath_2) \in N^k$ such that that $\x_{(\jmath_1,\jmath_2)}^{\Tr} =[x_{\jmath_1},x_{\jmath_2}] \ge \0$, we need $$\x^{k+1}=\x_{B^k}=\A_{B^k}^{-1}\b
-\A_{B^k}^{-1}\A_{N^k}\x_{N^k} 
= \bar{\b} - \bar{\A}_{(\jmath_1,\jmath_2)}
\x_{(\jmath_1,\jmath_2)} \ge \0.
\label{updatedXB}$$ Therefore, the problem of finding a good new vertex is reduced to minimize the following linear programming problem. $$\begin{aligned}
\begin{array}{cl}
\min  &  \bar{\c}_{(\jmath_1,\jmath_2)}^{\T}
\x_{(\jmath_1,\jmath_2)}, \\ 
\mbox{\rm subject to} 
&  \bar{\A}_{(\jmath_1,\jmath_2)}
\x_{(\jmath_1,\jmath_2)} \le \bar{\b}, 
\hspace{0.1in} \x_{(\jmath_1,\jmath_2)} \ge \0.
\end{array}
\label{twoDim}\end{aligned}$$ Here the third merit criterion is introduced, which is to determine the values of the two entering variables to minimize the objective function under the constraints of (\[twoDim\]). These constraints make sure that the updated $\x_B \ge \0$ and the leaving variables are zeros. As this problem has only two variables, the solution is slightly more complicate than the selection of the single leaving variable in existing pivot rules, but is still simple and straightforward. Divide $\bar{\A}_{(\jmath_1,\jmath_2)}$ into two parts: $\bar{\A}_1$ has the rows with at least one positive element, and $\bar{\A}_2 \le \0$ has the rows with all elements smaller than or equal to zero . Partition $\bar{\b}=\A_B^{-1} \b$ into the corresponding $\bar{\b}_1$ and $\bar{\b}_2$. Since elements in $\bar{\A}_2$ are smaller than to equal to zero, in view of (\[updatedXB\]) or (\[twoDim\]), introducing positive entering variables will keep the corresponding elements in $\x_B$ to be positive. For $\bar{\A}_1$, in view of (\[updatedXB\]) or (\[twoDim\]), introducing positive variables may change the sign of $\x_B$. If the number of rows in $\bar{\A}_1$ is greater than or equal to $2$, for any two independent rows $(i_1,i_2)$ of $\bar{\A}_1$, solving $$\bar{\A}_1(i_1,i_2) \left[ \begin{array}{c}
x_{\jmath_1} \\ x_{\jmath_2} \end{array} \right]
= \bar{\b}_1(i_1,i_2)
\label{subEq}$$ will give a possible vertex in the convex polygon defined in (\[twoDim\]). Therefore $\x_2 := [x_{\jmath_1}, x_{\jmath_2}] \ge \0$ is a feasible vertex of the polygon if $\bar{\A}_1 \x_2 \le \bar{\b}_1$ holds. Otherwise, it is not feasible and will not be considered further. Two special feasible vertices should also be considered, i.e., $\x_2 := [x_{\jmath_1}, 0]$ and $\x_2 := [0, x_{\jmath_2}]$ which correspond to the most negative rule and the longest step-size rule respectivily. For all feasible vertices of the convex polygon defined in (\[twoDim\]), we select the vertex that minimizes the objective function of (\[twoDim\]). The corresponding row indices $(\imath_1,\imath_2)$ that form the selected vertex determine the leaving variables. If the number of rows in $\A_1$ is exact one, the longest step pivot rule is used.

The proposed algorithm is therefore as follows:

[ ]{}\
Data: Matrix $\A$, vectors $\b$ and $\c$. [ ]{}\
initial basic feasible solution $\x^0$, and its related partitions $\x_{B^0}$, $\x_{N^0}$, $\A_{B^0}$, $\A_{N^0}$, $\c_{B^0}$, $\c_{N^0}$, $(\A_{B^0})^{-1}$, and $\bar{\c}_{N^0}=\c_{N^0} - \c_{B^0} (\A_{B^0})^{-1} \A_{N^0}$.

-   While $\min (\bar{\c}_{N^k}) < 0$

    -   If at least two elements of $\bar{\c}_{N^k}$ are smaller than zero

        -   The first entering variable $x_{\jmath_1^k}$ is determined by Dantzig’s rule. For all negative elements of $\bar{\c}_{N^k}$ other than the most negative elements $\bar{\c}_{\jmath_1^k}$, determine the $x_{\jmath_2^k}$ such that the second entering variable will take the longest step. Two special vertices, $[x_{\jmath_1^k}, 0]$ and $[0, x_{\jmath_2^k}]$ are obtained.

        -   Divide $\bar{\A}_({\jmath_1,\jmath_2})$ into two parts: $\bar{\A}_1$ whose row has positive elements and $\bar{\A}_2 \le \0$. Partition $\A_{B^k}^{-1} \b$ into the corresponding $\bar{\b}_1$ and $\bar{\b}_2$.

        -   If the number of rows of $\bar{\A}_1$ is greater than or equal to $2$

            -   Compute all vertices in two dimensional plane by solving (\[subEq\]).

            -   Determine all feasible vertices which satisfy $\x_2=[x_{\jmath_1},x_{\jmath_2}]^{\Tr} \ge \0$ and $\bar{\A}_1 \x_2 \le \bar{\b}_1$.

            -   Find a pair of entering variables among all feasible vertices $\x_2$ (including the two special vertices) that minimizes the objective $[\bar{c}_{\jmath_1}, \bar{c}_{\jmath_2}] \x_2$.

            -   Update base $\A_{B^k}$ and $\c_{B^k}$, non-base $\A_{N^k}$ and $\c_{N^k}$. Compute $\A_{B^k}^{-1}$ and $\bar{\c}_{N^k} = \c_{N^k} - \c_{B^k} \A_{B^k}^{-1} \A_{N^k}$.

        -   Else if there is only one row in $\bar{\A}_1$

            -   The longest step rule is applied.

            -   Update base $\A_{B^k}$ and $\c_{B^k}$, non-base $\A_{N^k}$ and $\c_{N^k}$. Compute $\A_{B^k}^{-1}$ and $\bar{\c}_{N^k} = \c_{N^k} - \c_{B^k} \A_{B^k}^{-1} \A_{N^k}$.

        -   end (if)

    -   Else if only one element of $(\bar{\c}_{N^k})$ is negative,

        -   Dantzig’s rule (which is also the longest rule) is applied.

        -   Update base $\A_{B^k}$ and $\c_{B^k}$, non-base $\A_{N^k}$ and $\c_{N^k}$. Compute $\A_{B^k}^{-1}$ and $\bar{\c}_{N^k} = \c_{N^k} - \c_{B^k} \A_{B^k}^{-1} \A_{N^k}$.

    -   end (if)

    -   $k \Leftarrow k+1$.

-   end (while)

\[mainAlg\]

We can modify the algorithm by selecting two entering variables using the indices corresponding to the [**two**]{} most negative elements in $\bar{\c}_{N^k}$. In the numerical test section, we will show that this is a not a good strategy. \[mostNeg\]

Analysis of the algorithm
=========================

In this section, we provide two upper bounds of the iteration numbers for the proposed algorithm using the strategy developed in [@km11; @km13; @ye11].

Let $r$ be a real number and $\lceil r \rceil$ be the smallest integer bigger than $r$. Let $\gamma_P^*$ be the maximum value of all elements of $\x^*$ and $$\gamma_D = \max_{k} \{ \gamma_D^k \} =
\max_{k} \Big\{ \max_{j^k \in N^k} 
\{ -\bar{c}_{j^k} ~|~ \bar{c}_{j^k} < 0 \} \Big\}.
\label{gammaD}$$ Let $(B^k,N^k)$ and $(B^*,N^*)$ be the partitions of base and non-base variables at iteration $k$ and at the end of the program when the optimization is achieved. Let $\x^*$ be partitioned using $(B^k,N^k)$ but not $(B^*,N^*)$, i.e., $$\x^*= \left[ \begin{array}{c}
\x_{B^k}^* \\ \x_{N^k}^* \end{array} \right].$$ The first lemma is derived using exactly the same argument but stating a slightly improved result of [@km11; @km13].

(Kitahara and Mizuno) Let $\x^*$ be partitioned using $(B^k,N^k)$ and $z^*$ be the optimal value of (\[LP\]), we have $$\c^{\Tr} \x^k - z^* 
\le \gamma_D^k \| \x_{N^k}^* \|_1.
\label{1stEst}$$ \[firstL\]

Since $\x^*$ is partitioned using $(B^k,N^k)$, we have $(\x_{B^k}^* , \x_{N^k}^*) \ge \0$, and $$\begin{aligned}
\A_{B^k}\x_{B^k}^* +\A_{N^k}\x_{N^k}^*= \b. \nonumber\end{aligned}$$ This gives $$\begin{aligned}
\x_{B^k}^*  
= \A_{B^k}^{-1} \b -\A_{B^k}^{-1} \A_{N^k}\x_{N^k}^*.
\nonumber \end{aligned}$$ Therefore, we have $$\begin{aligned}
\c^{\Tr} \x^* & = & 
\c_{B^k}^{\Tr}\x_{B^k}^* + {\c}_{N^k}^{\Tr}\x_{N^k}^*  
\nonumber \\
& = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
-{\c}_{B^k}^{\Tr}\A_{B^k}^{-1}\A_{N^k}\x_{N^k}^*
+{\c}_{N^k}^{\Tr}\x_{N^k}^*   
\nonumber \\
 & = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
+ ({\c}_{N^k}^{\Tr}-{\c}_{B^k}^{\Tr}\A_{B^k}^{-1}\A_{N^k})
\x_{N^k}^*.\end{aligned}$$ Using this relation and (\[cNbar\]), we have $$\begin{aligned}
z^* & = & \c^{\Tr} \x^*   \nonumber \\
& = & \c_{B^k}^{\Tr}  \A_{B^k}^{-1} \b 
+ \bar{\c}_{N^k}^{\Tr}\x_{N^k}^*  \nonumber \\ 
& \ge &  \c^{\Tr} \x^k -  \gamma_D^k \| \x_{N^k}^* \|_1.
\label{est1}\end{aligned}$$ This finishes the proof. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

If $B^* \ne B^k$, i.e., $\x^k$ is not an optimizer, from (\[est1\]), it must have $\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* <0$. Therefore, there are $j^k \in N^k$ such that $$\bar{c}_{j^k} <0 \hspace{0.1in} \mbox{and}
\hspace{0.1in} x_{j^k}^*>0.
\label{NkBstar}$$ This means that for $j^k \in N^k \cap B^*$, $x_{j^k}$ should be the entering variable. The problem is that one does not know $B^*$ before an optimizer is found. \[totalD\]

We may also partition $\x^k$ using $(B^*,N^*)$ as $$\x^k= \left[ \begin{array}{c}
\x_{B^*}^k \\ \x_{N^*}^k \end{array} \right].$$ This gives $$\begin{aligned}
\A_{B^*}\x_{B^*}^k +\A_{N^*}\x_{N^*}^k= \b, \nonumber\end{aligned}$$ and $$\begin{aligned}
\x_{B^*}^k  
= \A_{B^*}^{-1} \b -\A_{B^*}^{-1} \A_{N^*}\x_{N^*}^k.
\nonumber \end{aligned}$$ Similar to the derivation of (\[1stEst\]), we have $$\begin{aligned}
\c^{\Tr} \x^k  = \c^{\Tr} \x^* + 
({\c}_{N^*}- {\c}_{B^*}\A_{B^*}^{-1} \A_{N^*})^{\Tr} \x_{N^*}^k
= z^* + \bar{\c}_{N^*}^{\Tr}\x_{N^*}^k.
\nonumber \end{aligned}$$ If $x_{j}^k > 0$, we have $x_{j}^k \in B^k$. For $j \in {N^*} \cap B^k$, since $\bar{\c}_{N^*} \ge \0$, we have $$\begin{aligned}
z^* & \ge  \c^{\Tr} \x^k -   
\max \{ x_j^k   ~|~ j  \in N^* \cap B^k \}
\| \bar{\c}_{N^*}  \|_1.\end{aligned}$$

If $N^* \ne N^k$, i.e., $\x^k$ is not an optimizer, it must have $\bar{\c}_{N^*}^{\Tr}\x_{N^*}^k >0$. Therefore, there are $j^* \in N^*$ such that $$\bar{c}_{j^*} >0 \hspace{0.1in} \mbox{and}
\hspace{0.1in} x_{j^*}^k>0.
\label{NkBstar2}$$ This means that for $j^* \in N^* \cap B^k$, $0 < x_{j^*}^k \in B^k$ should be the leaving variable. The problem is that one does not know $N^*$ before an optimizer is found. \[totalDiff\]

Let $\gamma_{\ell}=\min_{k} x_{\jmath_2^k}$, where $x_{\jmath_2^k}$ is defined in (\[iniVar2\]), i.e., $x_{\jmath_2^k}$ is the longest step among all possible entering variables with $\bar{c}_{j^k} <0$ and $j^k \in N^k$; and define $$\delta_D =\min_{k} \delta_D^k
= \min_{k}  \Big\{ \min \{ -\bar{c}_{j^k} ~| ~j^k \in N^k
\hspace{0.1in}\mbox{and} \hspace{0.1in} \bar{c}_{j^k}<0 \}
\Big\}.$$ Considering Algorithm \[mainAlg\], our next lemma is an improvement of the one in [@km13].

Let $\x^k$ and $\x^{k+1}$ be the $k$th and $(k+1)$th iterates generated by Algorithm \[mainAlg\]. If $\x^k$ is not optimal and $\x^k \neq \x^{k+1}$, then, we have $$\c^{\Tr} \x^k - \c^{\Tr} \x^{k+1} \ge \delta_D \gamma_{\ell}.
\label{myIneq}$$ \[diffObj\]

Since $\x^k \neq \x^{k+1}$, from the derivation of (\[twoDim\]), the difference of the objective functions between $k$th and $(k+1)$th iterations is actually the solution of (\[twoDim\]), which is smaller than the special case when only one entering variable $x_{\jmath_2^k}$, which would generate the longest step among $\bar{c}_{j^k}<0$ for all $j^k \in N^k$, is selected. Let $\bar{\x}_{(\jmath_1^k,\jmath_2^k)}$ be the optimal solution of (\[twoDim\]) at iteration $k$. Therefore $$\begin{aligned}
\c^{\Tr} \x^k - \c^{\Tr} \x^{k+1} 
& = & - \bar{\c}_{(\jmath_1^k,\jmath_2^k)}^{\T}
\bar{\x}_{(\jmath_1^k,\jmath_2^k)}  
\nonumber \\
& \ge &  -\bar{c}_{\jmath_2^k}\bar{x}_{\jmath_2^k}
\nonumber \\
& \ge &  \delta_D \gamma_{\ell}.
\label{myIneq1}\end{aligned}$$ This finishes the proof. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

Lemma \[diffObj\] says that for Algorithm \[mainAlg\], the objective value decreases in every iteration at least by a constant $\delta_D \gamma_{\ell}$.\[constantD\]

From Lemmas \[firstL\], \[diffObj\] and Remark \[constantD\], it is easy to show that the following upper bound of iteration numbers of Algorithm \[mainAlg\] holds.

Suppose that we generate a sequence of basic feasible solutions by Algorithm \[mainAlg\] from an initial iterate $\x^0$. Then, the number of total iterations is bounded above by $$\Bigl\lceil 
\frac{\c^{\Tr} \x^0 - z^*}{\delta_D \gamma_{\ell}}
\Bigr\rceil \le
\Bigl\lceil
\frac{\gamma_D^0\| \x^* \|_1 }
{\delta_D \gamma_{\ell}}
\Bigr\rceil
\label{bound}$$ \[mainThe\]

The bound of the left side is obvious. By the defintion of $\gamma_D^k$, we have $$\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* \ge 
-{\gamma_D^k \| \x_{N^k}^* \|_1 }.$$ Therefore, for initial step, the last inequality of (\[est1\]) can be replaced by $$\c^{\Tr} \x^0 - z^* \le \gamma_D^0 \| \x^* \|_1 .$$ Since every iteration will reduce the objective function at least a constant $\delta_D \gamma_{\ell}$, we need at most $$\Bigl\lceil
\frac{\gamma_D^0 \| \x^* \|_1 }
{\delta_D \gamma_{\ell}}
\Bigr\rceil$$ iterations to find the optimal solution. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

The upper bound given in Theorem \[mainThe\] is smaller than the one in [@km13] because (a) $\gamma_{\ell}$ is the smallest value in all longest steps among all iterates while the corresponding number in [@km13] is the smallest value in all nonzero components among all iterates $\x^k$, (b) $\| \x^* \|_1 $ depends only on the optimal solution of $\x^*$, and (c) $\gamma_D^0$ depends only on the $\c$.

Now, we present a upper bound in terms of only $\delta$ and $\gamma$.

Assume that the $k$th iterate generated by Algorithm \[mainAlg\] is not an optimizer. Let $$t = m \frac{\gamma}{\delta}
\log\left( m \frac{\gamma}{\delta} \right)
\label{tIter}$$ then there is a $\bar{j} \in B^k$, a corresponding $x_{\bar{j}}^k>0$, after at most another $\lceil t \rceil$ iterations, $x_{\bar{j}}^{k+t}$ becomes zero and stay zero since then. \[thm2\]

In view of (\[est1\]) in Lemma \[firstL\], since $\x^*$ has at most $m$ nonzero elements and $\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* \ge -\gamma_D^k (m \gamma)$, we have $${\c}^{\Tr} \x^k -z^* \le m \gamma \gamma_D^k.$$ Using this inequality, together with (\[myIneq1\]) in Lemma \[diffObj\] and (\[enteringVar\]), we have $$\begin{aligned}
\c^{\Tr} \x^k - \c^{\Tr} \x^{k+1} 
& = & - \bar{\c}_{(\jmath_1^k,\jmath_2^k)}^{\T}
\bar{\x}_{(\jmath_1^k,\jmath_2^k)}  
\nonumber \\
& \ge &  -\bar{c}_{\jmath_1^k}\bar{x}_{\jmath_1^k}
\nonumber \\
& \ge &  \gamma_D^k \delta
\nonumber \\
& \ge &  \frac{\delta}{m\gamma}
\left( {\c}^{\Tr} \x^k -z^*  \right).
\nonumber $$ This shows $$\begin{aligned}
\c^{\Tr} \x^k - z^* - (\c^{\Tr} \x^{k+1} -z^*)
\ge  \frac{\delta}{m\gamma}
\left( {\c}^{\Tr} \x^k -z^*  \right)
\nonumber $$ or equivalently $$\begin{aligned}
\c^{\Tr} \x^{k+1} -z^*
\le  \left( 1 - \frac{\delta}{m\gamma} \right)
\left( {\c}^{\Tr} \x^k -z^*  \right).
\nonumber $$ Therefore, for any integer $t>0$, we have $$\begin{aligned}
\frac{\c^{\Tr} \x^{k+t} -z^*} {\c^{\Tr} \x^k -z^*}
\le  \left( 1 - \frac{\delta}{m\gamma} \right)^t.
\label{myIneq2}\end{aligned}$$ Since $| B^k |=m$ and $$\c^{\Tr} \x^k -z^* = \x^{k^{\Tr}} \s^* 
= \sum_{j \in B^k} x_j^k s_j^*,$$ there must have a $\bar{j} \in B^k$ such that $$x_{\bar{j}}^k s_{\bar{j}}^* \ge \frac{1}{m} (\c^{\Tr} \x^k -z^* ).$$ Using Assumption 4, $\gamma \ge x_{\bar{j}}^k > 0$, we have $$\begin{aligned}
s_{\bar{j}}^* \ge \frac{1}{mx_{\bar{j}}^k } (\c^{\Tr} \x^k -z^* )
\ge \frac{1}{m \gamma } (\c^{\Tr} \x^k -z^* ).
\label{myIneq3}\end{aligned}$$ Moreover, for any integer $t >0$, we have $$\c^{\Tr} \x^{k+t} -z^* = \s^{*^{\Tr}}\x^{k+t} 
\ge x_{\bar{j}}^{k+t} s_{\bar{j}}^*.$$ this gives $$\begin{aligned}
x_{\bar{j}}^{k+t} \le  \frac{\c^{\Tr} \x^{k+t} -z^* }{s_{\bar{j}}^*}.
\label{myIneq4}\end{aligned}$$ Substituting (\[myIneq3\]) and (\[myIneq2\]) into (\[myIneq4\]) gives $$\begin{aligned}
x_{\bar{j}}^{k+t} 
\le m \gamma \frac{\c^{\Tr} \x^{k+t} -z^* }
{\c^{\Tr} \x^k -z^* }
\le m \gamma \left( 1 - \frac{\delta}{m\gamma} \right)^t.
\label{myIneq5}\end{aligned}$$ Substituting (\[tIter\]) into (\[myIneq5\]) and using the identity $x^{\log_b y}= y^{\log_b x}$ and the inequality $\log(1-x) \le -x$ for all $x \le  1$, we have $$\begin{aligned}
x_{\bar{j}}^{k+t} & \le &  m \gamma \left( 1 - \frac{\delta}{m\gamma} \right)^{m \frac{\gamma}{\delta}
\log\left( m \frac{\gamma}{\delta} \right)}
\nonumber \\
& = & m \gamma \left[ \left( 1 - \frac{\delta}{m\gamma} 
\right)^{\log\left( m \frac{\gamma}{\delta} \right)}
\right]^{m \frac{\gamma}{\delta}}
\nonumber \\
& = & m \gamma \left[ 
\left( m \frac{\gamma}{\delta} \right)^{\log
\left( 1 - \frac{\delta}{m\gamma} \right)}
\right]^{m \frac{\gamma}{\delta}}
\nonumber \\
& \le & m \gamma \left[ \left( 
m \frac{\gamma}{\delta} \right)^{- \frac{\delta}{m\gamma}} 
\right]^{m \frac{\gamma}{\delta}} \le \delta.
\label{myIneq6}\end{aligned}$$ Therefore, after at most $\lceil t \rceil$ iterations, $x_{\bar{j}}^{k+t}< \delta$ holds. In view of Assumption 4, we conclude that $x_{\bar{j}}^{k+t}$ is not a basic variable of $B^{k+t}$ and (\[myIneq2\]) asserts that it will not be a basic variable thereafter. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

The scenario described in the theorem can occur at most one time for each optimal non-basic variable and since there are $n-m$ non-basic optimal variables, we have the following theorem.

For the double-pivot algorithm \[mainAlg\], it needs at most $(n-m) \Bigl\lceil
m \frac{\gamma}{\delta}
\log\left( m \frac{\gamma}{\delta} \right)
\Bigr\rceil$ iterations to find the optimal solution of (\[LP\]).

The way of selecting $x_{\bar{j}}^{k}$ below (\[myIneq2\]) implies that one should consider the entering variable that takes the longest step because this variable is likely an optimal non-basic variable. \[longestStep\]

Similar to the argument in [@km13a], we can apply the above theorem to some special linear programming problems, such as LP with a totally unimodular matrix and Markov Decision Problem with a fixed discount rate, and show that the double-pivot algorithm solves these special LP problems in a strongly polynomial time.

The tightness of the bounds in the two theorems can be seen from the following problem provided in [@km11]: $$\begin{aligned}
\begin{array}{cl}
\min & -\sum_{i=1}^m   x_i \\
\mbox{subject to} & 
x_1 + x_{m+1} = 1, \\
& 2 \sum_{i=1}^{k-1} x_i +x_k + x_{m+k} = 2^k-1
 \hspace{0.1in} k=2, \ldots, m, 
  \\
& x_i \ge 0 \hspace{0.1in} i=1, \ldots, 2m.
\end{array}
\label{3rdProblem}\end{aligned}$$ Assuming that the initial point is taken as $\x^0 =[0,\ldots,0,1,\ldots,1]$ (there are $m$ zeros and $n-m$ ones) and Dantzig’s rule is used, for this problem, Kitathra and Mizuno showed [@km11] that the bound of Theorem \[thm2\] is reduced to $\lceil (2m \log 2)2^m \rceil$, while the actual iteration number is $2^m-1$. The estimated bound is reasonably tight. We show that the bound of Theorem \[mainThe\] is much tighter than the one of Theorem \[thm2\]. For this problem, it is easy to see that the first $m$ variables of the optimal solution are $[x_1^*,\ldots,x_m^*]=[ 0, \ldots, 0,2^m-1]$ with optimal objective function $-(2^m-1)$ and the objective function at initial $\x^0$ is zero. Therefore, we have $\c^{\Tr}\x^0-z^*=2^m-1$. Since every component of any basic feasible solution is a positive integer (because every basic matrix is lower triangle and it is easy to see the claim), this shows that $\delta_D = 1$ because either $x_1=1$ or $x_{m+1}=1$. In the first iteration, noticing that $B^0=\{ m+1, m+2,\ldots, 2m \}$ and the entering variable $\bar{x}_{\jmath_2^k}=x_m=2^m-1$. In view of Theorem \[mainThe\], it needs only one iteration to find the optimal solution and $\gamma_{\ell}=2^m-1$. This claim is verified in the numerical test in the next section for several variants of Klee-Minty cube.

Numerical test
==============

Klee-Minty cube and its variants have been used to prove that several popular simplex algorithms need exponential number of iterations in the worst case to find an optimizer. In this section, three variants of Klee-Minty cube [@greenberg97; @ibrahima13; @km11] are used to test the proposed algorithm.

The first variant of Klee-Minty cube is given in [@greenberg97]: $$\begin{aligned}
\begin{array}{cl}
\min & -\sum_{i=1}^m 2^{m-i} x_i \\
\mbox{subject to} & 
\left[ 
\begin{array}{cccccc}
1 & 0 & 0 & \ldots & 0 & 0 \\
2^2 & 1 & 0 & \ldots & 0 & 0 \\
2^3 & 2^2  & 1 & \ldots & 0 & 0 \\
\vdots &  \vdots & \vdots &  \ddots & 0 & 0 \\
2^{m-1} &  2^{m-2} & 2^{m-3} & \ldots  & 1 & 0 \\
2^m &  2^{m-1} & 2^{m-2} & \ldots &  2^2  & 1 \\
\end{array}
\right]
\left[ \begin{array}{c}
x_1 \\ x_2 \\ \vdots \\  \vdots \\ x_{m-1} \\ x_m
\end{array} \right] 
\le 
\left[ \begin{array}{c}
5 \\ 25 \\ \vdots \\  \vdots \\ 5^{m-1} \\ 5^m
\end{array} \right] 
  \\
& x_i \ge 0 \hspace{0.1in} i=1, \ldots, m.
\end{array}
\label{1stProblem}\end{aligned}$$ The optimizer is $[ 0, \ldots, 0,5^m ]$ with optimal objective function $-5^m$.

The second variant of Klee-Minty cube is given in [@ibrahima13]: $$\begin{aligned}
\begin{array}{cl}
\min & -\sum_{i=1}^m 10^{m-i} x_i \\
\mbox{subject to} & 
2 \sum_{j=1}^{i-1} 10^{i-j} x_j +x_i \le 100^{i-1}
 \hspace{0.1in} i=1, \ldots, m,  \\
& x_i \ge 0 \hspace{0.1in} i=1, \ldots, m.
\end{array}
\label{2ndProblem}\end{aligned}$$ The optimizer is $[ 0, \ldots, 0,10^{2(m-1)}]$ with optimal objective function $-10^{2(m-1)}$.

The third variant of Klee-Minty cube is given in [@km11] (its standard form was discussed in the previous section): $$\begin{aligned}
\begin{array}{cl}
\min & -\sum_{i=1}^m   x_i \\
\mbox{subject to} & 
x_1 \le 1, \\
& 2 \sum_{i=1}^{k-1} x_i +x_k \le 2^k-1
 \hspace{0.1in} k=2, \ldots, m, 
  \\
& x_i \ge 0 \hspace{0.1in} i=1, \ldots, m.
\end{array}
\label{3rdProblem}\end{aligned}$$ The optimizer is $[ 0, \ldots, 0,2^m-1]$ with optimal objective funtion $-(2^m-1)$. The test results are summarized in Table \[table1\]. All initial points are selected as $[0, \ldots, 0]^{\Tr}$. For the first variant of Klee-Minty cube [@greenberg97], using the most two negative elements of $\bar{c}_{N^k}$ to choose the entering variables (described in Remark \[mostNeg\]) is better than the strategy of Dantzig’s rule which uses the most negative element of $\bar{c}_{N^k}$ to choose the entering variable. The pivot rule with the most two negative elements uses half of the iterations of Dantzig’s rule but the iteration numbers still increase exponentially fast. When the size $m \ge 18$, the program freezes because iteration numbers are very big and the computational time is very long.

Algorithm \[mainAlg\] is much more impressive. For all problems in three variants, only one iteration is needed to find the optimal solution, except for the problem with dimension $m=200$ in variant 2 [@ibrahima13] because Matlab R2016a on computer Dell Inspiron 3847 cannot store the big value (bigger than 10E+310) in vector $\b$. This shows that the estimated bound of Theorem \[mainThe\] is reachable.

We also compared the tests result with the one in [@ibrahima13] which uses randomized pivot method. For $m=100$, the randomized pivot method uses more than $1000$ iterations to find the solution for a variant of Klee-Minty cube on average of $200$ runs; for $m=200$, the randomized pivot method uses more than $5000$ iterations to find the solution on average of $200$ runs. Using Algorithm \[mainAlg\], it takes one iteration for these problems. The proposed double-pivot algorithm is much more efficient than the randomized algorithm for these Klee-Minty cube problems. This result justifies a moderate computational cost increase in each iteration.

[|c|c|c|c|c|c|]{} & & &\
& [Dantzig]{} & Remark \[mostNeg\] & Alg. 2.1 & Alg. 2.1 & Alg. 2.1\
2 & 3 & 2 & 1 & 1 & 1\
3 & 7 & 4 & 1 & 1 & 1\
4 & 15 & 8 & 1 & 1 & 1\
5 & 31 & 16 & 1 & 1 & 1\
6 & 63 & 32 & 1 & 1 & 1\
7 & 127 & 64 & 1 & 1 & 1\
8 & 255 & 128 & 1 & 1 & 1\
9 & 511 & 256 & 1 & 1 & 1\
10 & 1023 & 512 & 1 & 1 & 1\
11 & $2^{11}-1$ & 1024 & 1 & 1 & 1\
12 & $2^{12}-1$ & $2^{11}$ & 1 & 1 & 1\
13 & $2^{13}-1$ & $2^{12}$ & 1 & 1 & 1\
14 & $2^{14}-1$ & $2^{13}$ & 1 & 1 & 1\
15 & $2^{15}-1$ & $2^{14}$ & 1 & 1 & 1\
16 & $2^{16}-1$ & $2^{15}$ & 1 & 1 & 1\
17 & - & $2^{16}$ & 1 & 1 & 1\
18 & - & - & 1 & 1 & 1\
19 & - & - & 1 & 1 & 1\
20 & - & - & 1 & 1 & 1\
21 & - & - & 1 & 1 & 1\
22 & - & - & 1 & 1 & 1\
23 & - & - & 1 & 1 & 1\
24 & - & - & 1 & 1 & 1\
25 & - & - & 1 & 1 & 1\
26 & - & - & 1 & 1 & 1\
27 & - & - & 1 & 1 & 1\
28 & - & - & 1 & 1 & 1\
29 & - & - & 1 & 1 & 1\
30 & - & - & 1 & 1 & 1\
100 & - & - & 1 & 1 & 1\
200 & - & - & 1 & - & 1\

\[table1\]

Conclusion
==========

In this paper, a double-pivot simplex method is proposed. Two upper-bounds of the iteration numbers for the proposed algorithm are derived. The first bound is very tight and can be reached. The second bound, when it is applied to some special linear programming problems, such as LP with a totally unimodular matrix and Markov Decision Problem with a fixed discount rate, shows that the proposed algorithm will find the optimal solution in a strongly polynomial time. The numerical test for Klee-Minty cube problems shows very promising result. It is hoped that the double-pivot strategy may lead to some strongly polynomial algorithms for general linear programming problems.

The Matlab codes used for the tests of the Klee-Minty variants in [@greenberg97; @ibrahima13; @km11] are available up request to the author.

[99]{}

N. Bonifas, M.D. Summa, F. Eisenbrand, N. Hahnle, and M. Niemeier, (2014), On sub-determinants and the diameter of polyhedra. Discrete and Computational Geometry, 52, 102-115.

G.B. Dantzig, (1949), Programming in a linear structure, Econometrica 17, 73–74.

G.B. Dantzig, (1963), Linear programming and extensions, Princeton University Press, Princeton, 1963.

O. Friedmann, (2011), A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games., In: IPCO, pp. 192–206.

B. Gartner, M. Henk, and G.M. Ziegler (1998), Randomized simplex algorithms on Klee-Minty cubes Combinatorica, 18(3), 49-372.

D. Goldfarb and W.Y. Sit, (1979), Worst case behavior of the steepest edge simplex method, Discrete Applied Mathematics, 1, 277-285.

H. J. Greenberg, (1997), Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method, University of Colorado at Denver, http://www.cudenver.edu/ hgreenbe.

F. Ihrahima, (2013), Degeneracy and geometry in the simplex method, Stanford University report, available from the Internet, https://pdfs.semanticscholar.org/0b28/52b085df3288d0ddcc28c5e511082fd03fef.pdf.

R.G., Jeroslow, (1973), The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Mathematics, 4, 367-377.

G. Kalai and D. Kleitman, (1992), A quasi-polynomial bound for the diameter of graphs of polyhedra, Bulletin of the American Mathematical Society, 26, 315-316.

J.A. Kelner and D.A. Spielman, (2006), A randomized polynomial-time simplex algorithm for linear programming, Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, 51-60.

T. Kitahara and S. Mizuno, (2011), Klee-Minty’s LP and Upper Bounds for Dantzig’s Simplex Method, Operations Research Letters, 39(2), 88-91.

T. Kitahara and S. Mizuno, (2013), A bound for the number of different basic solutions generated by the simplex method, Mathematical Programming, 137, 579-586.

T. Kitahara and S. Mizuno, (2013) An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables, Asia-Pacific Journal of operational research, 30, 1340012, \[10 pages\].

V. Klee and G.J. Minty, (1972), How good is the simplex algorithm? In O. Shisha, editor, Inequalities, III, 159-175. Academic Press, New York, NY.

Paparrizos K., Samaras N., Zissopoulos D. (2008) Linear Programming: Klee-Minty Examples. In: Floudas C., Pardalos P. (eds) Encyclopedia of Optimization. Springer, Boston, MA

N. Ploskas and N. Samaras, (2014), Pivoting rules for the revised simplex algorithm, Yugoslav Journal of Operations Research, 24(3), 321-332.

F. Santos, (2012), A counterexample to the Hirsch conjecture. Annals of Mathematics, 176, 383-412.

F. Santos, (2012), The Hirsch conjecture has been disproved: An interview with Francisco Santos. EMS Newsletter December 2012.

S. Smale, (1999). Mathematical problems for the next century. In Arnold, V. I.; Atiyah, M.; Lax, P.; Mazur, B. Mathematics: frontiers and perspectives. American Mathematical Society, 271–294.

N. Sukegawa, (2017), Improving bounds on the diameter of a polyhedron in high dimensions, Discrete Mathematics, 340, 2134-2142.

T. Terlaky and S. Zhang, (1993), Pivot rules for linear programming: A survey on recent theoretical developments, Annals of Operations Research, Vol. 46 (1), 203–233.

M. J. Todd, (2014), An improved Kalai–Kleitman bound for the diameter of a polyhedron, SIAM Journal on Discrete Mathematics, 26(2), 1944-1947.

Y. Yang, (2018), On the diameter of polytopes, arXiv:1809.06780v1.

Y. Ye, (2011), The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate, Mathematics of Operations Research, 36(4), 593-603.

[^1]: US NRC, Office of Research, 11555 Rockville Pike, Rockville, 20850. Email: yaguang.yang@verizon.net.
