.png){kind=icon}
Return
A primal deficient-basis simplex algorithm for linear programming
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2007.07.030.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The standard basis, which plays a fundamental role in simplex methodology, was recently extended to include a deficient case (with fewer columns than rows) by taking advantage of primal degeneracy. Computational results have been favorable with dense implementations. In this paper, we propose a primal simplex algorithm using sparse LU factors of deficient bases. Amenable to real-world linear programming problems, which are often degenerate or even highly degenerate, the algorithm would solve them with potentially improved stability compared to the simplex algorithm. The proposed algorithm has been implemented and tested on a set of 50 Netlib test problems as well as a set of 15 much larger real-world problems, including 8 Kennington and 5 BPMPD problems. It significantly outperformed MINOS 5.3 in terms of both iteration counts and run time. In particular,. these results reveal that there is no inevitable correlation between an algorithm's inefficiency and degeneracy (contradicting common belief). (C) 2007 Elsevier Inc. All rights reserved.
Keywords:
large-scale linear programming
simplex algorithm
primal degeneracy
deficient-basis
LU factorization
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSave
ShareSave
ShareSaveShareSaveShareSave
View more