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