3. The Simplex Algorithm

In this chapter, we discuss the Simplex Algorithm, a classical and fairly simple algorithm for solving linear programs, that is, for finding optimal solutions of linear programs. As discussed in Section 2.4, the Simplex Algorithm does not run in polynomial time in the worst case, but it is remarkably fast in practice.

The Simplex Algorithm expects its input in standard form. By Lemmas 2.11 and 2.12, every LP can be transformed into an equivalent LP in standard form. Thus, this is not a restriction. Throughout this chapter, all LPs will be in standard form, so we simply refer to them as linear programs without explicitly stating the assumption that they are in standard form.

The Simplex Algorithm can be summarized as follows: Every LP in standard form has a unique special solution called its basic solution. If this solution is feasible, it is called a basic feasible solution (BFS¹). The first step of the Simplex Algorithm is to decide whether the given LP \(P\) is feasible, whether it has a feasible solution at all. If it doesn't, the algorithm terminates and reports that \(P\) is infeasible. If \(P\) has a feasible solution, then the Simplex Algorithm transforms it into an equivalent LP \(P^{(0)}\) whose basic solution is feasible. Recall the concept of equivalence of two LPs: They have the same set of feasible solutions and assign the same objective function value to any such solution. Thus, the BFS of \(P^{(0)}\) is also a feasible solution of \(P\). After constructing \(P^{(0)}\), the Simplex Algorithm continues to transform this LP, producing a sequence of LPs \(P^{(0)}, \ldots, P^{(t)}\) that are all equivalent to \(P\) and all have basic feasible solutions. The transformation of each LP \(P^{(s)}\) into the next LP \(P^{(s+1)}\), called pivoting, also ensures that the BFS of \(P^{(s+1)}\) has an objective function value that is no less, ideally greater, than the objective function value of the BFS of \(P^{(s)}\). Thus, the algorithm makes steady progress towards better and better solutions. Once the Simplex Algorithm can verify that the BFS of the current LP \(P^{(t)}\) is optimal, something that is particularly easy to check for a BFS, it terminates and reports this solution. Since \(P^{(t)}\) is equivalent to \(P\), this solution must also be an optimal solution of \(P\).

This chapter is organized as follows:

• In Section 3.1, we introduce the concepts of the basic solution and of the basic feasible solution (BFS) of an LP.

• Section 3.2 gives an overview of the Simplex Algorithm.

• Section 3.3 discusses pivoting, the basic operation used by the Simplex Algorithm to move from BFS to BFS in search of an optimal solution.

• This discussion assumes that the basic solution of the initial LP is feasible. In general, this may not be the case. Thus, we need to discuss how to test whether the initial LP has any feasible solution and, if so, how to transform it into an equivalent LP whose basic solution is feasible. Section 3.4 discusses how to do this. Remarkably, we use the Simplex Algorithm itself, applying it to an auxiliary LP, to perform this step—how's that for bootstrapping!

• The previous four sections amount to a complete description of the Simplex Algorithm. Section 3.5 rounds out this discussion using an extended example and, in the process, introduces a tabular representation of an LP, called a tableau. Pivoting is easy to implement on a tableau using elementary row operations. Thus, tableaux are essential for the efficient implementation of the Simplex Algorithm and may also aid your intuition about how the Simplex Algorithm works. I encourage you to peek ahead at this section while reading the earlier sections of this chapter to connect the formal discussion of the Simplex Algorithm to the mechanics of performing the different steps on a concrete example.

• The final section, Section 3.6, considers cycling, a problem that can cause the Simplex Algorithm to run forever. The pivoting step gives us a lot of freedom in how we transform a given LP \(P^{(s)}\) into the next LP \(P^{(s+1)}\). If we are not careful, then some sequence of pivoting steps may transform a given LP back into itself. That's cycling: The algorithm cycles through the same set of LPs forever. We discuss Bland's rule, one of many rules that specify the details of the pivoting step in a way that prevents cycling. As part of the discussion of cycling and of Bland's rule as a means to avoid cycling, we provide an (exponential) upper bound on the running time of the Simplex Algorithm. We defer the correctness proof of the algorithm until we discuss LP duality in Chapter 4 because we need LP duality to complete the proof.