FA-12011 / Optimization solver contracts / Open access
Simplex leaving row includes nonlimiting coefficients · case 01
Simplex leaving row includes nonlimiting coefficients.
ROOT CAUSE
Ratio selection includes negative pivot column coefficients.
VERIFIED REPAIR
Consider strictly positive coefficients, compare exact ratios, and break ratio ties by smallest basis index.
Unsuccessful approach: Filtering negative coefficients fixes feasibility but row-order tie breaking violates the stated anti-cycling rule.
Case contract
Given finite Python integer/float nonnegative RHS values and nonzero pivot coefficients, return basis index of the minimum exact represented rhs/coefficient over positive coefficients; tie by smallest basis index; None means unbounded.
Why this case matters
This deterministic solver-step model isolates an algorithmic invariant used by iterative optimization implementations.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
N = 1
observations = []
def solve(rows):
return min(rows, key=lambda r:r[1]/r[2])[0] if rows else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('negative coefficient', solve([(1,N,-1),(2,2*N,1)]), 2)
check('basis tie', solve([(8,2*N,2),(3,N,1)]), 3)
check('strict minimum', solve([(8,3*N,1),(3,N,1)]), 3)
check('unbounded', solve([(1,N,-1)]), None)
check('degenerate tie', solve([(9,0,1),(2,0,2)]), 2)
check('empty tableau', solve([]), None)
check('nearby large ratios remain distinct', solve([(0,2**54+N,1),(1,2**54+N-1,1)]), 1)
check('tiny positive ratio remains distinct from zero', solve([(0,1e-300,1e300),(1,0,1)]), 1)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| negative coefficient | 1 | 2 | Failed |
| basis tie | 8 | 3 | Failed |
| strict minimum | 3 | 3 | Passed |
| unbounded | 1 | None | Failed |
| degenerate tie | 9 | 2 | Failed |
| empty tableau | None | None | Passed |
| nearby large ratios remain distinct | 0 | 1 | Failed |
| tiny positive ratio remains distinct from zero | 0 | 1 | Failed |
SHA-256 / 4d05b2227608cdef524f363e2cad2b585702668bb0a54ca50f5a0f655abba482
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
N = 1
observations = []
def solve(rows):
eligible=[r for r in rows if r[2]>0]
return min(eligible,key=lambda r:r[1]/r[2])[0] if eligible else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('negative coefficient', solve([(1,N,-1),(2,2*N,1)]), 2)
check('basis tie', solve([(8,2*N,2),(3,N,1)]), 3)
check('strict minimum', solve([(8,3*N,1),(3,N,1)]), 3)
check('unbounded', solve([(1,N,-1)]), None)
check('degenerate tie', solve([(9,0,1),(2,0,2)]), 2)
check('empty tableau', solve([]), None)
check('nearby large ratios remain distinct', solve([(0,2**54+N,1),(1,2**54+N-1,1)]), 1)
check('tiny positive ratio remains distinct from zero', solve([(0,1e-300,1e300),(1,0,1)]), 1)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| negative coefficient | 2 | 2 | Passed |
| basis tie | 8 | 3 | Failed |
| strict minimum | 3 | 3 | Passed |
| unbounded | None | None | Passed |
| degenerate tie | 9 | 2 | Failed |
| empty tableau | None | None | Passed |
| nearby large ratios remain distinct | 0 | 1 | Failed |
| tiny positive ratio remains distinct from zero | 0 | 1 | Failed |
SHA-256 / 0575b96bf1a5f90dd9b0f1e169ed175e3e33891e0f6e274358b244144df621ed
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
N = 1
observations = []
def solve(rows):
eligible=[r for r in rows if r[2]>0]
return min(eligible,key=lambda r:(Fraction(r[1])/Fraction(r[2]),r[0]))[0] if eligible else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('negative coefficient', solve([(1,N,-1),(2,2*N,1)]), 2)
check('basis tie', solve([(8,2*N,2),(3,N,1)]), 3)
check('strict minimum', solve([(8,3*N,1),(3,N,1)]), 3)
check('unbounded', solve([(1,N,-1)]), None)
check('degenerate tie', solve([(9,0,1),(2,0,2)]), 2)
check('empty tableau', solve([]), None)
check('nearby large ratios remain distinct', solve([(0,2**54+N,1),(1,2**54+N-1,1)]), 1)
check('tiny positive ratio remains distinct from zero', solve([(0,1e-300,1e300),(1,0,1)]), 1)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| negative coefficient | 2 | 2 | Passed |
| basis tie | 3 | 3 | Passed |
| strict minimum | 3 | 3 | Passed |
| unbounded | None | None | Passed |
| degenerate tie | 2 | 2 | Passed |
| empty tableau | None | None | Passed |
| nearby large ratios remain distinct | 1 | 1 | Passed |
| tiny positive ratio remains distinct from zero | 1 | 1 | Passed |
SHA-256 / 3608f4163263db28d8fcd6b75606a762b9f77febfc11c84d6eb7d91b0aacd9b5
Verification & scope
Controlled finite inputs and explicit one-step contracts; this is not a production solver or a numerical stability benchmark. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:38:53.035301+00:00.
Case digest / 329fb6d8f832052f33739ff71df6e7b2f7fb25a0ed390f36e629e848711ea147