[
https://issues.apache.org/jira/browse/MATH-1674?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Li Qu updated MATH-1674:
------------------------
Attachment: (was: TestSimplexSolver-1.java)
> 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: 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)
