Revised Simplex step-by-step

LP definition with bounds

Let’s start by defining a linear programming problem in standard form with bounds:

$$\begin{align*} \text{Min } & c^T x \\ \text{Subject to } & Ax = b \\ & l \leq x \leq u \end{align*}$$

where:

• $A \in \R^{m \times n}$ is the constraint matrix.
• $b \in \R^m$ is the right-hand side vector.
• $c \in \R^n$ is the coefficient vector of the objective function.
• $l, u \in (\R \cup \{-\infty, +\infty\})^n$ are the lower and upper bounds on the variables.

A feasible solution to this problem is a vector $x \in \R^n$ that satisfies all the constraints. A feasible solution is optimal if it minimizes the objective function while satisfying the constraints.

Basis

A basis $\mathcal{B}$ is a set of $m$ indices corresponding to a subset of columns of $A$. We define as $B \coloneqq A_{\mathcal{B}} \in \R^{m \times m}$, and we assume that $B$ is invertible. If $A$ is full rank, then there exists at least one such basis. Each column corresponds to a basic variable.
The remaining $n - m$ variables are called non-basic variables, and the corresponding indices belong to the set $\mathcal{N}$, where $N \coloneqq A_{\mathcal{N}} \in \R^{m \times (n - m)}$ is the matrix formed by the non-basic columns of $A$.

Example
Let $\mathcal{B} = \{1, 3\}$ and $\mathcal{N} = \{2, 4, 5\}$. Then, for the following problem we have:

$$A = \begin{bmatrix} 13 & 2 & 1 & 0 & 7 \\ 0 & 1 & 5 & 1 & 0 \\ \end{bmatrix}, \quad B = \begin{bmatrix} 13 & 1 \\ 0 & 5 \end{bmatrix}, \quad N = \begin{bmatrix} 2 & 0 & 7 \\ 1 & 1 & 0 \end{bmatrix}$$

Following the partition of variables into basic and non-basic, we can follow a similar approach for the vectors $c$, $b$ and $x$:

$$c = \begin{bmatrix} c_B \\ c_N \end{bmatrix}, \quad b = \begin{bmatrix} b_B \\ b_N \end{bmatrix}, \quad x = \begin{bmatrix} x_B \\ x_N \end{bmatrix}$$

Basic Feasible Solution

Given a basis $\mathcal{B}$, we can define a basic feasible solution (BFS) as a solution where the basic variables are determined by solving the system $Bx_B + Nx_N = b$. Usually the non-basic variables are set to their bounds or to $0$, if unbounded. Moreover, for the solution to be optimal, we are interested in the following assignments for the non-basic variables:

Variable Type	Value in BFS
Basic Variables	$x_B = B^{-1} (b - N x_N)$, $l_i \leq x_i \leq u_i$
Bounded Non-Basic Variables	Set to $x = l_i$ or $x_i = u_i$
Unbounded Non-Basic Variables	Set to $0$

Revised Simplex Method Overview

The Revised Simplex Method is an efficient algorithm for solving linear programming problems. It operates by iteratively improving a basic feasible solution until an optimal solution is found.

Step 1: Initialization

1. Choose an initial basis $\mathcal{B}$ such that the corresponding basic feasible solution is feasible.
2. Compute $\pi = (B^T)^{-1} c_B$, where $c_B$ are the coefficients of the basic variables in the objective function.
3. Compute the reduced costs for the non-basic variables: $r_N = c_N - N^T \pi$.
   • We first express the basic variables in terms of the non-basic ones: $$\begin{align*} Bx_B + Nx_N & = b \newline x_B & = B^{-1} (b - N x_N) \newline \end{align*}$$
   • Then, we consider the objective function: $$\begin{align*} c^T x & = c_B^T x_B + c_N^T x_N \newline & = c_B^T B^{-1} (b - N x_N) + c_N^T x_N \newline & = c_B^T B^{-1} b + \underbrace{(c_N^T - c_B^T B^{-1} N)}_{\text{Reduced Costs}} x_N \newline \end{align*}$$
   • We define the reduced costs vector as: $$r_N = c_N - N^T B^{-T} c_B$$ Altering the reduced costs vector $r$ will affect the objective function value, e.g., increasing a non-basic variable with a negative reduced cost will decrease the objective function value, moving us closer to the optimum.
4. If $r_i \ge 0$ for all non-basic variables already at their lower bound and $r_i \le 0$ for all non-basic variables already at their upper bound, then the current solution is optimal. Stop.
5. If there is a non-basic variable with a reduced cost that violates the optimality condition, select one such variable to enter the basis. This is called the entering variable.
6. Compute the direction of movement for the basic variables: $$d = B^{-1} A_{:,e}$$ where $A_{:,e}$ is the column of $A$ corresponding to the entering variable
   • Let $t$ be the new value we want to assign to the entering variable. To keep the system satisfied, we need to adjust the basic variables $\bar{x}_B$ as follows: $$B \bar{x}_B + A_{:,e} t + N x_N = b \newline$$ From which we get: $$\begin{align*} \bar{x}_B &= B^{-1} (b - N x_N) - B^{-1}A_{:,e} t \newline &= x_B - B^{-1} A_{:,e} t \newline &= x_B - d t \end{align*}$$
   • While we would like to increase (or decrease) $t$ indefinitely to improve the objective function, we must ensure that $\bar{x}_B$ and $t$ itself remain within their respective bounds. $$\begin{cases} l_B \leq \bar{x}_B = x_B - d t \leq u_B \newline l_e \leq t \leq u_e \newline \end{cases}$$ with the first condition leading to: $$\begin{cases} \frac{x_{B_i} - u_{B_i}}{d_i} \leq t \leq \frac{x_{B_i} - l_{B_i}}{d_i} & \text{if } d_i > 0 \newline \frac{x_{B_i} - l_{B_i}}{d_i} \leq t \leq \frac{x_{B_i} - u_{B_i}}{d_i} & \text{if } d_i < 0 \newline -\infty < t < +\infty & \text{if } d_i = 0 \end{cases}$$
   • In practice, we only care about the strictest bound that limit the increase (or decrease) of $t$.
7. Determine the maximum allowable step size $t^*$ for the entering variable without violating any bounds. If no such limit exists (i.e., the entering variable is unbounded in the direction of improvement), then the problem is unbounded. Stop.
8. Identify the leaving variable, with index $l$, which is the basic variable that reaches its bound first as we increase (or decrease) $t$ to $t^*$.
9. Update the basis by replacing the leaving variable with the entering variable.
   • Note that, based on how we made the change, the leaving variable will now be at its bound (either lower or upper).
10. Update the basic feasible solution accordingly: $$\begin{align*} x_e & = t^* \newline x_B & = x_B - d t^* \newline \end{align*}$$ and do the same for the sets $\mathcal{B} = (\mathcal{B} \setminus \{l\}) \cup \{e\}$ and $\mathcal{N} = (\mathcal{N} \setminus \{e\}) \cup \{l\}$.