4.1 The revised simplex method
Each iteration of the simplex method needs only four computations with the current basis matrix \(B\):
- (1)
- the basic solution \(x_B = B^{-1}b\);
- (2)
- the simplex multipliers \(y^{\mathsf T} = c_B^{\mathsf T}B^{-1}\), by solving \(B^{\mathsf T}y = c_B\);
- (3)
- the reduced costs \(\bar c_j = c_j - y^{\mathsf T}A_j\) of the non-basic columns (pricing), to choose the entering column \(j\);
- (4)
- the entering column \(u = B^{-1}A_j\), by solving \(Bu = A_j\), for the ratio test.
The rest of \(B^{-1}A\) is never formed. Solving with \(B\) is done from a factorisation, updated after each pivot instead of recomputed. The simplest update is the product form of the inverse.
Proposition 4.1.1 (Eta update). If column \(j\) enters at row \(r\), with \(u = B^{-1}A_j\) and \(u_r \neq 0\), the new basis matrix \(\bar B\) satisfies \(\bar B^{-1} = EB^{-1}\), where \(E\) is the identity except in column \(r\), which is \[ \eta = \Bigl (-\frac {u_1}{u_r}, \ldots , -\frac {u_{r - 1}}{u_r}, \frac 1{u_r}, -\frac {u_{r + 1}}{u_r}, \ldots , -\frac {u_m}{u_r}\Bigr )^{\mathsf T} . \]
Proof. \(B^{-1}\bar B\) is the identity with column \(r\) replaced by \(B^{-1}A_j = u\). The matrix \(E\) is the inverse of that: \(E\) times the identity-with-column-\(u\) has column \(r\) equal to \(Eu = u_r\eta + \sum _{i \neq r}u_ie_i = e_r\), and its other columns unchanged. So \(EB^{-1}\bar B = I\). □
After \(k\) pivots \(B^{-1} = E_k\cdots E_1B_0^{-1}\), and each \(E_i\) is stored as one column. Since the product grows and rounding errors accumulate, the basis is refactorised from scratch every few dozen pivots. Modern codes use a sparse \(LU\) factorisation of \(B\) with updates of Forrest–Tomlin type, and choose the entering column by more refined rules than Dantzig’s (steepest edge, which picks the edge that improves the objective most per unit of distance, and partial pricing, which prices only part of the columns at each iteration).
Example 4.1.2. For Example 3.2.1 as a minimisation of \(-Z = -10x_1 - 15x_2\), the revised method visits the same bases as the tableau (Software 4.4.1). At the final basis \(\{s_3, x_1, x_2\}\) the multipliers are \(y = (-\frac 53, -\frac {10}3, 0)\), the shadow prices of the tableau with the sign of the minimisation: an extra hour of the first resource is worth \(\frac 53\), of the second \(\frac {10}3\), and of the third, which has slack, nothing.
Work per iteration. For an \(m \times n\) problem, a tableau pivot costs about \(mn\) operations. The revised method costs two solves with \(B\) (about \(m^2\) each for dense factors, much less if sparse) and pricing, \(O(\text {nonzeros of } A)\). When \(n\) is much larger than \(m\), as in most applications, and \(A\) is sparse, the saving is large; and the revised method works with the original sparse \(A\) throughout, where the tableau fills in.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.