[
https://issues.apache.org/jira/browse/MATH-1674?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17951097#comment-17951097
]
Li Qu commented on MATH-1674:
-----------------------------
Sorry about placing the patch incorrectly—thanks for correcting that and
integrating the test case.
I fully understand your explanation that the root cause here relates to
numerical precision and tolerance settings. From a mathematical perspective,
however, it feels somewhat counterintuitive that two equivalent sets of
constraints and objectives would require manual adjustment of tolerance
settings to produce identical feasibility results.
As you've mentioned, an adaptive tolerance mechanism—if feasible to
implement—would indeed be a better solution.
Thanks again for your help and clarification!
> 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)
