[
https://issues.apache.org/jira/browse/MATH-1674?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17951353#comment-17951353
]
Gilles Sadowski commented on MATH-1674:
---------------------------------------
bq. it feels somewhat counterintuitive that two equivalent sets of constraints
and objectives would require manual adjustment of tolerance settings to produce
identical feasibility results.
AFAICT, your unit test does not expect them to be _identical_ since it sets a
relatively lax tolerance (1e-4).
bq. adaptive tolerance mechanism [...] would indeed be a better solution.
You could contribute an analysis about how a sequence of transformations
(expressed in parametric form) impacts the accuracy ("equality") of the result
(and the tolerance required to avoid the observed failure).
Then maybe, it'll give you hints on how to devise an automated scaling
procedure...
> SimplexSolver incorrectly throws NoFeasibleSolutionException after valid
> translation of feasible problem
> --------------------------------------------------------------------------------------------------------
>
> Key: MATH-1674
> URL: https://issues.apache.org/jira/browse/MATH-1674
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 4.0-beta1
> Environment: * Java version: Java 8
> * Platform: Windows
> Reporter: Li Qu
> Priority: Major
> Attachments: MATH-1674.patch, reproduction.patch
>
>
> During metamorphic testing of the {{{}SimplexSolver{}}}, we observed that
> translating a feasible linear programming problem by a random vector
> occasionally causes the solver to throw a
> {{{}NoFeasibleSolutionException{}}}, even though the transformed problem
> remains theoretically feasible.
> In particular, the test is as follows:
> * A feasible LP problem is randomly generated, ensuring that a known
> feasible point {{x₀}} satisfies all constraints.
> * The problem is shifted via a variable transformation {{{}x' = x + d{}}},
> where {{d}} is a random vector.
> * Constraints are adjusted accordingly: each constraint {{A x <= b}} is
> transformed to {{{}A x' <= b + A d{}}}.
> * The original and transformed problems are solved independently.
> *Expected behavior:*
> Since {{x₀}} is feasible for the original problem, {{x₀ + d}} should be
> feasible for the shifted problem. Therefore, the shifted problem should
> always have a feasible solution.
> *Actual behavior:*
> After ~2700 random tests, in some cases, solving the shifted problem results
> in a {{{}NoFeasibleSolutionException{}}}. This suggests that
> {{SimplexSolver}} may have issues handling feasible translated problems,
> potentially due to numerical instability or bugs during the Phase 1 process.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
