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.
