You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Benjamin McCann (JIRA)" <ji...@apache.org> on 2009/10/14 22:18:31 UTC
[jira] Commented: (MATH-302) Bugs in Simplex Implementation
[ 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.