3.3. Pivoting

Given the \(s\)th LP \(P^{(s)}\) in the sequence of LPs produced by the Simplex Algorithm, pivoting has the goal to achieve one of three things:

• Decide that the BFS \(\hat z^{(s)}\) of \(P^{(s)}\) is an optimal solution. In this case, \(t = s\) and the Simplex Algorithm terminates, reporting \(\hat z^{(s)}\) as an optimal solution of its input LP \(P\), which is correct because \(P\) and \(P^{(s)}\) are equivalent.

• Decide that \(P^{(s)}\) has a feasible solution with objective function value \(\infty\). In this case, \(P^{(s)}\) is unbounded. Again, since \(P\) and \(P^{(s)}\) are equivalent, this implies that \(P\) is also unbounded. The Simplex Algorithm terminates in this case and reports the fact that \(P\) is unbounded.

• If we cannot conclude that \(P^{(s)}\) is unbounded nor that its BFS is an optimal solution, then pivoting constructs an equivalent LP \(P^{(s+1)}\) and aims to do so in a way that ensures that the BFS \(\hat z^{(s+1)}\) of \(P^{(s+1)}\) has a greater objective function value than the BFS \(\hat z^{(s)}\) of \(P^{(s)}\). In the worst case, \(\hat z^{(s+1)}\) and \(\hat z^{(s)}\) have the same objective function value.

A pivoting step consists of two substeps: first we transform the BFS \(\hat z^{(s)}\) of \(P^{(s)}\) into a feasible solution \(\hat z^{(s+1)}\) of \(P^{(s)}\) with a greater or at least no lower objective function value than that of \(\hat z^{(s)}\). Then we transform \(P^{(s)}\) into an equivalent LP \(P^{(s+1)}\) that has \(\hat z^{(s+1)}\) as its BFS. We discuss these two parts of pivoting next.