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] Commented: (MATH-302) Bugs in Simplex Implementation
Date Wed, 14 Oct 2009 20:18:31 GMT

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

Benjamin McCann commented on MATH-302:
--------------------------------------

These are likely bugs that have already been fixed in the Subversion repository.  Can you
try again with the latest version compiled from SVN?

I've verified that the first problem gives valid output with the SVN version:
Constraints:
{1; 1; 0; 0; 0; 0; 0} = 1.0
{0; 0; 1; 1; 1; 0; 0} = 1.0
{0; 0; 0; 0; 0; 1; 1} = 1.0
{0.54; 0; 0.34; 0; 0; 0.12; 0} = 0.54
{0; 0.54; 0; 0.34; 0; 0; 0.12} = 0.34
Solution:
{0.37; 0.63; 0.65; 0; 0.35; 1; 0}


I haven't completely checked the second one, but it appears to be correct as well with the
SVN version:
Constraints:
{1; 1; 1; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0} = 1.0
{0; 0; 0; 1; 1; 1; 1; 0; 0; 0; 0; 0; 0} = 1.0
{0; 0; 0; 0; 0; 0; 0; 1; 1; 1; 0; 0; 0} = 1.0
{0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 1; 1; 1} = 1.0
{0.54; 0; 0; 0.32; 0; 0; 0; 0.1; 0; 0; 0.02; 0; 0} = 0.54
{0; 0.54; 0; 0; 0.32; 0; 0; 0; 0.1; 0; 0; 0.02; 0} = 0.32
{0; 0; 0; 0; 0; 0.32; 0; 0; 0; 0; 0; 0; 0} = 0.1
Solution:
[0.3703703703703704, 0.5925925925925926, 0.037037037037037035, 0.6875, 0.0, 0.3125, 0.0, 0.9999999999999999,
0.0, 0.0, 1.0, 0.0, 0.0]

> Bugs in Simplex Implementation
> ------------------------------
>
>                 Key: MATH-302
>                 URL: https://issues.apache.org/jira/browse/MATH-302
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.0
>            Reporter: Christian Winter
>
> Simplex routine may return infeasible solution:
> {code:title=Bug1.java|borderstyle=solid}
> import java.util.ArrayList;
> import org.apache.commons.math.linear.ArrayRealVector;
> import org.apache.commons.math.optimization.GoalType;
> import org.apache.commons.math.optimization.OptimizationException;
> import org.apache.commons.math.optimization.linear.*;
> public class Bug1 {
>     
>     public static void main(String[] args) throws OptimizationException {
>         
>         LinearObjectiveFunction c = new LinearObjectiveFunction(new double[7], 0.0d);
>         
>         ArrayList<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(5);
>         LinearConstraint cnst;
>         cnst = new LinearConstraint(new double[] {1.00d, 1.00d, 0.00d, 0.00d, 0.0d, 0.00d,
0.00d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 1.00d, 1.00d, 1.0d, 0.00d,
0.00d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.00d, 0.00d, 0.0d, 1.00d,
1.00d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.54d, 0.00d, 0.34d, 0.00d, 0.0d, 0.12d,
0.00d}, Relationship.EQ, 0.54d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.54d, 0.00d, 0.34d, 0.0d, 0.00d,
0.12d}, Relationship.EQ, 0.34d);
>         cnsts.add(cnst);
>         System.out.println("Constraints:");
>         for(LinearConstraint con : cnsts) {
>             System.out.println(con.getCoefficients().toString() + " " + con.getRelationship()
+ " " + con.getValue());
>         }
>         
>         SimplexSolver simplex = new SimplexSolver();
>         double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE, true).getPointRef();
>         System.out.println("Solution:\n" + new ArrayRealVector(sol));
>         System.out.println("Third constraint is violated!");
>     }
> }
> {code}
> or may find no solution where some exist:
> {code:title=Bug1.java|borderstyle=solid}
> import java.util.ArrayList;
> import org.apache.commons.math.linear.ArrayRealVector;
> import org.apache.commons.math.optimization.GoalType;
> import org.apache.commons.math.optimization.OptimizationException;
> import org.apache.commons.math.optimization.linear.*;
> public class Bug2 {
>     
>     public static void main(String[] args) throws OptimizationException {
>         
>         LinearObjectiveFunction c = new LinearObjectiveFunction(new double[13], 0.0d);
>         
>         ArrayList<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(5);
>         LinearConstraint cnst;
>         cnst = new LinearConstraint(new double[] {1.00d, 1.00d, 1.0d, 0.00d, 0.00d, 0.00d,
0.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 1.00d, 1.00d, 1.00d,
1.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.00d,
0.0d, 1.0d, 1.0d, 1.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.00d,
0.0d, 0.0d, 0.0d, 0.0d, 1.00d, 1.00d, 1.0d}, Relationship.EQ, 1.0d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.54d, 0.00d, 0.0d, 0.32d, 0.00d, 0.00d,
0.0d, 0.1d, 0.0d, 0.0d, 0.02d, 0.00d, 0.0d}, Relationship.EQ, 0.54d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.54d, 0.0d, 0.00d, 0.32d, 0.00d,
0.0d, 0.0d, 0.1d, 0.0d, 0.00d, 0.02d, 0.0d}, Relationship.EQ, 0.32d);
>         cnsts.add(cnst);
>         cnst = new LinearConstraint(new double[] {0.00d, 0.00d, 0.0d, 0.00d, 0.00d, 0.32d,
0.0d, 0.0d, 0.0d, 0.0d, 0.00d, 0.00d, 0.0d}, Relationship.EQ, 0.1d);
>         cnsts.add(cnst);
>         System.out.println("Constraints:");
>         for(LinearConstraint con : cnsts) {
>             System.out.println(con.getCoefficients().toString() + " " + con.getRelationship()
+ " " + con.getValue());
>         }
>         
>         System.out.println("verifying a known solution:");
>         ArrayRealVector sol = new ArrayRealVector(new double[] {4.0d/9.0d, 5.0d/9.0d,
0.0d, 11.0d/16.0d, 0.0d, 5.0d/16.0d, 0.0d, 4.0d/5.0d, 0.0d, 1.0d/5.0d, 0.0d, 1.0d, 0.0d});
>         System.out.println("sol = " + sol);
>         for(LinearConstraint con : cnsts) {
>             System.out.println(sol.dotProduct(con.getCoefficients()) + " = " + con.getValue());
>         }
>         
>         SimplexSolver simplex = new SimplexSolver();
>         double[] newsol = simplex.optimize(c, cnsts, GoalType.MINIMIZE, true).getPointRef();
>         System.out.println("Solution:\n" + new ArrayRealVector(newsol));
>     }
> }
> {code}

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