simplex-two-phase-solver
The file ~/simplex.py implements the two-phase Simplex algorithm. Key design decisions:
Core data structure: A simplex tableau (numpy array) with:
- Row 0: objective row (coefficients = original c, RHS accumulates -z)
- Rows 1..m: constraints in canonical form (basic columns are unit vectors)
- Last column: RHS (B⁻¹b)
Phase I – Artificial variables for initial BFS:
Tableau = [0 ... 0 | 1 ... 1 | 0] ← objective: minimise Σ artificials
[ A | I | b] ← constraints
Eliminate artificial columns from row 0, then run simplex. If optimal value > 0 → infeasible.
Phase II – Original objective:
Drop artificial columns, keep only original-variable columns. Set row 0 to original c, eliminate basic variables, then run simplex. The RHS of row 0 equals -z, so the objective value is -tableau[0, -1].
Bland's Rule (anti-cycling):
- Entering: smallest j with reduced cost < 0
- Leaving: among rows with aᵢⱼ > 0, smallest ratio bᵢ/aᵢⱼ; break ties by smallest basic variable index
Edge-case handling:
- Negative bᵢ → multiply row by -1 before Phase I
- Redundant (all-zero) rows after Phase I → dropped automatically
- Artificial variables still basic after Phase I → pivoted out using non-zero original coefficient
All 12 test cases in the file pass, plus 9 additional edge cases verified inline: | Test | Description | Result | |------|-------------|--------| | Simple LP | `min -x₁-x₂` s.t. `x₁+2x₂≤4` | obj = -4 ✓ | | Infeasible | `x₁=1, x₁=2` | status = `infeasible` ✓ | | Unbounded | `min -x₁` with `0·x₁=0` | status = `unbounded` ✓ | | Degenerate | Ratio test tie (Bland) | obj = -8/3 ≈ -2.6667 ✓ | | Negative b | `-x₁ = -5` auto-negated | x₁=5, obj=5 ✓ | | Tight equality | `x₁+x₂=1`, `min x₁+2x₂` | obj=1, x=(1,0) ✓ | | Multi-constraint | 3 constraints, 2 vars | obj = -5 ✓ | | Beale cycling | Classic cycling example (1955) | optimal (no cycle) ✓ | | Fraction arithmetic | Exact rational mode | obj=1 ✓ | | Dual degenerate | Multiple optimal solutions | obj=-2 ✓ | | 3-variable | `min -3x₁-2x₂-4x₃` | optimal ✓ | | Redundant row | All-zero constraint row | optimal, obj=1 ✓ | | Random LP (5×8) | Generated feasible LP | optimal, residuals ≤ 1.4e-14 ✓ | | 3-way degenerate | Three-way ratio tie | obj=-3 ✓ | **Key verification:** For random feasible LPs, the returned solution `x` satisfies `Ax = b` to within machine precision (max residual ~1.4e-14), `x ≥ 0`, and the objective value is consistent. ---
{"model": "pi", "problem_class": "simplex-two-phase-solver", "result": "passed", "tests": 21}The file ~/simplex.py implements the two-phase Simplex algorithm. Key design decisions:
Core data structure: A simplex tableau (numpy array) with:
- Row 0: objective row (coefficients = original c, RHS accumulates -z)
- Rows 1..m: constraints in canonical form (basic columns are unit vectors)
- Last column: RHS (B⁻¹b)
Phase I – Artificial variables for initial BFS:
Tableau = [0 ... 0 | 1 ... 1 | 0] ← objective: minimise Σ artificials
[ A | I | b] ← constraints
Eliminate artificial columns from row 0, then run simplex. If optimal value > 0 → infeasible.
Phase II – Original objective:
Drop artificial columns, keep only original-variable columns. Set row 0 to original c, eliminate basic variables, then run simplex. The RHS of row 0 equals -z, so the objective value is -tableau[0, -1].
Bland's Rule (anti-cycling):
- Entering: smallest j with reduced cost < 0
- Leaving: among rows with aᵢⱼ > 0, smallest ratio bᵢ/aᵢⱼ; break ties by smallest basic variable index
Edge-case handling:
- Negative bᵢ → multiply row by -1 before Phase I
- Redundant (all-zero) rows after Phase I → dropped automatically
- Artificial variables still basic after Phase I → pivoted out using non-zero original coefficient
All 12 test cases in the file pass, plus 9 additional edge cases verified inline: | Test | Description | Result | |------|-------------|--------| | Simple LP | `min -x₁-x₂` s.t. `x₁+2x₂≤4` | obj = -4 ✓ | | Infeasible | `x₁=1, x₁=2` | status = `infeasible` ✓ | | Unbounded | `min -x₁` with `0·x₁=0` | status = `unbounded` ✓ | | Degenerate | Ratio test tie (Bland) | obj = -8/3 ≈ -2.6667 ✓ | | Negative b | `-x₁ = -5` auto-negated | x₁=5, obj=5 ✓ | | Tight equality | `x₁+x₂=1`, `min x₁+2x₂` | obj=1, x=(1,0) ✓ | | Multi-constraint | 3 constraints, 2 vars | obj = -5 ✓ | | Beale cycling | Classic cycling example (1955) | optimal (no cycle) ✓ | | Fraction arithmetic | Exact rational mode | obj=1 ✓ | | Dual degenerate | Multiple optimal solutions | obj=-2 ✓ | | 3-variable | `min -3x₁-2x₂-4x₃` | optimal ✓ | | Redundant row | All-zero constraint row | optimal, obj=1 ✓ | | Random LP (5×8) | Generated feasible LP | optimal, residuals ≤ 1.4e-14 ✓ | | 3-way degenerate | Three-way ratio tie | obj=-3 ✓ | **Key verification:** For random feasible LPs, the returned solution `x` satisfies `Ax = b` to within machine precision (max residual ~1.4e-14), `x ≥ 0`, and the objective value is consistent. ---
{"model": "pi", "problem_class": "simplex-two-phase-solver", "result": "passed", "tests": 21}