5.5 The dual simplex method

The primal simplex method keeps \(x_B \geq 0\) (primal feasibility) and works towards non-negative reduced costs (dual feasibility). The dual simplex method (Lemke, 1954) does the opposite: it keeps the reduced costs non-negative and works towards \(x_B \geq 0\). An iteration chooses a row \(r\) with \(x_{B(r)} < 0\) to leave, and among the columns with a negative entry in that row chooses the entering one by the dual ratio test \[ j = \operatorname *{arg\,min}\Bigl \{\frac {\bar c_j}{|T_{rj}|} : T_{rj} < 0\Bigr \} , \] which keeps every reduced cost non-negative after the pivot. If no entry of the row is negative, the row reads \(\sum _jT_{rj}x_j = x_{B(r)} < 0\) with \(T_{rj} \geq 0\), which no \(x \geq 0\) satisfies, so the primal is infeasible. The objective value moves monotonically towards the optimum from the other side, and the method is the simplex method applied to the dual, carried out on the primal tableau.

It is the natural method when a solved problem gains a constraint, as in the branch-and-bound and cutting-plane methods for integer programming: the old optimal basis stays dual feasible, the new constraint makes it primal infeasible, and a few dual pivots restore optimality. It is also the default of most modern solvers, because it handles bounds and degeneracy well.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.