QuantEcon / QuantEcon.py / 34295292025

94%

Build Type

push

github

Committed by web-flow

Commit Message

FIX: Pivoting routines: Report numerical breakdown correctly (#949)

* FIX: Do not report an unresolved lexicographic tie as "not found"

`_lex_min_ratio_test` returned `found=False` both when the pivot column
has no positive entry and when the lexicographic tie breaking failed to
single out one row among the candidates of the ratio test. The caller
`solve_tableau` treats `found=False` as "unbounded", so the second case
was reported as unbounded although the pivot column does have positive
entries. It arises when the tableau entries are large relative to the
absolute tolerance `tol_ratio_diff`, e.g. for `A_ub = [[1e14], [1e14]]`,
where the ratios in all columns tie within the tolerance.

Now `found` is True whenever the first pass finds a candidate, and if the
tie breaking leaves several rows, which are then indistinguishable within
`tol_ratio_diff`, the first of them is taken.

Add tests: a unit test of `_lex_min_ratio_test` and the linprog_simplex
example above. Add the analogous Lemke-Howson example (payoffs scaled by
1e16) as an expected failure: it also requires the tolerance to be
scale-aware, which is left for later.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>

* FIX: lemke_howson: Stop with converged=False on numerical breakdown

`_lemke_howson_tbl` ignored the `found` flag of `_lex_min_ratio_test`
and, when the pivot column had no positive entry (up to `tol_piv`),
pivoted on a meaningless row and could return a wrong "equilibrium" with
`converged=True`. This cannot happen in exact arithmetic, and is a
numerical breakdown; now the pivoting stops and `converged=False` is
returned, so that the capping loop moves on to the next initial pivot.

Add a test of the breakdown path.

Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>

* ENH: _lex_min_ratio_test: Report whether the tie was resolved

Return a third value `resolved`: True if the row returned is the unique
lexico-minimum row, False if no candidate was found or if the
le... (continued)

Coverage Stats

83 of 85 new or added lines in 6 files covered. (97.65%)

6 existing lines in 2 files now uncovered.

5294 of 5828 relevant lines covered (90.84%)

0.91 hits per line