Generalized dual phase-2 simplex algorithm

Generalized dual phase-2 simplex algorithm

0.00 Avg rating0 Votes
Article ID: iaor20043330
Country: Netherlands
Volume: 149
Issue: 1
Start Page Number: 1
End Page Number: 16
Publication Date: Aug 2003
Journal: European Journal of Operational Research
Authors:
Keywords: duality
Abstract:

Recently, the dual simplex method has attracted considerable interest. This is mostly due to is 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.

Reviews

Required fields are marked *. Your email address will not be published.