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.