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

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

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

Li Qu edited comment on MATH-1674 at 5/12/25 9:33 AM:
------------------------------------------------------

Thanks for the response.

As requested, I've attached a new patch that adds a regression test for the issue.


was (Author: JIRAUSER309523):
Thanks for the request.

As requested, I’ve attached a new patch that adds a regression test for the issue.

> 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: MATH-1674.patch, 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)