A generalized dual phase-2 simplex algorithm1

Abstract

Real-life linear programming (LP) problems include all types of variables and constraints. Current versions of the primal simplex method are well prepared to handle such problems efficiently. At the same time, the usefulness of the dual simplex method was thought to be limited to the standard problem though it could be the ideal algorithm in many other cases. For instance, most solution methods for Mixed Integer Programming (MIP) problems require the repeated solution of closely related continuous LP problems. It is typical that the optimal basis of a node problem is dual feasible for its child problems. In such a situation the dual simplex algorithm (DSA) is undoubtedly the best solution method. The LP relaxation of MIP problems contains many bounded variables and, realistically, other types of variables may also be present. This necessitates such an implementation of the DSA that can handle variables of arbitrary type. The paper presents an algorithm called BSD for the efficient handling of all types of variables. 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 creates a large flexibility in finding a pivot element, (v) it excels 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.