Overview
The revised simplex method keeps the current basis and computes entering and leaving variables from matrix solves with that basis. It avoids explicitly maintaining the full simplex tableau.
CoreSource checked
Revised Simplex Method
Solves linear programs by updating a compact basis representation instead of a full tableau.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Linear Programming
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
linear programmingdynamic programmingoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when a linear program can be represented with a manageable basis matrix.
- Use when tableau storage is too expensive but simplex-style pivots are desired.
When Not to Use
- Avoid when the model is nonlinear or has nonconvex constraints.
- Avoid when degeneracy and numerical conditioning require a more robust solver strategy than the implementation provides.
What It Does
- Maintains a feasible basis
- Computes reduced costs for candidate entering variables
- Pivots by replacing one basis variable at a time
Use Cases
- Large sparse linear programs
- Industrial simplex implementations
- Teaching basis-oriented linear programming
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Pseudocode
- 1.Start from an initial feasible basis
- 2.Solve with the basis matrix to compute reduced costs
- 3.Choose an entering variable with improving reduced cost
- 4.Run the ratio test to choose a leaving variable
- 5.Pivot the basis and update its factorization
- 6.Stop when no reduced cost can improve the objective
Canonical Example
- Input
- maximize 3x + 2y subject to x + y <= 4, x <= 2, y <= 3
- Output
- basis pivots toward x = 2, y = 2 with objective 10
- Explanation
- Each pivot changes the active constraint basis while preserving feasibility.
Implementation Notes
- Separate basis factorization from pricing and ratio-test logic.
- Use tolerances for feasibility and reduced-cost comparisons.
- Test infeasible, unbounded, degenerate, and optimal cases.
Common Pitfalls
- Ignoring degeneracy can cause cycling without an anti-cycling rule.
- Basis factorizations must be updated or recomputed carefully.
- Poor scaling can make reduced costs and pivot tests unreliable.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow updating a basis representation instead of the full simplex tableau on a small linear programming example.
Step 1 of 6: Start from an initial feasible basis
optimization-mechanismNotes
Numerical tolerances and anti-cycling rules are part of a practical revised simplex implementation.
Sources (2)
What each reference supports for this entry.
Linear Programming and Extensions
BookClassic reference for simplex and revised simplex linear-programming methods.
The Algorithm Design Manual
BookAlgorithm catalog support for Revised Simplex Method's problem context, known alternatives, and practical selection tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toKarmarkar's Algorithm
Optimization · Core
Revised Simplex Method and Karmarkar's Algorithm solve related linear programming problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toKarmarkar's Algorithm
Revised Simplex Method and Karmarkar's Algorithm solve related linear programming problems with different assumptions and tradeoffs.
Conceptual neighborLinear Programming Simplex Method
Revised Simplex Method and Linear Programming Simplex Method both relate to linear programming, but use different structures or assumptions.
Conceptual neighborInterior Point Method
Revised Simplex Method and Interior Point Method both relate to linear programming, but use different structures or assumptions.
Tags
Optimization