Fact-checked by Grok 2 weeks ago

Revised simplex method

The revised simplex method is a computational variant of the for solving problems, introduced by George B. Dantzig in 1953 as an efficient implementation that avoids maintaining a full tableau by instead tracking the current basis matrix and its . This approach focuses on updating only the essential data—such as reduced costs and basis representations—through matrix operations at each iteration, enabling the method to progress from one to an adjacent one until optimality is achieved. In contrast to the standard simplex method, which requires explicit updates to an entire coefficient tableau and can become cumbersome for large-scale problems due to high storage and computational demands, the revised simplex method maintains primal feasibility and complementary slackness while seeking dual feasibility by solving linear systems involving the basis . Key steps include selecting an entering variable based on the most negative (for minimization), determining the leaving variable via a minimum on the updated column, and then pivoting the basis by updating the using techniques like the product form of the inverse or . This structure not only reduces memory usage from O(n²) to O(m²)—where m is the number of constraints and n the number of variables—but also enhances by minimizing error accumulation in repeated operations. The method's efficiency has made it the foundation for most modern solvers, supporting extensions like the dual simplex algorithm and applications in , such as and scheduling. Despite its worst-case exponential , practical implementations often perform well, especially when combined with anti-cycling procedures to handle degeneracy.

Background

Relation to Standard Simplex Method

The standard simplex method, developed by George Dantzig in 1947, is a foundational algorithm for solving linear programming problems that operates by traversing the vertices of the feasible polyhedron to find an optimal basic feasible solution. It employs a tableau-based representation of the linear program, where the constraints and objective function are arranged in a matrix augmented with slack, surplus, or artificial variables to transform inequalities into equalities and ensure an initial feasible starting point. This tabular format allows the method to systematically evaluate and improve the objective value at each iteration while maintaining feasibility. The key steps of the standard simplex method begin with initialization, where an initial is identified, often using artificial variables if a natural starting basis is unavailable. Next, an entering is selected—typically the nonbasic with the most negative in the objective row of the tableau—to indicate potential improvement in the . The leaving is then chosen via the minimum on the updated column to prevent violation of nonnegativity constraints. Finally, the tableau is updated through elementary row operations to reflect the new basis, effectively pivoting to the adjacent . Despite its effectiveness for small to medium-sized problems, the standard simplex method exhibits limitations that become pronounced in large-scale applications, primarily due to redundant computations during tableau updates. Each iteration requires full Gaussian elimination-like operations on the entire tableau, recalculating coefficients that remain unchanged across iterations, which increases both time and quadratically with problem size. Furthermore, the monolithic tableau structure lacks , hindering efficient implementation of numerical safeguards against or adaptation to sparse matrices common in real-world optimization scenarios.

Motivations for Revision

The standard simplex method, while effective for small-scale linear programming problems, exhibits significant inefficiencies when applied to larger instances, particularly in terms of computational time and memory usage. In the full tableau implementation, each pivot operation requires updating the entire tableau, which has dimensions proportional to the number of constraints m and variables n, leading to a time complexity of O(mn) per iteration. This recomputation involves unnecessary operations on redundant entries, such as the identity matrix portion representing basic variables, making the process wasteful for problems where n \gg m. Furthermore, the storage requirement of O(mn) becomes prohibitive on early computers with limited memory, hindering scalability for real-world applications like resource allocation in industry. These drawbacks motivated the development of the revised simplex method in the early , as optimization problems grew in size with the advent of digital computers. Introduced by George B. Dantzig in 1953, with key contributions to its implementation and related techniques from E.M.L. Beale in 1954, the revised approach maintains only the basis inverse or —requiring O(m^2) storage—and computes necessary quantities on demand, reducing average time per iteration to O(m^2) in practice while preserving worst-case O(mn). This revision was particularly suited to the computational constraints of the era, enabling efficient handling of sparse matrices common in practical linear programs, such as those arising in network flows or . Beyond efficiency, the revised simplex method enhances and software , addressing vulnerabilities in the standard method's direct tableau manipulations. By solving linear systems via with partial pivoting instead of explicit inversions, it mitigates rounding errors that could accumulate in full tableau updates, especially for ill-conditioned bases. This modular —separating basis updates from and tests—facilitates into larger optimization codes, allowing reuse of factorizations across iterations and adaptation to specialized hardware or in later decades. These improvements established the revised simplex as the foundation for commercial solvers, transforming into a viable tool for during the 1960s expansion of computer-based optimization.

Problem Formulation

Linear Programming in Standard Form

The revised simplex method addresses linear programming problems, which seek to optimize a linear objective function subject to linear constraints. A general linear program in inequality form is formulated as maximizing the objective \mathbf{c}^T \mathbf{x} subject to A \mathbf{x} \leq \mathbf{b} and \mathbf{x} \geq \mathbf{0}, where \mathbf{c} \in \mathbb{R}^n is the coefficient vector for the decision variables \mathbf{x} \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n} is the constraint matrix with m rows corresponding to m inequality constraints, and \mathbf{b} \in \mathbb{R}^m is the right-hand-side vector. To apply the simplex method, including its revised variant, the problem must be converted to standard equality form. This involves introducing nonnegative slack variables \mathbf{s} \in \mathbb{R}^m for each inequality constraint, transforming A \mathbf{x} + \mathbf{s} = \mathbf{b} with \mathbf{s} \geq \mathbf{0}, while retaining the nonnegativity on \mathbf{x}. The resulting standard form is then maximize \mathbf{c}^T \mathbf{x} subject to \tilde{A} \tilde{\mathbf{x}} = \mathbf{b} and \tilde{\mathbf{x}} \geq \mathbf{0}, where \tilde{A} = [A \mid I_m] \in \mathbb{R}^{m \times (n+m)} augments the identity matrix for the slacks, and \tilde{\mathbf{x}} = [\mathbf{x}; \mathbf{s}]. In this standard form, assuming A has full row rank m, solutions correspond to vertices of the feasible , represented by . A arises by selecting m linearly independent columns of \tilde{A} to form the basis matrix B, an m \times m invertible submatrix, setting the corresponding basic variables \mathbf{x}_B = B^{-1} \mathbf{b} \geq \mathbf{0}, and the remaining nonbasic variables to zero. The simplex method, including the , iterates among such to reach optimality.

Primal and Dual Forms

In the context of the revised simplex method, which operates on linear programs in standard form, the associated dual problem provides a complementary perspective that facilitates economic interpretations and algorithmic efficiency. Given a primal maximization problem \max \mathbf{c}^T \mathbf{x} subject to \mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}, the dual is formulated as the minimization problem \min \mathbf{b}^T \mathbf{y} subject to \mathbf{A}^T \mathbf{y} \geq \mathbf{c}, \mathbf{y} \geq \mathbf{0}. This dual structure arises naturally from the Lagrangian dual of the primal constraints, where \mathbf{y} represents the multipliers associated with the equality constraints in the primal. The strong duality theorem asserts that if the primal problem is feasible and bounded, then the dual is also feasible and bounded, with the optimal values of the primal and dual being equal. This equivalence holds under the assumptions of and ensures that solving one problem yields the solution to the other, a property that underpins the convergence guarantees of simplex-based algorithms. In practice, this theorem implies no exists for feasible linear programs, allowing the revised simplex method to leverage dual information for verification of optimality without solving a separate problem. Within the revised simplex iterations, the dual variables \mathbf{y}, often termed shadow prices, play a crucial role in pricing non-basic variables by computing the reduced costs, which guide the selection of entering variables. These shadow prices quantify the marginal value of relaxing the primal constraints, providing interpretive insights into resource allocation while enabling efficient updates in the matrix-factorized basis representation used by the revised method. By maintaining dual feasibility alongside primal feasibility, the algorithm exploits this interplay to progress toward optimality.

Core Algorithm

Optimality and Feasibility Conditions

In the revised simplex method, a basic solution is defined by selecting a basis matrix B, which consists of m linearly independent columns of the constraint matrix A, where m is the number of constraints. The corresponding basic variables are given by x_B = B^{-1} b, with the non-basic variables set to zero, ensuring that the solution satisfies the equality constraints Ax = b. This solution is feasible if and only if x_B \geq 0, meaning all basic variables are non-negative, which aligns with the non-negativity requirements of the linear program. Optimality in the revised simplex method is determined by examining the reduced costs of the non-basic . The simplex multipliers, or , are computed as \pi^T = c_B^T B^{-1}, where c_B is the of coefficients for the basic . The for a non-basic j is then \bar{c}_j = \pi^T A_j - c_j, where c_j is the coefficient and A_j is the corresponding column of A. For a maximization problem, the current is optimal if \bar{c}_j \geq 0 for all non-basic j, indicating that introducing any non-basic into the basis would not improve the value. These conditions correspond to dual feasibility and complementary slackness in the Karush-Kuhn-Tucker optimality criteria for linear programs. If an initial basic feasible solution is not readily available, the revised simplex method employs a Phase I procedure to detect feasibility or infeasibility. This involves augmenting the original constraints with artificial variables to form an auxiliary problem: Ax + I x_a = b, x, x_a \geq 0, where x_a are the artificial variables and I is the . The is to minimize the sum of the artificial variables (or use a big-M penalty), solved via the revised simplex method starting from the trivial basis of artificial variables. If the optimal value of this auxiliary objective is zero, a to the original problem exists (with x_a = 0), and Phase II proceeds with the original objective using this basis; otherwise, the original problem is infeasible.

Basis Update and Pivot Selection

In the revised simplex method, basis update begins with the selection of an entering from the set of non-basic variables to improve value while preserving feasibility. For a maximization problem, the entering variable j is typically chosen as the non-basic index with the most negative \bar{c}_j < 0, where \bar{c}_j = \pi^T A_j - c_j and \pi^T = c_B^T B^{-1} represents the simplex multipliers derived from the current basis B. This selection, known as the Dantzig rule, prioritizes the variable that promises the steepest ascent in the objective function, as a unit increase in x_j would increase the objective by -\bar{c}_j. Once the entering variable is identified, the leaving variable is determined via the minimum ratio test to ensure the updated solution remains non-negative. Compute the search direction u = B^{-1} A_j, where A_j is the column corresponding to the entering variable. The maximum feasible step size is then \theta^* = \min\left\{ \frac{\hat{x}_{B(i)}}{u_i} \;\middle|\; i = 1, \dots, m, \; u_i > 0 \right\}, with \hat{x}_B = B^{-1} b denoting the current basic solution values. The leaving variable is the basic variable x_{B(r)} at the index r = \arg\min \{ \frac{\hat{x}_{B(i)}}{u_i} \mid u_i > 0 \}, which reaches zero first as x_j increases to \theta^*, thereby preventing any basic variable from becoming negative and maintaining feasibility. If all u_i \leq 0, the problem is unbounded. The pivot operation then swaps the entering and leaving variables to form the new basis B', updating the without requiring a full tableau recomputation. Specifically, replace the r-th column of B with A_j, and adjust the basic solution as x_B' = \hat{x}_B - \theta^* u with x_j' = \theta^*, while other non-basic variables remain zero. The basis inverse B^{-1} is efficiently updated using an or product-form decomposition, such as premultiplying by E = I - \frac{u e_r^T}{u_r} where e_r is the r-th , to avoid inverting the entire anew and enabling scalability for large problems. This step completes the iteration, yielding a new with an improved objective value.

Implementation Details

Matrix Factorizations for Efficiency

In the revised simplex method, explicit computation and storage of the basis inverse B^{-1} are avoided by instead maintaining an factorization of the basis B, where B = [LU](/page/Lu) with L lower triangular and U upper triangular. This approach enables efficient solution of linear systems involving B or B^T, such as those required for and tests, at a cost of O(m^2) arithmetic operations per iteration for an m \times m basis, significantly reducing computational overhead compared to full matrix inversions. Upon selecting a pivot column and row during basis update, the LU factorization is updated incrementally rather than recomputed from scratch, preserving efficiency across iterations. This involves applying targeted row and column operations to the L and U factors to reflect the change in basis, such as those derived from elementary matrices corresponding to the transformation. A prominent technique is the Forrest-Tomlin update, which modifies the factorization by adjusting specific rows and columns in L and U to account for the rank-one perturbation induced by the , thereby avoiding dense refactorizations. These strategies offer key advantages in handling sparse matrices typical of large-scale linear programs, as they minimize fill-in during updates—nonzero elements introduced in the factors—unlike the full tableau representation in the standard method, which can lead to excessive and storage demands. By exploiting sparsity through partial pivoting and selective updates, the revised method maintains and scalability for problems with thousands of constraints.

Numerical Example

Consider the problem of maximizing $3x_1 + 5x_2 subject to x_1 + 2x_2 \leq 4, $2x_1 + x_2 \leq 5, and x_1, x_2 \geq 0. To apply the revised simplex method, introduce nonnegative variables s_1 and s_2 to convert the inequalities to equalities, yielding the standard form: maximize $3x_1 + 5x_2 subject to x_1 + 2x_2 + s_1 = 4, $2x_1 + x_2 + s_2 = 5, and all variables nonnegative. The is A = \begin{bmatrix} 1 & 2 & 1 & 0 \\ 2 & 1 & 0 & 1 \end{bmatrix}, right-hand side b = \begin{bmatrix} 4 \\ 5 \end{bmatrix}, and objective coefficients c = [3, 5, 0, 0]. The initial basic feasible solution uses the slack variables as the basis, so the basis matrix B consists of the third and fourth columns of A, which is the $2 \times 2 identity matrix I. Thus, the initial LU factorization is trivial with L = I and U = I. The basic solution is x_B = B^{-1} b = b = [4, 5]^T, corresponding to s_1 = 4, s_2 = 5, x_1 = x_2 = 0, and objective value 0. To check optimality, compute the dual variables (simplex multipliers) \pi = c_B B^{-1}, where c_B = [0, 0]. Since B^{-1} = I, this requires no solve: \pi = [0, 0]. The reduced costs for the nonbasic variables are \bar{c}_j = c_j - \pi a_j, where a_j is the j-th column of A. For x_1 (j=1): \bar{c}_1 = 3 - [0, 0] \begin{bmatrix} 1 \\ 2 \end{bmatrix} = 3 > 0. For x_2 (j=2): \bar{c}_2 = 5 - [0, 0] \begin{bmatrix} 2 \\ 1 \end{bmatrix} = 5 > 0. Since this is a maximization problem and positive reduced costs indicate potential improvement, select the entering variable as x_2 (largest \bar{c}_j > 0). To find the leaving variable, compute the search direction d = B^{-1} a_2. With B^{-1} = I, this is a trivial forward/back : d = \begin{bmatrix} 2 \\ 1 \end{bmatrix}. The ratios for positive components of d are $4/2 = 2 (for row 1, s_1) and $5/1 = 5 (for row 2, s_2); the minimum , so s_1 leaves the basis. The step length is \theta = 2, updating the solution to x_B = [2, 3]^T (now for x_2 = 2, s_2 = 3) and objective value $5 \times 2 = 10. The new basis matrix is B = \begin{bmatrix} 2 & 0 \\ 1 & 1 \end{bmatrix}. Update the LU factorization via eta-file or direct computation: perform to obtain L = \begin{bmatrix} 1 & 0 \\ 0.5 & 1 \end{bmatrix} and U = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}. In the second iteration, compute \pi = c_B B^{-1} with new c_B = [5, 0]. To solve \pi B = c_B using the LU factorization B = LU, first solve \tilde{\pi} U = c_B by back-substitution (since U is upper triangular) to obtain \tilde{\pi}, then solve \pi L = \tilde{\pi} by (since L is lower triangular). The result is \pi = [2.5, 0]. The s are: for x_1: \bar{c}_1 = 3 - [2.5, 0] \begin{bmatrix} 1 \\ 2 \end{bmatrix} = 3 - 2.5 = 0.5 > 0; for s_1: \bar{c}_{s_1} = 0 - [2.5, 0] \begin{bmatrix} 1 \\ 0 \end{bmatrix} = -2.5 < 0. Select entering variable x_1 (only positive ). Compute d = B^{-1} a_1: L w = a_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} gives w = \begin{bmatrix} 1 \\ 1.5 \end{bmatrix}; back substitution U d = w gives d = \begin{bmatrix} 0.5 \\ 1.5 \end{bmatrix}. Ratios: $2/0.5 = 4 (row 1, x_2) and $3/1.5 = 2 (row 2, s_2); minimum is 2, so s_2 leaves. Update solution to x_B = [2, 1]^T (now x_1 = 2, x_2 = 1) and objective value $3 \times 2 + 5 \times 1 = 11. The new basis B = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} has LU factorization L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}, U = \begin{bmatrix} 1 & 2 \\ 0 & -3 \end{bmatrix} (after elimination). For the final check, compute \pi = c_B B^{-1} with c_B = [3, 5]. Using the new , the row solve yields \pi = [7/3, 1/3]. Reduced costs for nonbasics s_1, s_2: \bar{c}_{s_1} = 0 - [7/3, 1/3] \begin{bmatrix} 1 \\ 0 \end{bmatrix} = -7/3 < 0; \bar{c}_{s_2} = 0 - [7/3, 1/3] \begin{bmatrix} 0 \\ 1 \end{bmatrix} = -1/3 < 0. No positive reduced costs remain, confirming optimality. The optimal solution is x_1 = 2, x_2 = 1, s_1 = 0, s_2 = 0 with value 11; the optimal values are \pi = [7/3, 1/3].

Practical Challenges

Degeneracy Resolution

In the simplex method, including its revised variant, degeneracy occurs when a has one or more basic variables equal to zero, meaning multiple bases correspond to the same of the feasible . This condition arises due to linear dependencies among the coefficients, leading to non-unique representations of extreme points. Degenerate solutions can result in pivot operations that produce zero-step changes, where the basic solution and objective value remain unchanged despite a basis update. Such zero-step pivots risk causing the algorithm to cycle indefinitely through a finite set of degenerate bases without progressing toward optimality, a first demonstrated theoretically in using an artificial example. , though rare in practice, violates the finite termination guarantee of the simplex method unless preventive measures are taken. To resolve degeneracy and ensure algorithm finiteness, Bland's rule selects the entering variable as the eligible nonbasic variable (negative ) with the smallest index and the leaving variable as the basic variable with the smallest index among those tied for the minimum ratio in the . This lexicographic-like indexing prevents revisiting prior bases, guaranteeing termination in at most as many steps as there are possible bases. The perturbation method, originally proposed by Charnes, addresses degeneracy by symbolically adding diminishing positive perturbations (e.g., ε, ε², ..., ε^m for m constraints) to the right-hand side vector b, transforming the problem into a nondegenerate one where all basic variables are strictly positive. The simplex method is then applied to this perturbed instance, avoiding zero-steps and ; the original solution is obtained by taking the limit as ε approaches zero, preserving exactness for rational data. An equivalent symbolic approach is lexicographic ordering, which resolves ties in the minimum by treating the updated basic solution as a and selecting the leaving variable that yields the lexicographically smallest nonnegative among candidates. This method mimics the effect of perturbations without introducing symbolic parameters, ensuring strict progress in the ordering and finite termination. In the revised simplex method, these resolution techniques primarily affect pivot selection during the , requiring tie-breaking rules to identify valid entering and leaving variables while the underlying factorization of the basis remains updated via standard product-form or full updates regardless of degeneracy. This separation allows efficient computation of search directions and step lengths without altering the core mechanics, though degenerate steps may temporarily stall improvement until a nondegenerate is found.

Basis Representation and Stability

In the revised simplex method, the current basis is represented by the indices of the basic variables and a compact of the basis matrix B, such as an with partial , rather than the full explicit inverse B^{-1}, which is typically dense and storage-intensive even when B is sparse. This approach enables efficient computation of basic solution components, including forward and backward substitutions to solve systems like B x_B = b for the right-hand side vector b and B^{-T} \pi = c_B for dual prices \pi, with proportional to the number of nonzeros in the factors. The factors are updated at each using stable techniques, such as the Forrest-Tomlin method, which modifies the by incorporating the incoming column while preserving sparsity. Numerical stability is maintained by monitoring the condition number \kappa(B) = \|B\| \cdot \|B^{-1}\|, which quantifies the sensitivity of the solution to perturbations; values exceeding $10^{10} often signal ill-conditioning under typical floating-point tolerances of $10^{-6}. If instability is detected through metrics like growth in the factors or loss of feasibility, the basis matrix is refactorized from scratch using direct sparse LU decomposition, typically every 50 to 1000 iterations or upon threshold violation, to eliminate accumulated round-off errors. Scaling strategies further enhance stability by equilibrating coefficients to prevent disparities in magnitude—for instance, transforming a constraint like \frac{1}{3} x_1 + \frac{2}{3} x_2 = 1 (with \kappa \approx 8 \times 10^6) to x_1 + 2 x_2 = 3 (with \kappa = 8), thereby reducing error propagation in updates. For practical implementations, especially in sparse linear programs, the basis representation leverages data structures like column lists to store only the nonzero entries of the selected columns forming B, minimizing usage to O(m^2 + n + \mathrm{nz}(A)) where m is the number of , n the variables, and \mathrm{nz}(A) the nonzeros in A. This column-oriented format facilitates sparsity exploitation during pricing and ratio tests, with operations like matrix-vector multiplications performed in O(\mathrm{nz}(A)) time via linear lists of indices. In hyper-sparse problems, where over 60% of intermediate vectors in basis operations have at most 10% nonzeros, optimized traversal of these lists—such as selective file updates—yields significant speedups while preserving through integrated .