Paper Info
Title
A generalized dual phase-2 simplex algorithm
Abstract
Recently, the dual simplex method has attracted considerable interest. This is mostly due to its important role in solving mixed integer linear programming problems where dual feasible bases are readily available. Even more than that, it is a realistic alternative to the primal simplex method in many cases. Real world linear programming problems include all types of variables and constraints. This necessitates a version of the dual simplex algorithm that can handle all types of variables efficiently. The paper presents increasingly more capable dual algorithms that evolve into one which is based on the piecewise linear nature of the dual objective function. The distinguishing features of this method are: (i) in one iteration it can make progress equivalent to many traditional dual iterations, (ii) using proper data structures it can be implemented very efficiently so that an iteration requires hardly more work than the traditional pivot method, (iii) its effectiveness just increases if more upper bounded variables are present, (iv) it has inherently better numerical stability because it can create a large flexibility in finding a pivot element, (v) it can excel itself in coping with degeneracy as it can bypass dual degenerate vertices more easily than the traditional pivot procedures. The power of the method is demonstrated through examples. The performance on some real world problems is also presented.
Year
DOI
Venue
2003
10.1016/S0377-2217(02)00448-4
European Journal of Operational Research
Keywords
Field
DocType
Linear programming,Simplex method,Dual algorithm,Large scale optimization
Linear-fractional programming,Big M method,Mathematical optimization,Simplex algorithm,Revised simplex method,Algorithm,Integer programming,Pivot element,Linear programming,Criss-cross algorithm,Mathematics
Journal
Volume
Issue
ISSN
149
1
0377-2217
Citations 
PageRank 
References 
11
0.70
1
Authors
1
Name
Order
Citations
PageRank
István Maros1315.84