[jira] [Created] (MATH-1674) SimplexSolver incorrectly throws NoFeasibleSolutionException after valid translation of feasible problem

["Li Qu (Jira)" <ji...@apache.org>]

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)