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


Abstract in English

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 implementation of Dantzigs algorithm, for several test sets, including a set of cycling LP problems, Klee-Mintys 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 expected, and (b) more efficient than Dantzigs algorithm for large size randomly generated LP problems but less efficient for Netlib benchmark problems and small size randomly generated problems in terms of CPU time.

Download