# A double-pivot degenerate-tolerable simplex algorithm for linear programming

@inproceedings{Yang2021ADD, title={A double-pivot degenerate-tolerable simplex algorithm for linear programming}, author={Yaguang Yang and Fabio Vitor}, year={2021} }

A double pivot algorithm that combines features of two recently published papers by these authors is proposed. The proposed algorithm is implemented in MATLAB. The MATLAB code is tested, along with a MATLAB implemention of Dantzig’s algorithm, for several test sets, including a set of cycling LP problems, Klee-Minty’s problems, randomly generated linear programming (LP) problems, and Netlib benchmark problems. The test result shows that the proposed algorithm is (a) degenerate-tolerance as we… Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

The double pivot simplex method

- Computer Science, Mathematics
- Math. Methods Oper. Res.
- 2018

This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one, and demonstrates that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances. Expand

Pivoting Rules for the Revised Simplex Algorithm

- Mathematics
- 2014

Pricing is a significant step in the simplex algorithm where an improving non-basic variable is selected in order to enter the basis. This step is crucial and can dictate the total execution time. In… Expand

Analysis of mathematical programming problems prior to applying the simplex algorithm

- Mathematics, Computer Science
- Math. Program.
- 1975

An algorithm to detect structure is described and this algorithm identifies sets of variables and the corresponding constraint relationships so that the total number of GUB-type constraints is maximized. Expand

CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programming

- Computer Science
- Numerical Algorithms
- 2016

This paper will demonstrate, by testing Netlib problems and comparing the test results obtained by the arc-search infeasible interior-point algorithm and Mehrotra’s algorithm, that the proposed arc- search infeasable interior- point algorithm is a more reliable and efficient algorithm than MehroTra's algorithm. Expand

A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games

- Mathematics, Computer Science
- IPCO
- 2011

The first subexponential lower bound of the form 2Ω(√n) lower bound is obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. Expand

Randomized simplex algorithms on Klee-Minty cubes

- Mathematics, Computer Science
- Proceedings 35th Annual Symposium on Foundations of Computer Science
- 1994

The analysis of two most natural randomized pivot rules on the Klee-Minty cubes leads to (nearly) quadratic lower bounds for the complexity of linear programming with random pivots, and disprove two bounds conjectured in the literature. Expand

Klee-Minty's LP and upper bounds for Dantzig's simplex method

- Mathematics, Computer Science
- Oper. Res. Lett.
- 2011

It is shown that the ratio for a simple variant of Klee-Minty's LP is equal to the number of iterations by Dantzig's simplex method for solving it. Expand

Presolving in linear programming

- Mathematics, Computer Science
- Math. Program.
- 1995

This paper presents a comprehensive survey of presolve methods and discusses the restoration procedure in detail, i.e., the procedure that undoes the presolve. Expand

MATH 310 : Degeneracy and Geometry in the Simplex Method

- 2013

This project is exploring a bit deeper the study of the simplex method introduced in 1947 by George Dantzig [3] to solve Linear Programming problems. The simplex algorithm has been listed as one of… Expand

Pivot rules for linear programming: A survey on recent theoretical developments

- Mathematics, Computer Science
- Ann. Oper. Res.
- 1993

The various pivot rules of the simplex method and its variants that have been developed in the last two decades are discussed, starting from the appearance of the minimal index rule of Bland. Expand