[
https://issues.apache.org/jira/browse/MATH-1549?focusedWorklogId=460032&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-460032
]
ASF GitHub Bot logged work on MATH-1549:
----------------------------------------
Author: ASF GitHub Bot
Created on: 17/Jul/20 01:00
Start Date: 17/Jul/20 01:00
Worklog Time Spent: 10m
Work Description: mohrezaei opened a new pull request #155:
URL: https://github.com/apache/commons-math/pull/155
I looked at MATH-1549 and the core issue is deep inside the algorithm.
Basically, it's just doing division and subtraction (see
`SimplexTableau.performRowOperations`). That set of operations amplifies small
differences and starting with larger constants will cause problems in a matrix
that's also filled with 1's and -1's. Part of the problem comes from the fact
that floating point multiplication + division does not produce the same result:
```java
double d = 10.0/3.0;
double scale = 100.0;
System.out.println("Diff: "+(d - d * scale / scale)); // prints non-zero
```
The other part of the problem is that the epsilon parameter is not used to
look at the convergence of the solution (alone), but also some internal
computations. That makes reasoning about epsilon very hard.
The proposed solution scales all constants linearly to be closer to 1 by
using double exponent changes to avoid any bit errors.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
Issue Time Tracking
-------------------
Worklog Id: (was: 460032)
Remaining Estimate: 0h
Time Spent: 10m
> Simplex solver report unbounded solution when solvable constraints scaling up
> -----------------------------------------------------------------------------
>
> Key: MATH-1549
> URL: https://issues.apache.org/jira/browse/MATH-1549
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.6.1
> Environment: macOS catalina
> Reporter: Fan Zhang
> Priority: Major
> Attachments: CommonsMathSimplexSolverTest.java
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> *scenario 1:*
> {code:java}
> min: x + y
> x, y >= 0
> 9000x + y >= 0
> 10000x + y >= 2000
> x >= 2{code}
> *scenario 2:*
> {code:java}
> min: x + y
> x, y >= 0
> 9.0E15x + 1.0E12y >= 0
> 1.1e16x + 1.0e12y >= 2.0e15
> 1.0e12x >= 2e12{code}
> for scenario 1, it works out. but for scenario 2 whose constrains are just
> scaled up by 1e12, the solver reports unbounded solution.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
