Name
Abstract | ||
|---|---|---|
We resolve the problem of degeneracy in a recently developed primal-dual simplex algorithm for general linear programming problems (Chen et al., 1994). We show that the algorithm cycles. It is also shown that if ties are broken by an arbitrary cycling-free pivot rule of the classical primal simplex algorithm, then the refined primal-dual algorithm does not cycle. Exponential worst-case behaviour is shown and relations with other algorithms are discussed. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0167-6377(96)00008-9 | Oper. Res. Lett. |
Keywords | Field | DocType |
exterior point simplex algorithm,refined primal-dual algorithm,primal-dual simplex algorithm,simplex method,pivoting rules,arbitrary cycling-free pivot rule,classical primal simplex algorithm,algorithm cycle,degeneracy,linear programming,general linear programming problem,exponential worst-case behaviour,linear program,simplex algorithm | Big M method,Mathematical optimization,Chen,Exponential function,Simplex algorithm,Revised simplex method,Degeneracy (mathematics),Linear programming,Criss-cross algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 1 | Operations Research Letters |
Citations | PageRank | References |
3 | 0.49 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantinos Dosios | 1 | 3 | 0.49 |
| Konstantinos Paparrizos | 2 | 178 | 17.95 |