A double-pivot simplex algorithm and its upper bounds of the iteration numbers
- PDF / 575,546 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 18 Downloads / 178 Views
RESEARCH
A double-pivot simplex algorithm and its upper bounds of the iteration numbers Yaguang Yang* * Correspondence:
[email protected] US NRC, Office of Research, 11555 Rockville Pike, Rockville 20850, USA
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 with a fixed discount rate, indicates that the double-pivot simplex method solves these problems in a strongly polynomial time. Applying the other bound to a variant of Klee–Minty cube shows that this bound is actually attainable. Numerical test on three variants of Klee–Minty cubes is performed for the problems with sizes as big as 200 constraints and 400 variables. The test result shows that the proposed algorithm performs extremely good for all three variants. Dantzig’s simplex method cannot handle the Klee–Minty cube problems with 200 constraints because it needs about 2200 ≈ 1060 iterations. Numerical test is also performed for randomly generated problems for both the proposed and Dantzig’s simplex methods. This test shows that the proposed method is promising for large-size problems. Keywords: Double-pivot algorithm, Simplex method, Linear programming, Klee–Minty cube Mathematics Subject Classification: 90C05, 90C49
1 Introduction Since Dantzig invented the simplex method in 1940s [2], its complexity has been a topic that attracted many researchers. Since all pivot rules of the simplex method 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 iteration number that the best simplex algorithm can possibly achieve. Hirsch in 1957 [3] conjectured that the diameter of the polytope is m − n for the polytope P = {x ∈ Rn : Ax ≤ b} where A ∈ Zm×n and m > n. This conjecture was disapproved by Santos [18] after a 50-year effort of many experts. Now, some experts, for example Santos [19], believe that the diameter of the convex polytope can be bounded by a polynomial of (m − n)n. This conjectured upper bound for the diameter of the convex polytope is much smaller than the best-known quasi-polynomial upper bounds which are due to Kalai and Kleitman [10], Todd [23] and Sukegawa [21]. In a recent effort [27], this author showed that for a given polytope, the diameter is bounded
123
© This is a U.S. government work and its text is not subject to copyright protection in the United States; however, its text may be subject to foreign copyright protection 2020.
0123456789().,–: volV
34
Page 2 of 19
Y. Yang Res Math Sci (2020) 7:34
3 n by O det(A ∗ ) , where is the largest absolute value among all (n − 1) × (n − 1) subdeterminants of A and det(A∗ ) is the smallest absolute value
Data Loading...
