Lecture Notes on the Simplex Method

Author

Your Name

Published

January 30, 2025

Introduction

This lecture focuses on the Simplex method, a fundamental algorithm for solving linear programming problems. We will examine the method in detail, striving for clarity and simplicity despite its technical nature. Understanding the Simplex method is crucial for optimization across various fields. We will revisit the standard form of linear programs, systematically develop the steps of the Simplex algorithm, and address key concepts such as bases, basic variables, reduced costs, and optimality conditions. We will also discuss potential challenges like degeneracy and cycling, along with methods to handle them. Techniques for finding an initial feasible basis will be explored. Finally, we will briefly touch upon the computational complexity of the Simplex method and alternative polynomial-time algorithms.

Linear Programming in Standard Form

Definition of Standard Form

We begin by recalling the standard form of a Linear Programming (LP) problem. A generic LP in standard form is expressed as: $$ \[\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}\]

$$ where:

$x$ is the vector of variables to be determined.
$c$ is the cost vector.
$A$ is an $m \times (m+n)$ matrix of full rank $m$. This implies that all rows of $A$ are linearly independent, and if $A$ has $m$ rows, it must have at least $m$ columns (here denoted as $m+n$).
$b$ is the right-hand side vector.
$x \geq 0$ indicates that all variables must be non-negative.

Example of a Standard Form LP

Consider the following example of a linear programming problem in standard form: $$ \[\begin{aligned} \text{Maximize } & 2x_1 - 4x_2 + x_3 + 2x_4 - x_5 \\ \text{subject to } & 2x_1 + 3x_2 - 2x_3 + 5x_4 - x_5 = 3 \\ & x_1 + x_3 + x_4 - x_5 = 4 \\ & -x_1 + 2x_2 + x_3 + x_4 + 3x_5 = 1 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}\]

$$ This problem has three constraints (equations) and five variables.

Matrix Representation

In matrix form, the example can be represented as:

Cost vector $c^T = \begin{pmatrix} 2 & -4 & 1 & 2 & -1 \end{pmatrix}$
Constraint matrix $A = \begin{pmatrix} 2 & 3 & -2 & 5 & -1 \\ 1 & 0 & 1 & 1 & -1 \\ -1 & 2 & 1 & 1 & 3 \end{pmatrix}$
Right-hand side vector $b = \begin{pmatrix} 3 \\ 4 \\ 1 \end{pmatrix}$

The problem is to maximize $c^T x$ subject to $Ax = b$ and $x \geq 0$.

Bases and Basic Variables

Definition of a Basis

A basis is a set of column indices $B$ such that the corresponding columns of matrix $A$, denoted as $A_B$, are linearly independent and there are $m$ such indices, where $m$ is the number of rows in $A$. The columns $A_B$ form a basis for $\mathbb{R}^m$.

Let $B$ be the set of indices of the basis columns, and let $N$ be the set of indices of the remaining columns (non-basis columns).

Basic and Non-Basic Variables

Basic Variables: Variables corresponding to the indices in the basis $B$ are called basic variables, denoted as $x_B$.
Non-Basic Variables: Variables corresponding to the indices in the non-basis set $N$ are called non-basic variables, denoted as $x_N$.

Consider the basis $B = \{1, 3, 4\}$ for our example. The columns of $A$ corresponding to these indices are: These columns are linearly independent (can be verified using Gaussian elimination). Thus, $B = \{1, 3, 4\}$ is a valid basis. The non-basis indices are $N = \{2, 5\}$.

Partitioning the Problem

Given a basis $B$ and non-basis $N$, we can partition the problem components:

Submatrices $A_B$ and $A_N$

$A_B$: Submatrix of $A$ consisting of columns with indices in $B$.
$A_N$: Submatrix of $A$ consisting of columns with indices in $N$.

Cost Vectors $c_B$ and $c_N$

$c_B$: Subvector of $c$ consisting of costs with indices in $B$.
$c_N$: Subvector of $c$ consisting of costs with indices in $N$.

Variable Vectors $x_B$ and $x_N$

$x_B$: Vector of basic variables.
$x_N$: Vector of non-basic variables.

For our example with basis $B = \{1, 3, 4\}$ and $N = \{2, 5\}$:

$x_B = \begin{pmatrix} x_1 \\ x_3 \\ x_4 \end{pmatrix}$, $x_N = \begin{pmatrix} x_2 \\ x_5 \end{pmatrix}$
$c_B^T = \begin{pmatrix} 2 & 1 & 2 \end{pmatrix}$, $c_N^T = \begin{pmatrix} -4 & -1 \end{pmatrix}$
$A_B = \begin{pmatrix} 2 & -2 & 5 \\ 1 & 1 & 1 \\ -1 & 1 & 1 \end{pmatrix}$, $A_N = \begin{pmatrix} 3 & -1 \\ 0 & -1 \\ 2 & 3 \end{pmatrix}$

Rewriting the System

The system $Ax = b$ can be rewritten as $A_B x_B + A_N x_N = b$. To express basic variables in terms of non-basic variables, we multiply the system by $A_B^{-1}$ (since $A_B$ is a basis, it is invertible) from the left: \[I x_B + A_B^{-1} A_N x_N = A_B^{-1} b\] Let $\bar{A}_N = A_B^{-1} A_N$ and $\bar{b} = A_B^{-1} b$. Then the system becomes: and the constraints are: $$ \[\begin{aligned} x_B + \bar{A}_N x_N &= \bar{b} \\ x_B &\geq 0 \\ x_N &\geq 0 \end{aligned}\]

Example of Rewriting the System

For our example with basis $B = \{1, 3, 4\}$, we first calculate $A_B^{-1}$: Then we compute $\bar{A}_N = A_B^{-1} A_N$ and $\bar{b} = A_B^{-1} b$: \[\bar{A}_N = \begin{pmatrix} 0 & 1 & -1 \\ -1/2 & 7/2 & -3/2 \\ 1 & -2 & 2 \end{pmatrix} \begin{pmatrix} 3 & -1 \\ 0 & -1 \\ 2 & 3 \end{pmatrix} = \begin{pmatrix} -2 & -4 \\ -9/2 & -5 \\ 7 & 7 \end{pmatrix}\] The transcription example shows a different $\bar{A}_N$ and $\bar{b}$. Let’s use the provided $\bar{A}_N$ and $\bar{b}$ from the transcription for consistency.

According to the transcription, we have: \[\bar{A}_N = \begin{pmatrix} -1 & -2 \\ 0 & 2/7 \\ 1 & 5/7 \end{pmatrix}, \quad \bar{b} = \begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix}\] Thus, the rewritten system is: $$ \[\begin{aligned} x_1 - x_2 - 2x_5 &= 3/2 \\ x_3 + 2/7 x_5 &= 25/14 \\ x_2 + x_4 + 5/7 x_5 &= 5/7 \end{aligned}\] \[ Rewriting to express basic variables in terms of non-basic variables: \] \[\begin{aligned} x_1 &= 3/2 + x_2 + 2x_5 \\ x_3 &= 25/14 - 2/7 x_5 \\ x_4 &= 5/7 - x_2 - 5/7 x_5 \end{aligned}\]

Independent and Dependent Variables

From the rewritten system, it’s clear that $x_2$ and $x_5$ (non-basic variables) are independent, while $x_1, x_3, x_4$ (basic variables) are dependent on $x_2$ and $x_5$. We need to choose $x_2 \geq 0$ and $x_5 \geq 0$ such that $x_1 \geq 0, x_3 \geq 0, x_4 \geq 0$.

Reduced Costs

The objective function is $c^T x = c_B^T x_B + c_N^T x_N$. Substituting $x_B = \bar{b} - \bar{A}_N x_N$: The term $c_B^T \bar{b}$ is a constant. The coefficients of $x_N$ in the objective function are called reduced costs, denoted as $\bar{c}_N^T = c_N^T - c_B^T \bar{A}_N$.

Rewriting the Objective Function

The objective function becomes: \[\text{Maximize } z = c_B^T \bar{b} + \bar{c}_N^T x_N\] where $\bar{c}_N^T = c_N^T - c_B^T A_B^{-1} A_N$.

For our example, using values from transcription: $\bar{c}_N^T = \begin{pmatrix} -4 & 16/7 \end{pmatrix}$. Constant term: $c_B^T \bar{b} = \begin{pmatrix} 2 & 1 & 2 \end{pmatrix} \begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix} = 3 + \frac{25}{14} + \frac{10}{7} = \frac{87}{14}$. Objective function: $z = \frac{87}{14} + \begin{pmatrix} -4 & 16/7 \end{pmatrix} \begin{pmatrix} x_2 \\ x_5 \end{pmatrix} = \frac{87}{14} - 4x_2 + \frac{16}{7} x_5$.

Canonical Form

The problem is now rewritten in canonical form with respect to the basis $B$: $$ \[\begin{aligned} \text{Maximize } & \frac{87}{14} - 4x_2 + \frac{16}{7} x_5 \\ \text{subject to } & x_1 = 3/2 + x_2 + 2x_5 \\ & x_3 = 25/14 - 2/7 x_5 \\ & x_4 = 5/7 - x_2 - 5/7 x_5 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}\] \[ And equivalently, focusing on upper bounds for $x_N$ to ensure $x_B \geq 0$: \] \[\begin{aligned} \text{Maximize } & \frac{87}{14} - 4x_2 + \frac{16}{7} x_5 \\ \text{subject to } & x_2 + 2x_5 \geq -3/2 \\ & 2/7 x_5 \leq 25/14 \implies x_5 \leq 25/4 \\ & x_2 + 5/7 x_5 \leq 5/7 \implies x_2 \leq 5/7 - 5/7 x_5 \\ & x_2, x_5 \geq 0 \end{aligned}\] \[ More accurately, the constraints in terms of $\bar{A}_N$ and $\bar{b}$ are $\bar{b} - \bar{A}_N x_N \geq 0$ and $x_N \geq 0$. So, $\bar{A}_N x_N \leq \bar{b}$ and $x_N \geq 0$. \] \[\begin{pmatrix} -1 & -2 \\ 0 & 2/7 \\ 1 & 5/7 \end{pmatrix} \begin{pmatrix} x_2 \\ x_5 \end{pmatrix}\] \[\begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix}\] \[ \] \[\begin{aligned} -x_2 - 2x_5 &\leq 3/2 \\ 2/7 x_5 &\leq 25/14 \\ x_2 + 5/7 x_5 &\leq 5/7 \end{aligned}\]

$$ and $x_2, x_5 \geq 0$.

Key Idea of the Simplex Method

The key idea is to rewrite the original problem in terms of non-basic variables for a chosen basis. By changing the basis systematically, the Simplex method searches for an optimal basis where the solution becomes straightforward to find. In this canonical form, we have a problem in a lower dimension (in terms of non-basic variables), which is derived from the original higher-dimensional problem.

The Simplex Method

General Problem Formulation

The general problem we are addressing is to maximize $c^T x$ subject to $Ax = b, x \geq 0$.

The PDB Problem

For each basis $B$, we can formulate a problem in terms of non-basic variables, denoted as PDB (Problem Dependent on Basis). PDB is to maximize $\bar{c}_N^T x_N$ subject to $\bar{A}_N x_N \leq \bar{b}$ and $x_N \geq 0$. The original objective value is $c_B^T \bar{b} + \bar{c}_N^T x_N$.

Finding the Optimal Basis

The Simplex method aims to find a basis $B^*$ such that the PDB problem related to $B^*$ is easily solvable, ideally when the optimal solution for PDB is $x_N = 0$.

When is the Origin Optimal?

Consider the PDB problem: Maximize $\bar{c}_N^T x_N$ subject to $\bar{A}_N x_N \leq \bar{b}, x_N \geq 0$. The solution $x_N = 0$ is optimal if increasing any component of $x_N$ does not improve the objective function. This happens when all reduced costs are non-positive, i.e., $\bar{c}_N \leq 0$.

Conditions for Optimal Basis

A basis $B$ is optimal if it satisfies two conditions:

Non-positive Reduced Costs

$\bar{c}_N = c_N - c_B^T \bar{A}_N \leq 0$.

Non-negative $\bar{b}$ vector

$\bar{b} = A_B^{-1} b \geq 0$. This ensures that setting $x_N = 0$ leads to a feasible basic solution $x_B = \bar{b} \geq 0$.

Basic Feasible Solutions (BFS)

A basic feasible solution is obtained by choosing a basis $B$, setting non-basic variables $x_N = 0$, and solving $A_B x_B = b$ for basic variables $x_B$. If $x_B = A_B^{-1} b = \bar{b} \geq 0$, then $(x_B, x_N)$ is a BFS.

Degenerate and Non-Degenerate Solutions

Non-Degenerate BFS: A BFS is non-degenerate if all basic variables are strictly positive, i.e., $x_B > 0$.
Degenerate BFS: A BFS is degenerate if at least one basic variable is zero, i.e., at least one component of $x_B$ is 0.

Existence of Optimal Basic Solution

If an optimal solution exists, then there exists an optimal basic feasible solution.

This is a key justification for the Simplex method, which searches among BFSs.

The Goal of the Simplex Method

The goal of the Simplex method is to find an optimal basis $B^*$ such that the corresponding BFS is an optimal solution to the original LP problem. This is achieved by iteratively moving from one basis to another, improving the objective function at each step (or at least not decreasing it).

Finite Number of Bases

The number of possible bases is finite, bounded by $\binom{m+n}{m}$, where $m+n$ is the number of columns in $A$ and $m$ is the number of rows. This finiteness is crucial for the Simplex method to terminate in a finite number of steps (in the absence of cycling).

Iterative Search for Optimal Basis

The Simplex method is an iterative algorithm that starts with an initial feasible basis and moves to adjacent bases in search of an optimal basis.

Moving Between Bases

The Simplex method moves from one basis to an adjacent basis.

Adjacent Bases

Two bases are adjacent if they share $m-1$ columns. Moving to an adjacent basis involves removing one column from the current basis and adding one column from the non-basis set. This operation is called pivoting.

Degeneracy and the Simplex Method

Bases with the same BFS

In the presence of degeneracy, different bases can lead to the same BFS. This is because in a degenerate BFS, some basic variables are zero.

Pivoting

Pivoting is the operation of changing the basis by exchanging one basic variable with a non-basic variable. It is the core step in moving from one BFS to another in the Simplex method.

Choosing the Entering Variable

The entering variable is a non-basic variable that is chosen to become basic in the next iteration.

Greedy Approach

A common strategy is to choose the entering variable with the most positive reduced cost. This is a greedy approach aimed at maximizing the increase in the objective function in each iteration.

Determining the Level of the Entering Variable

Once an entering variable $x_j$ is chosen, we need to determine how much its value can be increased. This is limited by the constraints that basic variables must remain non-negative ($x_B = \bar{b} - \bar{A}_N x_N \geq 0$). We calculate the maximum allowable increase by considering the ratios $\frac{\bar{b}_i}{\bar{a}_{ij}}$ for all $\bar{a}_{ij} > 0$.

Unbounded Problems

If, for an entering variable $x_j$, all coefficients $\bar{a}_{ij}$ in the column $\bar{A}_N$ corresponding to $x_j$ are non-positive ($\bar{a}_{ij} \leq 0$), it means that $x_j$ can be increased indefinitely without violating feasibility. In this case, the problem is unbounded, and there is no optimal solution.

Choosing the Exiting Variable

The exiting variable is a basic variable that becomes non-basic in the next iteration. It is chosen based on the minimum ratio test. The exiting variable corresponds to the row $k$ that achieves the minimum ratio: \[\min_{i | \bar{a}_{ij} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{ij}} \right\} = \frac{\bar{b}_k}{\bar{a}_{kj}}\] The basic variable corresponding to row $k$ becomes the exiting variable.

Pseudocode of the Simplex Method

Matrix $A$, vectors $b$, $c$, initial feasible basis $B$ Choose an entering variable $x_j$ with $\bar{c}_j > 0$ Check for unboundedness: If $\bar{a}_{ij} \leq 0$ for all $i$, then problem is unbounded, terminate. Determine ratios for all $i$ such that $\bar{a}_{ij} > 0$: $r_i = \frac{\bar{b}_i}{\bar{a}_{ij}}$ Find the minimum ratio: $r_k = \min_{i | \bar{a}_{ij} > 0} \{r_i\}$ Choose the exiting variable $x_{B_k}$ corresponding to row $k$ Update basis: $B_{new} = (B \setminus \{B_k\}) \cup \{j\}$, $N_{new} = (N \setminus \{j\}) \cup \{B_k\}$ Update $\bar{A}_N$, $\bar{b}$, $\bar{c}_N$ for the new basis Return current basic feasible solution $x$

Summary of the Simplex Process

The Simplex method iteratively improves the objective function by moving from one BFS to another. It selects an entering variable with a positive reduced cost and an exiting variable based on the minimum ratio test. This process continues until no more improvement is possible, indicated by all reduced costs being non-positive.

Cycling and Degeneracy

Potential for Infinite Loops

In the presence of degeneracy, the Simplex method might cycle, meaning it could revisit a basis and enter an infinite loop without reaching the optimal solution. This occurs when a sequence of pivots does not improve the objective function.

Anti-Cycling Rules

To prevent cycling, anti-cycling rules are used.

Randomized Pivoting

Randomly choosing among eligible entering or exiting variables can probabilistically avoid cycling.

Blend’s Rule

Blend’s rule is a deterministic anti-cycling rule that chooses the entering variable with the smallest index among those with positive reduced costs, and similarly, chooses the exiting variable with the smallest index among those achieving the minimum ratio.

Finding an Initial Feasible Basis

A crucial step for starting the Simplex method is finding an initial feasible basis. This is not always straightforward.

Two-Phase Simplex Method

The Two-Phase Simplex Method is used to find an initial feasible basis and then solve the original LP problem.

Phase 1: Auxiliary LP

In Phase 1, an auxiliary LP problem is formulated. Artificial variables are added to the original constraints to create an initial feasible basis easily. The objective in Phase 1 is to minimize the sum of these artificial variables.

Phase 2: Original LP

If Phase 1 successfully reduces the sum of artificial variables to zero, a feasible basis for the original problem is obtained. Phase 2 then uses this basis to solve the original LP problem using the standard Simplex method.

Auxiliary LP

For a standard form LP $Ax = b, x \geq 0, b \geq 0$, the auxiliary LP is constructed as follows: $$ \[\begin{aligned} \text{Minimize } & \sum_{i=1}^m y_i \\ \text{subject to } & Ax + y = b \\ & x \geq 0, y \geq 0 \end{aligned}\]

$$ where $y = (y_1, \dots, y_m)^T$ are artificial variables. An initial feasible basis for this auxiliary problem is formed by the columns corresponding to $y$.

Optimality of the Auxiliary LP

The optimal value of the auxiliary LP indicates the feasibility of the original LP. If the minimum value is 0, then the original LP is feasible. If the minimum value is greater than 0, the original LP is infeasible.

Computational Complexity

Exponential Number of Bases

In the worst case, the Simplex method can visit an exponential number of bases, making its worst-case complexity exponential. This is due to the potential for the algorithm to traverse many vertices of the feasible region.

Polynomial Algorithms

Despite the exponential worst-case complexity, polynomial-time algorithms exist for linear programming.

Ellipsoid Method

The Ellipsoid method, developed by Leonid Khachiyan in 1979, was the first algorithm proven to solve linear programming problems in polynomial time. However, despite its theoretical importance, the Ellipsoid method is not efficient in practice due to its slow convergence and numerical instability.

Interior Point Method

The Interior Point Method, notably Karmarkar’s algorithm from 1984, provides a more practical polynomial-time algorithm for linear programming. Unlike the Simplex method, which moves along the edges of the feasible region, interior point methods move through the interior of the feasible region. These methods have shown to be very efficient in practice, especially for large-scale linear programming problems.

Conclusion

In this lecture, we have explored the Simplex method in detail, covering its algebraic foundations, iterative process, and key components such as bases, basic variables, reduced costs, and pivoting. We have seen how the Simplex method systematically searches for an optimal solution by moving from one basic feasible solution to another, improving the objective function at each step.

Important Remarks and Key Takeaways:

The Simplex method is a powerful algorithm for solving linear programming problems, widely used in practice due to its efficiency on average-case problems.
Understanding the concepts of bases, basic and non-basic variables, and reduced costs is crucial for grasping the mechanics of the Simplex method.
Degeneracy and cycling are potential issues in the Simplex method, but anti-cycling rules like Blend’s rule and randomized pivoting can effectively prevent infinite loops.
The Two-Phase Simplex method provides a systematic approach to finding an initial feasible basis, making the Simplex method applicable to any linear programming problem.
While the Simplex method has exponential worst-case complexity, polynomial-time algorithms such as the Ellipsoid method and Interior Point methods exist, offering theoretical and sometimes practical advantages, especially for large-scale problems.

Follow-up Questions and Topics for the Next Lecture:

How do different pivoting rules affect the performance of the Simplex method in practice?
Can we visualize the Simplex method geometrically in lower dimensions?
What are the practical considerations when implementing the Simplex method, such as numerical stability and efficiency?
How do Interior Point methods work in more detail, and what are their advantages and disadvantages compared to the Simplex method?
Are there other algorithms for linear programming beyond Simplex and Interior Point methods?

This lecture provides a solid foundation in the Simplex method, preparing you for more advanced topics in linear programming and optimization. Further study and practice are encouraged to deepen your understanding and skills in this area.

--- title: "Lecture Notes on the Simplex Method" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture focuses on the Simplex method, a fundamental algorithm for solving linear programming problems. We will examine the method in detail, striving for clarity and simplicity despite its technical nature. Understanding the Simplex method is crucial for optimization across various fields. We will revisit the standard form of linear programs, systematically develop the steps of the Simplex algorithm, and address key concepts such as bases, basic variables, reduced costs, and optimality conditions. We will also discuss potential challenges like degeneracy and cycling, along with methods to handle them. Techniques for finding an initial feasible basis will be explored. Finally, we will briefly touch upon the computational complexity of the Simplex method and alternative polynomial-time algorithms. # Linear Programming in Standard Form ## Definition of Standard Form We begin by recalling the standard form of a Linear Programming (LP) problem. A generic LP in standard form is expressed as: $$\begin{aligned} \text{Maximize } & c^T x \\ \text{subject to } & Ax = b \\ & x \geq 0 \end{aligned}$$ where: - $x$ is the vector of variables to be determined. - $c$ is the cost vector. - $A$ is an $m \times (m+n)$ matrix of full rank $m$. This implies that all rows of $A$ are linearly independent, and if $A$ has $m$ rows, it must have at least $m$ columns (here denoted as $m+n$). - $b$ is the right-hand side vector. - $x \geq 0$ indicates that all variables must be non-negative. ## Example of a Standard Form LP Consider the following example of a linear programming problem in standard form: $$\begin{aligned} \text{Maximize } & 2x_1 - 4x_2 + x_3 + 2x_4 - x_5 \\ \text{subject to } & 2x_1 + 3x_2 - 2x_3 + 5x_4 - x_5 = 3 \\ & x_1 + x_3 + x_4 - x_5 = 4 \\ & -x_1 + 2x_2 + x_3 + x_4 + 3x_5 = 1 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}$$ This problem has three constraints (equations) and five variables. ## Matrix Representation In matrix form, the example can be represented as: - Cost vector $c^T = \begin{pmatrix} 2 & -4 & 1 & 2 & -1 \end{pmatrix}$ - Constraint matrix $A = \begin{pmatrix} 2 & 3 & -2 & 5 & -1 \\ 1 & 0 & 1 & 1 & -1 \\ -1 & 2 & 1 & 1 & 3 \end{pmatrix}$ - Right-hand side vector $b = \begin{pmatrix} 3 \\ 4 \\ 1 \end{pmatrix}$ The problem is to maximize $c^T x$ subject to $Ax = b$ and $x \geq 0$. # Bases and Basic Variables ## Definition of a Basis ::: tcolorbox A basis is a set of column indices $B$ such that the corresponding columns of matrix $A$, denoted as $A_B$, are linearly independent and there are $m$ such indices, where $m$ is the number of rows in $A$. The columns $A_B$ form a basis for $\mathbb{R}^m$. ::: Let $B$ be the set of indices of the basis columns, and let $N$ be the set of indices of the remaining columns (non-basis columns). ## Basic and Non-Basic Variables - **Basic Variables**: Variables corresponding to the indices in the basis $B$ are called basic variables, denoted as $x_B$. - **Non-Basic Variables**: Variables corresponding to the indices in the non-basis set $N$ are called non-basic variables, denoted as $x_N$. ::: tcolorbox Consider the basis $B = \{1, 3, 4\}$ for our example. The columns of $A$ corresponding to these indices are: These columns are linearly independent (can be verified using Gaussian elimination). Thus, $B = \{1, 3, 4\}$ is a valid basis. The non-basis indices are $N = \{2, 5\}$. ::: ## Partitioning the Problem Given a basis $B$ and non-basis $N$, we can partition the problem components: ### Submatrices $A_B$ and $A_N$ - $A_B$: Submatrix of $A$ consisting of columns with indices in $B$. - $A_N$: Submatrix of $A$ consisting of columns with indices in $N$. ### Cost Vectors $c_B$ and $c_N$ - $c_B$: Subvector of $c$ consisting of costs with indices in $B$. - $c_N$: Subvector of $c$ consisting of costs with indices in $N$. ### Variable Vectors $x_B$ and $x_N$ - $x_B$: Vector of basic variables. - $x_N$: Vector of non-basic variables. For our example with basis $B = \{1, 3, 4\}$ and $N = \{2, 5\}$: - $x_B = \begin{pmatrix} x_1 \\ x_3 \\ x_4 \end{pmatrix}$, $x_N = \begin{pmatrix} x_2 \\ x_5 \end{pmatrix}$ - $c_B^T = \begin{pmatrix} 2 & 1 & 2 \end{pmatrix}$, $c_N^T = \begin{pmatrix} -4 & -1 \end{pmatrix}$ - $A_B = \begin{pmatrix} 2 & -2 & 5 \\ 1 & 1 & 1 \\ -1 & 1 & 1 \end{pmatrix}$, $A_N = \begin{pmatrix} 3 & -1 \\ 0 & -1 \\ 2 & 3 \end{pmatrix}$ ## Rewriting the System The system $Ax = b$ can be rewritten as $A_B x_B + A_N x_N = b$. To express basic variables in terms of non-basic variables, we multiply the system by $A_B^{-1}$ (since $A_B$ is a basis, it is invertible) from the left: $$I x_B + A_B^{-1} A_N x_N = A_B^{-1} b$$ Let $\bar{A}_N = A_B^{-1} A_N$ and $\bar{b} = A_B^{-1} b$. Then the system becomes: and the constraints are: $$\begin{aligned} x_B + \bar{A}_N x_N &= \bar{b} \\ x_B &\geq 0 \\ x_N &\geq 0 \end{aligned}$$ ## Example of Rewriting the System For our example with basis $B = \{1, 3, 4\}$, we first calculate $A_B^{-1}$: Then we compute $\bar{A}_N = A_B^{-1} A_N$ and $\bar{b} = A_B^{-1} b$: $$\bar{A}_N = \begin{pmatrix} 0 & 1 & -1 \\ -1/2 & 7/2 & -3/2 \\ 1 & -2 & 2 \end{pmatrix} \begin{pmatrix} 3 & -1 \\ 0 & -1 \\ 2 & 3 \end{pmatrix} = \begin{pmatrix} -2 & -4 \\ -9/2 & -5 \\ 7 & 7 \end{pmatrix}$$ The transcription example shows a different $\bar{A}_N$ and $\bar{b}$. Let's use the provided $\bar{A}_N$ and $\bar{b}$ from the transcription for consistency. According to the transcription, we have: $$\bar{A}_N = \begin{pmatrix} -1 & -2 \\ 0 & 2/7 \\ 1 & 5/7 \end{pmatrix}, \quad \bar{b} = \begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix}$$ Thus, the rewritten system is: $$\begin{aligned} x_1 - x_2 - 2x_5 &= 3/2 \\ x_3 + 2/7 x_5 &= 25/14 \\ x_2 + x_4 + 5/7 x_5 &= 5/7 \end{aligned}$$ Rewriting to express basic variables in terms of non-basic variables: $$\begin{aligned} x_1 &= 3/2 + x_2 + 2x_5 \\ x_3 &= 25/14 - 2/7 x_5 \\ x_4 &= 5/7 - x_2 - 5/7 x_5 \end{aligned}$$ ## Independent and Dependent Variables From the rewritten system, it's clear that $x_2$ and $x_5$ (non-basic variables) are independent, while $x_1, x_3, x_4$ (basic variables) are dependent on $x_2$ and $x_5$. We need to choose $x_2 \geq 0$ and $x_5 \geq 0$ such that $x_1 \geq 0, x_3 \geq 0, x_4 \geq 0$. ## Reduced Costs The objective function is $c^T x = c_B^T x_B + c_N^T x_N$. Substituting $x_B = \bar{b} - \bar{A}_N x_N$: The term $c_B^T \bar{b}$ is a constant. The coefficients of $x_N$ in the objective function are called **reduced costs**, denoted as $\bar{c}_N^T = c_N^T - c_B^T \bar{A}_N$. ## Rewriting the Objective Function The objective function becomes: $$\text{Maximize } z = c_B^T \bar{b} + \bar{c}_N^T x_N$$ where $\bar{c}_N^T = c_N^T - c_B^T A_B^{-1} A_N$. For our example, using values from transcription: $\bar{c}_N^T = \begin{pmatrix} -4 & 16/7 \end{pmatrix}$. Constant term: $c_B^T \bar{b} = \begin{pmatrix} 2 & 1 & 2 \end{pmatrix} \begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix} = 3 + \frac{25}{14} + \frac{10}{7} = \frac{87}{14}$. Objective function: $z = \frac{87}{14} + \begin{pmatrix} -4 & 16/7 \end{pmatrix} \begin{pmatrix} x_2 \\ x_5 \end{pmatrix} = \frac{87}{14} - 4x_2 + \frac{16}{7} x_5$. ## Canonical Form The problem is now rewritten in canonical form with respect to the basis $B$: $$\begin{aligned} \text{Maximize } & \frac{87}{14} - 4x_2 + \frac{16}{7} x_5 \\ \text{subject to } & x_1 = 3/2 + x_2 + 2x_5 \\ & x_3 = 25/14 - 2/7 x_5 \\ & x_4 = 5/7 - x_2 - 5/7 x_5 \\ & x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}$$ And equivalently, focusing on upper bounds for $x_N$ to ensure $x_B \geq 0$: $$\begin{aligned} \text{Maximize } & \frac{87}{14} - 4x_2 + \frac{16}{7} x_5 \\ \text{subject to } & x_2 + 2x_5 \geq -3/2 \\ & 2/7 x_5 \leq 25/14 \implies x_5 \leq 25/4 \\ & x_2 + 5/7 x_5 \leq 5/7 \implies x_2 \leq 5/7 - 5/7 x_5 \\ & x_2, x_5 \geq 0 \end{aligned}$$ More accurately, the constraints in terms of $\bar{A}_N$ and $\bar{b}$ are $\bar{b} - \bar{A}_N x_N \geq 0$ and $x_N \geq 0$. So, $\bar{A}_N x_N \leq \bar{b}$ and $x_N \geq 0$. $$\begin{pmatrix} -1 & -2 \\ 0 & 2/7 \\ 1 & 5/7 \end{pmatrix} \begin{pmatrix} x_2 \\ x_5 \end{pmatrix} \leq \begin{pmatrix} 3/2 \\ 25/14 \\ 5/7 \end{pmatrix}$$ $$\begin{aligned} -x_2 - 2x_5 &\leq 3/2 \\ 2/7 x_5 &\leq 25/14 \\ x_2 + 5/7 x_5 &\leq 5/7 \end{aligned}$$ and $x_2, x_5 \geq 0$. ## Key Idea of the Simplex Method The key idea is to rewrite the original problem in terms of non-basic variables for a chosen basis. By changing the basis systematically, the Simplex method searches for an optimal basis where the solution becomes straightforward to find. In this canonical form, we have a problem in a lower dimension (in terms of non-basic variables), which is derived from the original higher-dimensional problem. # The Simplex Method ## General Problem Formulation The general problem we are addressing is to maximize $c^T x$ subject to $Ax = b, x \geq 0$. ## The PDB Problem For each basis $B$, we can formulate a problem in terms of non-basic variables, denoted as PDB (Problem Dependent on Basis). PDB is to maximize $\bar{c}_N^T x_N$ subject to $\bar{A}_N x_N \leq \bar{b}$ and $x_N \geq 0$. The original objective value is $c_B^T \bar{b} + \bar{c}_N^T x_N$. ## Finding the Optimal Basis The Simplex method aims to find a basis $B^*$ such that the PDB problem related to $B^*$ is easily solvable, ideally when the optimal solution for PDB is $x_N = 0$. ## When is the Origin Optimal? Consider the PDB problem: Maximize $\bar{c}_N^T x_N$ subject to $\bar{A}_N x_N \leq \bar{b}, x_N \geq 0$. The solution $x_N = 0$ is optimal if increasing any component of $x_N$ does not improve the objective function. This happens when all reduced costs are non-positive, i.e., $\bar{c}_N \leq 0$. ## Conditions for Optimal Basis A basis $B$ is optimal if it satisfies two conditions: ### Non-positive Reduced Costs $\bar{c}_N = c_N - c_B^T \bar{A}_N \leq 0$. ### Non-negative $\bar{b}$ vector $\bar{b} = A_B^{-1} b \geq 0$. This ensures that setting $x_N = 0$ leads to a feasible basic solution $x_B = \bar{b} \geq 0$. ## Basic Feasible Solutions (BFS) ::: tcolorbox A basic feasible solution is obtained by choosing a basis $B$, setting non-basic variables $x_N = 0$, and solving $A_B x_B = b$ for basic variables $x_B$. If $x_B = A_B^{-1} b = \bar{b} \geq 0$, then $(x_B, x_N)$ is a BFS. ::: ## Degenerate and Non-Degenerate Solutions - **Non-Degenerate BFS**: A BFS is non-degenerate if all basic variables are strictly positive, i.e., $x_B > 0$. - **Degenerate BFS**: A BFS is degenerate if at least one basic variable is zero, i.e., at least one component of $x_B$ is 0. ## Existence of Optimal Basic Solution ::: tcolorbox If an optimal solution exists, then there exists an optimal basic feasible solution. ::: This is a key justification for the Simplex method, which searches among BFSs. ## The Goal of the Simplex Method The goal of the Simplex method is to find an optimal basis $B^*$ such that the corresponding BFS is an optimal solution to the original LP problem. This is achieved by iteratively moving from one basis to another, improving the objective function at each step (or at least not decreasing it). ## Finite Number of Bases The number of possible bases is finite, bounded by $\binom{m+n}{m}$, where $m+n$ is the number of columns in $A$ and $m$ is the number of rows. This finiteness is crucial for the Simplex method to terminate in a finite number of steps (in the absence of cycling). ## Iterative Search for Optimal Basis The Simplex method is an iterative algorithm that starts with an initial feasible basis and moves to adjacent bases in search of an optimal basis. ## Moving Between Bases The Simplex method moves from one basis to an **adjacent basis**. ### Adjacent Bases Two bases are adjacent if they share $m-1$ columns. Moving to an adjacent basis involves removing one column from the current basis and adding one column from the non-basis set. This operation is called **pivoting**. ## Degeneracy and the Simplex Method ### Bases with the same BFS In the presence of degeneracy, different bases can lead to the same BFS. This is because in a degenerate BFS, some basic variables are zero. ## Pivoting Pivoting is the operation of changing the basis by exchanging one basic variable with a non-basic variable. It is the core step in moving from one BFS to another in the Simplex method. ## Choosing the Entering Variable The **entering variable** is a non-basic variable that is chosen to become basic in the next iteration. ### Greedy Approach A common strategy is to choose the entering variable with the most positive reduced cost. This is a greedy approach aimed at maximizing the increase in the objective function in each iteration. ## Determining the Level of the Entering Variable Once an entering variable $x_j$ is chosen, we need to determine how much its value can be increased. This is limited by the constraints that basic variables must remain non-negative ($x_B = \bar{b} - \bar{A}_N x_N \geq 0$). We calculate the maximum allowable increase by considering the ratios $\frac{\bar{b}_i}{\bar{a}_{ij}}$ for all $\bar{a}_{ij} > 0$. ## Unbounded Problems If, for an entering variable $x_j$, all coefficients $\bar{a}_{ij}$ in the column $\bar{A}_N$ corresponding to $x_j$ are non-positive ($\bar{a}_{ij} \leq 0$), it means that $x_j$ can be increased indefinitely without violating feasibility. In this case, the problem is **unbounded**, and there is no optimal solution. ## Choosing the Exiting Variable The **exiting variable** is a basic variable that becomes non-basic in the next iteration. It is chosen based on the minimum ratio test. The exiting variable corresponds to the row $k$ that achieves the minimum ratio: $$\min_{i | \bar{a}_{ij} > 0} \left\{ \frac{\bar{b}_i}{\bar{a}_{ij}} \right\} = \frac{\bar{b}_k}{\bar{a}_{kj}}$$ The basic variable corresponding to row $k$ becomes the exiting variable. ## Pseudocode of the Simplex Method :::: tcolorbox ::: algorithmic Matrix $A$, vectors $b$, $c$, initial feasible basis $B$ Choose an entering variable $x_j$ with $\bar{c}_j > 0$ Check for unboundedness: If $\bar{a}_{ij} \leq 0$ for all $i$, then problem is unbounded, terminate. Determine ratios for all $i$ such that $\bar{a}_{ij} > 0$: $r_i = \frac{\bar{b}_i}{\bar{a}_{ij}}$ Find the minimum ratio: $r_k = \min_{i | \bar{a}_{ij} > 0} \{r_i\}$ Choose the exiting variable $x_{B_k}$ corresponding to row $k$ Update basis: $B_{new} = (B \setminus \{B_k\}) \cup \{j\}$, $N_{new} = (N \setminus \{j\}) \cup \{B_k\}$ Update $\bar{A}_N$, $\bar{b}$, $\bar{c}_N$ for the new basis Return current basic feasible solution $x$ ::: :::: ## Summary of the Simplex Process The Simplex method iteratively improves the objective function by moving from one BFS to another. It selects an entering variable with a positive reduced cost and an exiting variable based on the minimum ratio test. This process continues until no more improvement is possible, indicated by all reduced costs being non-positive. ## Cycling and Degeneracy ### Potential for Infinite Loops In the presence of degeneracy, the Simplex method might cycle, meaning it could revisit a basis and enter an infinite loop without reaching the optimal solution. This occurs when a sequence of pivots does not improve the objective function. ## Anti-Cycling Rules To prevent cycling, anti-cycling rules are used. ### Randomized Pivoting Randomly choosing among eligible entering or exiting variables can probabilistically avoid cycling. ### Blend's Rule Blend's rule is a deterministic anti-cycling rule that chooses the entering variable with the smallest index among those with positive reduced costs, and similarly, chooses the exiting variable with the smallest index among those achieving the minimum ratio. ## Finding an Initial Feasible Basis A crucial step for starting the Simplex method is finding an initial feasible basis. This is not always straightforward. ## Two-Phase Simplex Method The **Two-Phase Simplex Method** is used to find an initial feasible basis and then solve the original LP problem. ### Phase 1: Auxiliary LP In Phase 1, an auxiliary LP problem is formulated. Artificial variables are added to the original constraints to create an initial feasible basis easily. The objective in Phase 1 is to minimize the sum of these artificial variables. ### Phase 2: Original LP If Phase 1 successfully reduces the sum of artificial variables to zero, a feasible basis for the original problem is obtained. Phase 2 then uses this basis to solve the original LP problem using the standard Simplex method. ## Auxiliary LP For a standard form LP $Ax = b, x \geq 0, b \geq 0$, the auxiliary LP is constructed as follows: $$\begin{aligned} \text{Minimize } & \sum_{i=1}^m y_i \\ \text{subject to } & Ax + y = b \\ & x \geq 0, y \geq 0 \end{aligned}$$ where $y = (y_1, \dots, y_m)^T$ are artificial variables. An initial feasible basis for this auxiliary problem is formed by the columns corresponding to $y$. ## Optimality of the Auxiliary LP The optimal value of the auxiliary LP indicates the feasibility of the original LP. If the minimum value is 0, then the original LP is feasible. If the minimum value is greater than 0, the original LP is infeasible. ## Computational Complexity ### Exponential Number of Bases In the worst case, the Simplex method can visit an exponential number of bases, making its worst-case complexity exponential. This is due to the potential for the algorithm to traverse many vertices of the feasible region. ### Polynomial Algorithms Despite the exponential worst-case complexity, polynomial-time algorithms exist for linear programming. ### Ellipsoid Method The **Ellipsoid method**, developed by Leonid Khachiyan in 1979, was the first algorithm proven to solve linear programming problems in polynomial time. However, despite its theoretical importance, the Ellipsoid method is not efficient in practice due to its slow convergence and numerical instability. ### Interior Point Method The **Interior Point Method**, notably Karmarkar's algorithm from 1984, provides a more practical polynomial-time algorithm for linear programming. Unlike the Simplex method, which moves along the edges of the feasible region, interior point methods move through the interior of the feasible region. These methods have shown to be very efficient in practice, especially for large-scale linear programming problems. # Conclusion In this lecture, we have explored the Simplex method in detail, covering its algebraic foundations, iterative process, and key components such as bases, basic variables, reduced costs, and pivoting. We have seen how the Simplex method systematically searches for an optimal solution by moving from one basic feasible solution to another, improving the objective function at each step. **Important Remarks and Key Takeaways:** - The Simplex method is a powerful algorithm for solving linear programming problems, widely used in practice due to its efficiency on average-case problems. - Understanding the concepts of bases, basic and non-basic variables, and reduced costs is crucial for grasping the mechanics of the Simplex method. - Degeneracy and cycling are potential issues in the Simplex method, but anti-cycling rules like Blend's rule and randomized pivoting can effectively prevent infinite loops. - The Two-Phase Simplex method provides a systematic approach to finding an initial feasible basis, making the Simplex method applicable to any linear programming problem. - While the Simplex method has exponential worst-case complexity, polynomial-time algorithms such as the Ellipsoid method and Interior Point methods exist, offering theoretical and sometimes practical advantages, especially for large-scale problems. **Follow-up Questions and Topics for the Next Lecture:** - How do different pivoting rules affect the performance of the Simplex method in practice? - Can we visualize the Simplex method geometrically in lower dimensions? - What are the practical considerations when implementing the Simplex method, such as numerical stability and efficiency? - How do Interior Point methods work in more detail, and what are their advantages and disadvantages compared to the Simplex method? - Are there other algorithms for linear programming beyond Simplex and Interior Point methods? This lecture provides a solid foundation in the Simplex method, preparing you for more advanced topics in linear programming and optimization. Further study and practice are encouraged to deepen your understanding and skills in this area.