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

["Gilles Sadowski (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/MATH-1674?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17948630#comment-17948630 ] 

Gilles Sadowski commented on MATH-1674:
---------------------------------------

Thanks for the report.

Could you please provide a patch wrt the [corresponding file|https://github.com/apache/commons-math/blob/master/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/optim/linear/SimplexSolverTest.java] in the Junit test suite (defining the new test method with a name[1] such as  {{testMath1674}})?

The failing case should be "isolated"; i.e. rather than loop over thousands of tests (that pass), the unit test should contain the one test that fails.  The coefficients, for example, should be hard-coded in the source file[2] rather than depend on being arrived at through a generated sequence of numbers.[3]

Minor nit-pick (but helpful for reviewers): Please declare variables "final" (wherever possible).

[1] Alternatively, you could keep {{testMetamorphicTranslationInvariant}}, if a (code) comment contains this report's identifier ("MATH-1674").
[2] Or read from a simple text "resource" file (see examples of this in the non-linear optimization [resource directory|https://github.com/apache/commons-math/tree/master/commons-math-legacy/src/test/resources/org/apache/commons/math4/legacy/optim/nonlinear/scalar/noderiv]).
[3] A sequence that is obviously tied to a specific pseudo-random number generator.

> 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)