You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Andrea (JIRA)" <ji...@apache.org> on 2009/09/09 16:08:57 UTC
[jira] Created: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Matrix's "OutOfBoundException" in SimplexSolver
-----------------------------------------------
Key: MATH-293
URL: https://issues.apache.org/jira/browse/MATH-293
Project: Commons Math
Issue Type: Bug
Affects Versions: Nightly Builds
Environment: java 1.6 on Windows XP 32-Bit
Reporter: Andrea
Hi all,
This bug is somehow related to incident MATH-286, but not necessarily...
Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
* the only point in the feasible region for the second LP is the solution returned for the first LP
* the solution returned for the first LP is also the (only possible) solution to the second LP
This shows the problem:
{code:borderStyle=solid}
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
constraints = new ArrayList<LinearConstraint>();
constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
{code}
Instead of returning the solution, SimplexSolver throws an Exception:
{noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz updated MATH-293:
-----------------------------
Fix Version/s: 2.1
Affects Version/s: 2.0
(was: Nightly Builds)
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 2.0
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
> Fix For: 2.1
>
> Attachments: SimplexSolverTest.patch, SimplexTableau.patch
>
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: https://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Resolved: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-293.
--------------------------------
Resolution: Fixed
patch applied in subversion repository as of r813301
thanks to Andrea and Ben
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: Nightly Builds
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
> Attachments: SimplexSolverTest.patch, SimplexTableau.patch
>
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phil Steitz closed MATH-293.
----------------------------
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 2.0
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
> Fix For: 2.1
>
> Attachments: SimplexSolverTest.patch, SimplexTableau.patch
>
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: https://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Andrea (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12753213#action_12753213 ]
Andrea commented on MATH-293:
-----------------------------
Hi Ben,
Just to be clear, the first LP is solved correctly with the following solution:
Value: 40.57142857142857
x0: 15.714285714285714
x1: 0.0
x2: 14.285714285714286
x3: 0.0
x4: 0.0
x5: 30.0
Then I create new constraints that are satisfied by the solution here above:
c3: 0.8 * x0 + 0.2 * x1 >= 0.8 * 15.714285714285714 ( = 12.571428571428571)
c4: 0.7 * x2 + 0.3 * x3 >= 0.7 * 14.285714285714286 ( = 10.0)
c5: 0.4 * x4 + 0.6 * x5 >= 0.6 * 30.0 ( = 18.0)
Note that by its construction, the solution above satisfies the constraints c3, c4, and c5.
If I try to solve the new LP, a "OutOfBoundException" is thrown...
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: Nightly Builds
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Benjamin McCann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12753207#action_12753207 ]
Benjamin McCann commented on MATH-293:
--------------------------------------
Here's the standard LP description of the problem:
max .8 x0 + .2 x1 + .7 x2 + .3 x3 + .4 x4 + .6 x5
s.t.
x0 + x2 + x4 = 30
x1 + x3 + x5 = 30
.8 x0 + .2 x1 >= 10
.7 x2 + .3 x3 >= 10
.4 x4 + .6 x5 >= 10
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: Nightly Builds
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-293) Matrix's "OutOfBoundException" in
SimplexSolver
Posted by "Benjamin McCann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-293?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Benjamin McCann updated MATH-293:
---------------------------------
Attachment: SimplexSolverTest.patch
SimplexTableau.patch
Thanks for the bug report Andrea. I was expecting this problem when I submitted the patch for MATH-286, but didn't have a good test case to work against and verify the fix. This is largely what I was thinking of when I mentioned we should test some more, but didn't think you'd beat me to it in finding a good example to work off of :o) When I changed the columns being dropped in the patch for MATH-286 it meant there wasn't always a way to always tell which variable each column of the tableau represented. This patch creates a mapping between column index and variable label so that when we can read the final solution out of the tableau. I feel much better about this now. Thanks!
> Matrix's "OutOfBoundException" in SimplexSolver
> -----------------------------------------------
>
> Key: MATH-293
> URL: https://issues.apache.org/jira/browse/MATH-293
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: Nightly Builds
> Environment: java 1.6 on Windows XP 32-Bit
> Reporter: Andrea
> Attachments: SimplexSolverTest.patch, SimplexTableau.patch
>
>
> Hi all,
> This bug is somehow related to incident MATH-286, but not necessarily...
> Let's say I have an LP and I solve it using SimplexSolver. Then I create a second LP similar to the first one, but with "stronger" constraints. The second LP has the following properties:
> * the only point in the feasible region for the second LP is the solution returned for the first LP
> * the solution returned for the first LP is also the (only possible) solution to the second LP
> This shows the problem:
> {code:borderStyle=solid}
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, 10.0));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, 10.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> double valA = 0.8 * solution.getPoint()[0] + 0.2 * solution.getPoint()[1];
> double valB = 0.7 * solution.getPoint()[2] + 0.3 * solution.getPoint()[3];
> double valC = 0.4 * solution.getPoint()[4] + 0.6 * solution.getPoint()[5];
> f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ, 30.0));
> constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 }, Relationship.GEQ, valA));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 }, Relationship.GEQ, valB));
> constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 }, Relationship.GEQ, valC));
> solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE, true);
> {code}
> Instead of returning the solution, SimplexSolver throws an Exception:
> {noformat} Exception in thread "main" org.apache.commons.math.linear.MatrixIndexException: no entry at indices (0, 7) in a 6x7 matrix
> at org.apache.commons.math.linear.Array2DRowRealMatrix.getEntry(Array2DRowRealMatrix.java:356)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getEntry(SimplexTableau.java:408)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getBasicRow(SimplexTableau.java:258)
> at org.apache.commons.math.optimization.linear.SimplexTableau.getSolution(SimplexTableau.java:336)
> at org.apache.commons.math.optimization.linear.SimplexSolver.doOptimize(SimplexSolver.java:182)
> at org.apache.commons.math.optimization.linear.AbstractLinearOptimizer.optimize(AbstractLinearOptimizer.java:106){noformat}
> I was too optimistic with the bug MATH-286 ;-)
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.