commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benjamin McCann (JIRA)" <j...@apache.org>
Subject [jira] Updated: (MATH-286) SimplexSolver not working as expected?
Date Wed, 09 Sep 2009 01:55:57 GMT

     [ https://issues.apache.org/jira/browse/MATH-286?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Benjamin McCann updated MATH-286:
---------------------------------

    Attachment: patch.zip

Here's a patch that correctly solves the problem Andrea posted (sorry for not completely fixing
the problem with my earlier patches.)  It's mostly refactoring to make the solution easier,
which was to drop positive cost non-artificial variables and nonbasic artificial variables
at the end of phase 1 instead of all artificial variables.
There are some practical problems with degeneracy and redundant constraints that were not
obvious to me from the theory when I first started working on this.  We should really test
this a bit more with constraints outnumbering variables and redundant constraints to really
be comfortable that all the issues are addressed, but we're certainly pretty close now if
not there yet.
Andrea, thanks for the reports and validating fixes (or lack there of).  Luc, thanks for quickly
getting these into SVN and letting me know about the problems.

> SimplexSolver not working as expected?
> --------------------------------------
>
>                 Key: MATH-286
>                 URL: https://issues.apache.org/jira/browse/MATH-286
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.0
>         Environment: Java 1.6.0_13 on  Windows XP 32-bit
>            Reporter: Andrea
>             Fix For: 2.1
>
>         Attachments: patch.zip, simplex.txt, SimplexSolver.patch, SimplexSolverTest.patch,
SimplexSolverTest.patch, SimplexTableau.patch, SimplexTableau.patch
>
>
> I guess (but I could be wrong) that SimplexSolver does not always return the optimal
solution, nor satisfies all the constraints...
> Consider this LP:
> max: 0.8 x0 + 0.2 x1 + 0.7 x2 + 0.3 x3 + 0.6 x4 + 0.4 x5;
> r1: x0 + x2 + x4 = 23.0;
> r2: x1 + x3 + x5 = 23.0;
> r3: x0 >= 10.0;
> r4: x2 >= 8.0;
> r5: x4 >= 5.0;
> LPSolve returns 25.8, with x0 = 10.0, x1 = 0.0, x2 = 8.0, x3 = 0.0, x4 = 5.0, x5 = 23.0;
> The same LP expressed in Apache commons math is:
> LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7,
0.3, 0.6, 0.4 }, 0 );
> Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
> constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ,
23.0));
> constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ,
23.0));
> constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0, 0, 0 }, Relationship.GEQ,
10.0));
> constraints.add(new LinearConstraint(new double[] { 0, 0, 1, 0, 0, 0 }, Relationship.GEQ,
8.0));
> constraints.add(new LinearConstraint(new double[] { 0, 0, 0, 0, 1, 0 }, Relationship.GEQ,
5.0));
> RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MAXIMIZE,
true);
> that returns 22.20, with x0 = 15.0, x1 = 23.0, x2 = 8.0, x3 = 0.0, x4 = 0.0, x5 = 0.0;
> Is it possible SimplexSolver is buggy that way? The returned value is 22.20 instead of
25.8, and the last constraint (x4 >= 5.0) is not satisfied...
> Am I using the interface wrongly?

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message