Revised Simplex step-by-step

LP definition with bounds

Let’s start by defining a linear programming problem in canonical form:

$$\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_{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 of $B$ 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_{N} \in \R^{m \times (n - m)}$ is the matrix formed by the non-basic columns of $A$.

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 solution (BS) as a solution where the basic variables are determined by solving the system $Bx_B + Nx_N = b$ while the non-basic variables are usually set to their bounds or to $0$, if unbounded. To be considered a basic feasible solution (BFS), the solution must also satisfy the bounds $l \leq x \leq u$. This corresponds to the following assignments:

$$\begin{bmatrix} B & N \\ 0 & I_{n - m} \end{bmatrix} \begin{bmatrix} x_B \\ x_N \end{bmatrix} = \begin{bmatrix} b \\ v_N \end{bmatrix}$$

where $v_N \in \R^{n - m}$ is vector containing an arbitrary combination of lower and upper bounds 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$

Error analysis

When operating with floating-point arithmetic, numerical errors can accumulate and affect the accuracy of the solution. We now analyse the sources of errors in the Revised Simplex Method and how they impact the solution.

Linear system

An exact solution to a linear system $Ax = b$ satisfies the equation precisely, while a computed solution $(A + E)\tilde{x} = b$ solves a perturbed system, where $E$ represents the error we are introducing due to numerical inaccuracies. We are interested in the $\Delta x = \tilde{x} - x$, which represents the difference between the exact solution $x$ and the computed solution.

$$\Delta x = \tilde{x} - x = A^{-1}(A \tilde{x} - b) = A^{-1} (A \tilde{x} - (A + E) \tilde{x}) = - A^{-1} E \tilde{x}$$

We are interested in the norm of the error $\|\Delta x\|$:

$$\|\Delta x\| = \|A^{-1} E \tilde{x}\| \leq \|A^{-1}\| \|E\| \|\tilde{x}\|$$

Using the definition of the condition number $\kappa(A) = \|A\| \|A^{-1}\|$, we can rewrite the above expression as:

$$\frac{\|\Delta x\|}{\|\tilde{x}\|} \leq \kappa(A) \frac{\|E\|}{\|A\|}$$

More precisely, we are interested in the residual $r = A \tilde{x} - b$, which quantifies how well the computed solution satisfies the original system, or the relative residual $\frac{\|r\|}{\|B\|\|\tilde{x}\|}$. We can also bound the residual norm as follows:

$$\|r\| = \|A \tilde{x} - b\| = \|E \tilde{x}\| \leq \|E\| \|\tilde{x}\|$$

therefore, the relative residual can be bounded as:

$$\frac{\|r\|}{\|A\| \|\tilde{x}\|} \leq \frac{\|E\|}{\|A\|}$$

Some notable results tell us that

• $\frac{\|E\|}{\|A\|} \leq dm\epsilon$, where $m$ is the number of rows, and $\epsilon$ is the machine precision.
• $|E_{i,j}| \leq 3.01 dm\epsilon$
• $\epsilon \approx 10^{-16}$ for IEEE double precision.

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 $\delta_e$ be the change in value we want to apply to the entering variable $x_e$, which is currently outside the basis. To keep the system satisfied, we need to adjust the basic variables $\bar{x}_B$ as follows: $$B \bar{x}_B + A_{:,e} \delta_e + N x_N = b \newline$$ From which we get: $$\begin{align*} \bar{x}_B &= B^{-1} (b - N x_N) - B^{-1}A_{:,e} \delta_e \newline &= x_B - B^{-1} A_{:,e} \delta_e \newline &= x_B - d \delta_e \end{align*}$$
   • While we would like to increase (or decrease) $x_e$ indefinitely to improve the objective function, we must ensure that $\bar{x}_B$ and $x_e$ itself remain within their respective bounds. $$\begin{cases} l_B \leq \bar{x}_B = x_B - d \delta_e \leq u_B \newline x_e - l_e \leq \delta_e \leq u_e - x_e \newline \end{cases}$$ with the first condition which expands to: $$\begin{cases} \frac{x_{B_i} - u_{B_i}}{d_i} \leq \delta_e \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 \delta_e \leq \frac{x_{B_i} - u_{B_i}}{d_i} & \text{if } d_i < 0 \newline -\infty < \delta_e < +\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 $\delta_e^*$ 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) $\delta_e$ to $\delta_e^*$.
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 & = x_e + \delta_e^* \newline x_B & = x_B - d \delta_e^* \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\}$.