4.3 Numerical practice

In floating point the tests \(\bar c_j < 0\) and \(u_i > 0\) are made with tolerances, typically \(10^{-7}\) to \(10^{-9}\) relative to the data. A tiny pivot element \(u_r\) is dangerous, since the eta column contains \(1/u_r\); the Harris ratio test relaxes the bounds by the tolerance and then chooses, among the rows nearly tied for the minimum, the one with the largest \(|u_r|\). Problems are scaled so that the entries of \(A\) are of comparable size, and presolve removes redundant rows, fixed variables and singleton constraints before the simplex method starts. These details are invisible to the user of a modern solver, but they are why the method is reliable on problems with millions of variables.

For very large problems, interior-point methods are the main alternative. They follow a path through the interior of the feasible region, solving one large sparse linear system per iteration, and need a few dozen iterations almost regardless of size (Software 4.4.3); the simplex method needs more, cheaper iterations, but ends at a vertex and can be restarted quickly when the data change slightly, which matters for the sensitivity analysis and integer programming to come.

Questions on this section

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