Li Qu created MATH-1674:
---------------------------
Summary: 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
Environment: * Java version: Java 8
* Platform: Windows
Reporter: Li Qu
Attachments: TestSimplexSolver-1.java
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)
