Simplex in Reverse, understanding the Dual Simplex Algorithm

The Dual Simplex Algorithm, developed by Carlton E. Lemke (Lemke, 1954), provides an alternative approach to solving linear optimization problems. While the classical Simplex algorithm maintains primal feasibility and improves the objective function until the optimum is reached, the Dual Simplex algorithm follows the opposite strategy: it preserves dual feasibility while progressively eliminating violations of primal feasibility through successive pivot operations.

Although this change in perspective may initially seem counterintuitive, it proves especially useful in many practical situations where finding an initial primal feasible solution is difficult. Understanding how the algorithm works not only broadens our computational toolbox but also provides deeper insight into the behavior of linear optimization models.

The Dual Simplex algorithm is particularly effective in situations such as:

• Sensitivity Analysis: When new constraints are added or the resource vector of an already solved problem is modified, causing the current optimal solution to become primal infeasible.

• Problems with $\geqslant$ Constraints: It is often faster than the Two-Phase Method or the Big-M Method.

• Integer Optimization: It is commonly used in cutting-plane algorithms.

Before studying the algorithm in detail, it is helpful to compare it with the classical Simplex method:

	Primal Simplex	Dual Simplex
Maintains throughout the iterations	Primal feasibility	Dual feasibility
Objective of each pivot operation	Improve the objective function	Restore primal feasibility
Requires to start	A primal feasible solution	A dual feasible solution
Terminates when	No improving reduced costs remain	All basic variables are nonnegative

Steps of the Dual Simplex Algorithm

The algorithm can only be initialized when the initial tableau is dual feasible, that is, when the values $z_j-c_j$ satisfy the optimality condition, even if some basic variables are negative.

The steps of the algorithm are as follows:

1. Initialization: Select a basis $\mathbf{B} = \mathbf{I}$ consisting of the slack variables so as to guarantee initial dual feasibility.
2. Stopping Criterion: If all basic variables are nonnegative ($\mathbf{x}_\mathbf{B} \geqslant \mathbf{0}$), the optimal solution has been reached.

3. If at least one basic variable is negative ($x_{\mathbf{B}_i} < 0$), the current solution is primal infeasible and can be improved:

   • Leaving Rule (Leaving Variable): Select the basic variable with the most negative value, since it represents the greatest violation of primal feasibility. The leaving variable, $x_l$, is therefore the one with the most negative value in the right-hand-side column:

     \[\bar{x}_l = \min\{\bar{x}_s : \bar{x}_s < 0, \forall s \in \mathcal{I}\}\]

   • Entering Rule (Entering Variable): To determine the entering variable $x_k$, compute the minimum ratio between the values $z_j - c_j$ and the negative entries of the leaving row ($y_{lj} < 0$):

     \[\frac{z_k - c_k}{y_{lk}} = \min \left\{ \frac{z_j - c_j}{y_{lj}} : y_{lj} < 0, \forall j \in \mathcal{J} \right\}\]

   • Pivoting: Perform the pivot operation on the element $y_{lk}$ exactly as in the classical Primal Simplex algorithm, update the tableau, and return to Step 2.

The following example illustrates the complete execution of the algorithm.

Numerical Example

Consider the following linear optimization problem:

\[\begin{aligned} \max\;\; & z = 2x_1 + 6x_2 + 4x_3 \\ \textrm{s. a:}\;\; & - x_1 - 2x_2 - x_3 \leqslant -4 \\ & -2x_1 + x_2 - 3x_3 \leqslant -1 \\ & 4x_1 - 3x_2 + 2x_3 \leqslant -2 \\ & x_1, x_2, x_3 \geqslant 0 \end{aligned}\]

whose standard form is

\[\begin{aligned} \max\;\; & z = 2x_1 + 6x_2 + 4x_3 \\ \textrm{s. a:}\;\; & - x_1 - 2x_2 - x_3 + x_4^s = -4 \\ & -2x_1 + x_2 - 3x_3 + x_5^s = -1 \\ & 4x_1 - 3x_2 + 2x_3 + x_6^s = -2 \\ & x_1, x_2, x_3, x_4^s, x_5^s, x_6^s \geqslant 0 \end{aligned}\]

The final Simplex tableau is:

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}2} & {\color{gray}6} & {\color{gray}4} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^s & \\ \hline & z_j-c_j & 0 & 0 & 0 & -18/7 & -6/7 & -4/7 & 86/7 \\ \hline {\color{gray}2} & x_1 & 1 & 0 & 0 & -1/3 & 1/3 & 1/3 & 1/3 \\ {\color{gray}4} & x_3 & 0 & 0 & 1 & 2/21 & -11/21 & -5/21 & 13/21 \\ {\color{gray}6} & x_2 & 0 & 1 & 0 & -8/21 & 2/21 & -1/21 & 32/21 \\ \hline \end{array}\]

After three iterations, all basic variables are nonnegative, meaning that primal feasibility has been restored. Since dual feasibility has been maintained throughout the entire process, the resulting solution is optimal:

\[(\mathbf{x}^*)^\intercal = (1/3,32/21,13/21,0,0,0) \quad z^* = 86/7\]

The Artificial Constraint Method

So far, we have assumed that the initial tableau is dual feasible. However, this is not always the case. In such situations, it is necessary to artificially construct a basis that satisfies this condition before applying the algorithm.

Whenever this occurs, the Artificial Constraint Method is used. The main idea is to temporarily introduce a new constraint that forces the algorithm to construct a dual-feasible basis. Once dual feasibility has been restored, the artificial constraint is no longer needed and the algorithm continues on the original problem. The artificial constraint is defined as

\[\sum_{j \in \mathcal{N}} x_j \leqslant M\]

where:

• $\mathcal{N}$ is the set of variables that violate dual feasibility (i.e., those with $z_j-c_j > 0$ in a minimization problem, or equivalently $z_j-c_j < 0$ in a maximization problem).
• $M$ is a sufficiently large positive constant (an artificial parameter).

After adding the constraint, its corresponding slack variable is introduced and a forced pivot is performed so that this slack variable immediately leaves the basis. Once the pivot has been completed, dual feasibility is restored. From that point onward, the standard Dual Simplex algorithm proceeds normally. At termination, one of the following three situations may occur:

• Optimal Solution: All basic variables are nonnegative ($x_s \geqslant 0$), and the slack variable associated with the artificial constraint remains in the basis with a strictly positive value. The original problem has either a unique optimum or multiple optimal solutions.
• Unbounded Optimal Solution: All basic variables are nonnegative ($x_s \geqslant 0$), but the slack variable associated with the artificial constraint is either nonbasic or remains in the basis with value equal to zero. The original problem is unbounded.
• Infeasible Problem: There exists a negative basic variable ($x_s < 0$) whose corresponding row satisfies $\mathbf{y}_s \geqslant \mathbf{0}$. This implies that the dual problem is unbounded and, by duality, the original primal problem is infeasible.

Numerical Examples

Depending on the behavior of the variable associated with the artificial constraint, the algorithm may terminate in different scenarios. The following examples illustrate each possible outcome.

Unique Optimal Solution

The most common situation is when the problem has a unique optimal solution.

Consider the following linear optimization problem:

\[\begin{aligned} \max\;\; & z = x_1 + 6x_2 \\ \textrm{s. t.:}\;\; & x_1 + 2x_2 \leqslant 20 \\ & x_1 + \frac12x_2 \geqslant \frac12 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

whose standard form is

\[\begin{aligned} \max\;\; & z = x_1 + 6x_2 \\ \textrm{s. t.:}\;\; & x_1 + 2x_2 + x_3^s = 20 \\ & -x_1 - \frac12x_2 + x_4^s = -\frac12 \\ & x_1, x_2, x_3^s, x_4^s \geqslant 0 \end{aligned}\]

whose initial Simplex tableau is

\[\begin{array}{cc|rrrr|r} & & {\color{gray}1} & {\color{gray}6} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & \\ \hline & z_j-c_j & -1 & -6 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^s & 1 & 2 & 1 & 0 & 20 \\ {\color{gray}0} & x_4^s & -1 & -1/2 & 0 & 1 & -1/2 \\ \hline \end{array}\]

Since the initial tableau is not dual feasible, the artificial constraint

\[x_1 + x_2 \leqslant M\]

must be introduced.

The final tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}6} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & x_5^s & \\ \hline & z_j-c_j & 2 & 0 & 3 & 0 & 0 & 60 \\ \hline {\color{gray}0} & x_5^s & 1/2 & 0 & -1/2 & 0 & 1 & M-10 \\ {\color{gray}0} & x_4^s & -3/4 & 0 & 1/4 & 1 & 0 & 9/2 \\ {\color{gray}6} & x_2 & 1/2 & 1 & 1/2 & 0 & 0 & 10 \\ \hline \end{array}\]

Notice that the optimal solution has been reached because the slack variable associated with the artificial constraint ($x_5^s$) remains in the basis:

\[(\mathbf{x}^*)^\intercal = (0,10,0,9/2) \quad z^* = 60\]

Unbounded Optimal Solution

Consider the following linear optimization problem:

\[\begin{aligned} \max\;\; & z = -4x_1 + 5x_2 \\ \textrm{s. t.:}\;\; & 2x_1 + 2x_2 \geqslant 4 \\ & x_1 - x_2 \geqslant 3 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

whose standard form is

\[\begin{aligned} \max\;\; & z = -4x_1 + 5x_2 \\ \textrm{s. t.:}\;\; & -2x_1 - 2x_2 + x_3^s = -4 \\ & - x_1 + x_2 + x_4^s = -3 \\ & x_1, x_2, x_3^s, x_4^s \geqslant 0 \end{aligned}\]

whose initial Simplex tableau is

\[\begin{array}{cc|rrrr|r} & & {\color{gray}-4} & {\color{gray}5} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & \\ \hline & z_j-c_j & 4 & -5 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^s & -2 & -2 & 1 & 0 & -4 \\ {\color{gray}0} & x_4^s & -1 & 1 & 0 & 1 & -3 \\ \hline \end{array}\]

Since the initial tableau is not dual feasible, the artificial constraint

\[x_2 \leqslant M\]

must be introduced.

Note: The same result would be obtained using the constraint $x_1 + x_2 \leqslant M$.

The final tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}-4} & {\color{gray}5} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 0 & 4 & 1 & M-12 \\ \hline {\color{gray}0} & x_3^s & 0 & 0 & 1 & -2 & 4 & 4M+2 \\ {\color{gray}-4} & x_1 & 1 & 0 & 0 & -1 & 1 & M+3 \\ {\color{gray}5} & x_2 & 0 & 1 & 0 & 0 & 1 & M \\ \hline \end{array}\]

Notice that the slack variable associated with the artificial constraint ($x_5^s$) is no longer in the basis while primal feasibility has been achieved. Therefore, the original problem has unbounded optimal solution.

Infeasible Problem

Consider the following linear optimization problem:

\[\begin{aligned} \max\;\; & z = 2x_1 + x_2 \\ \textrm{s. t.:}\;\; & x_1 + x_2 \leqslant 2 \\ & -3x_1 + x_2 \geqslant 3 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

whose standard form is

\[\begin{aligned} \max\;\; & z = 2x_1 + x_2 \\ \textrm{s. t.:}\;\; & x_1 + x_2 + x_3^s = 2 \\ & 3x_1 - x_2 + x_4^s = -3 \\ & x_1, x_2, x_3^s, x_4^s \geqslant 0 \end{aligned}\]

whose initial Simplex tableau is

\[\begin{array}{cc|rrrr|r} & & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & \\ \hline & z_j-c_j & -2 & -1 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^s & 1 & 1 & 1 & 0 & 2 \\ {\color{gray}0} & x_4^s & 3 & -1 & 0 & 1 & -3 \\ \hline \end{array}\]

Since the initial tableau is not dual feasible, the artificial constraint

\[x_1 + x_2 \leqslant M\]

must be introduced.

The final tableau is

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^s & x_4^s & x_5^s & \\ \hline & z_j-c_j & 0 & 0 & 5/4 & 1/4 & 0 & 7/4 \\ \hline {\color{gray}0} & x_5^s & 0 & 0 & -1 & 0 & 1 & M-2 \\ {\color{gray}1} & x_2 & 0 & 1 & 3/4 & -1/4 & 0 & 9/4 \\ {\color{gray}2} & x_1 & 1 & 0 & 1/4 & 1/4 & 0 & -1/4 \\ \hline \end{array}\]

The next iteration cannot be performed because the candidate entering variable has no valid pivot element. This implies that the dual problem is unbounded and, by duality, the original primal problem is infeasible.

The Dual Simplex algorithm is a natural alternative to the classical Simplex method whenever a dual-feasible but primal-infeasible solution is available. Besides being an efficient technique for solving certain classes of linear optimization problems, it also plays a fundamental role in more advanced procedures such as sensitivity analysis, integer optimization, and column generation algorithms. Understanding how it works not only broadens the range of optimization techniques at our disposal but also provides deeper insight into the close relationship between a primal problem and its corresponding dual.