[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart updated MATH-434:
-
Attachment: MATH-434-cleanup.patch
Thanks for accepting the patch. The comparison using maxUlps has already been
adapted according to MATH-557, but it was missing for SimplexTableau. The
cleanup patch fixes this and also renames the test names for similarity.
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Fix For: 3.0
>
> Attachments: MATH-434-cleanup.patch, MATH-434-version2.patch,
> MATH-434.patch, SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug th
[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart updated MATH-434:
-
Attachment: MATH-434-version2.patch
updated patch, incorporating comments from luc
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Fix For: 3.0
>
> Attachments: MATH-434-version2.patch, MATH-434.patch,
> SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables ca
[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart updated MATH-434:
-
Attachment: MATH-434.patch
Attached a patch for the reported problems.
The problems can be split into two groups:
- wrong solution calculation with negative
variables
- failing to select an appropriate pivot
row when values are below a given
epsilon
The patch addresses both problems:
1. fix in SimplexTableau.getSolution()
2. use BigReal for arbitrary precision
support when selecting the pivot row
Additionally, 4 test cases are included, as well as a minor typo fix for a
method name.
The fixed epsilon is also used in some other places of the code, this may also
create problems under certain circumstances. So if this patch is accepted, the
other places could also be adapted.
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Fix For: 3.0
>
> Attachments: MATH-434.patch, SimplexSolverIssues.java,
> SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
>
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Phil Steitz updated MATH-434:
-
Fix Version/s: (was: 2.2)
3.0
Pushing out to 3.0.
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Fix For: 3.0
>
> Attachments: SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables can take a given value
> // then we choose the fir
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Phil Steitz updated MATH-434:
-
Fix Version/s: 2.2
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Fix For: 2.2
>
> Attachments: SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables can take a given value
> // then we choose the first and set the rest equal to 0
> coeffici
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wayne Witzel updated MATH-434:
--
Attachment: (was: SimplexSolverIssues.out)
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Attachments: SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables can take a given value
> // then we choose the first and set the rest equal to 0
> coeffic
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wayne Witzel updated MATH-434:
--
Attachment: SimplexSolverIssues.out
SimplexSolverIssues.java
Code, and resulting output, that illustrates issues with the SimplexSolver.
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Attachments: SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables can take a
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wayne Witzel updated MATH-434:
--
Attachment: SimplexSolverIssuesOutput.txt
> SimplexSolver returns unfeasible solution
> -
>
> Key: MATH-434
> URL: https://issues.apache.org/jira/browse/MATH-434
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 2.1
>Reporter: Wayne Witzel
> Attachments: SimplexSolverIssues.java, SimplexSolverIssuesOutput.txt
>
>
> The SimplexSolver is returning an unfeasible solution:
> import java.util.ArrayList;
> import java.text.DecimalFormat;
> 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 SimplexSolverBug {
>
> public static void main(String[] args) throws OptimizationException {
>
> LinearObjectiveFunction c = new LinearObjectiveFunction(new
> double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
>
> ArrayList cnsts = new
> ArrayList(5);
> LinearConstraint cnst;
> cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d,
> 0.0d, -0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d,
> 1.0d, 1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d,
> 0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> -1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
> cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
> 1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
> cnsts.add(cnst);
>
> DecimalFormat df = new java.text.DecimalFormat("0.#E0");
>
> System.out.println("Constraints:");
> for(LinearConstraint con : cnsts) {
> for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
>
> System.out.print(df.format(con.getCoefficients().getData()[i]) + " ");
> System.out.println(con.getRelationship() + " " + con.getValue());
> }
>
> SimplexSolver simplex = new SimplexSolver(1e-7);
> double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
> false).getPointRef();
> System.out.println("Solution:\n" + new ArrayRealVector(sol));
> System.out.println("Second constraint is violated!");
> }
> }
> It's an odd problem, but something I ran across. I tracked the problem to
> the getPivotRow routine in SimplexSolver. It was choosing a pivot that
> resulted in a negative right-hand-side. I recommend a fix by replacing
> ...
> if (MathUtils.equals(ratio, minRatio, epsilon)) {
> ...
> with
> ...
> if (MathUtils.equals(ratio, minRatio,
> Math.abs(epsilon/entry))) {
> ...
> I believe this would be more appropriate (and at least resolves this
> particular problem).
> Also, you may want to consider making a change in getPivotColumn to replace
> ...
> if (MathUtils.compareTo(tableau.getEntry(0, i), minValue,
> epsilon) < 0) {
> ...
> with
> ...
> if (tableau.getEntry(0, i) < minValue)
> ...
> because I don't see the point of biasing earlier columns when multiple
> entries are within epsilon of each other. Why not pick the absolute
> smallest. I don't know that any problem can result from doing it the other
> way, but the latter may be a safer bet.
> VERY IMPORTANT: I discovered another bug that occurs when not restricting to
> non-negatives. In SimplexTableu::getSolution(),
> ...
> if (basicRows.contains(basicRow))
> // if multiple variables can take a given value
> // then we choose the first and set the rest equal to 0
> coefficients
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible solution
[
https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wayne Witzel updated MATH-434:
--
Description:
The SimplexSolver is returning an unfeasible solution:
import java.util.ArrayList;
import java.text.DecimalFormat;
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 SimplexSolverBug {
public static void main(String[] args) throws OptimizationException {
LinearObjectiveFunction c = new LinearObjectiveFunction(new
double[]{0.0d, 1.0d, 1.0d, 0.0d, 0.0d, 0.0d, 0.0d}, 0.0d);
ArrayList cnsts = new ArrayList(5);
LinearConstraint cnst;
cnst = new LinearConstraint(new double[] {1.0d, -0.1d, 0.0d, 0.0d,
0.0d, 0.0d, 0.0d}, Relationship.EQ, -0.1d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {1.0d, 0.0d, 0.0d, 0.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, -1e-18d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 1.0d, 0.0d, 0.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 1.0d, 0.0d,
-0.0128588d, 1e-5d}, Relationship.EQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 0.0d, 0.0d, 1.0d,
1e-5d, -0.0128586d}, Relationship.EQ, 1e-10d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, -1.0d,
0.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 1.0d, 0.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d,
-1.0d, 0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
cnst = new LinearConstraint(new double[] {0.0d, 0.0d, 1.0d, 0.0d, 1.0d,
0.0d, 0.0d}, Relationship.GEQ, 0.0d);
cnsts.add(cnst);
DecimalFormat df = new java.text.DecimalFormat("0.#E0");
System.out.println("Constraints:");
for(LinearConstraint con : cnsts) {
for (int i = 0; i < con.getCoefficients().getDimension(); ++i)
System.out.print(df.format(con.getCoefficients().getData()[i])
+ " ");
System.out.println(con.getRelationship() + " " + con.getValue());
}
SimplexSolver simplex = new SimplexSolver(1e-7);
double[] sol = simplex.optimize(c, cnsts, GoalType.MINIMIZE,
false).getPointRef();
System.out.println("Solution:\n" + new ArrayRealVector(sol));
System.out.println("Second constraint is violated!");
}
}
It's an odd problem, but something I ran across. I tracked the problem to the
getPivotRow routine in SimplexSolver. It was choosing a pivot that resulted in
a negative right-hand-side. I recommend a fix by replacing
...
if (MathUtils.equals(ratio, minRatio, epsilon)) {
...
with
...
if (MathUtils.equals(ratio, minRatio, Math.abs(epsilon/entry)))
{
...
I believe this would be more appropriate (and at least resolves this particular
problem).
Also, you may want to consider making a change in getPivotColumn to replace
...
if (MathUtils.compareTo(tableau.getEntry(0, i), minValue, epsilon)
< 0) {
...
with
...
if (tableau.getEntry(0, i) < minValue)
...
because I don't see the point of biasing earlier columns when multiple entries
are within epsilon of each other. Why not pick the absolute smallest. I don't
know that any problem can result from doing it the other way, but the latter
may be a safer bet.
VERY IMPORTANT: I discovered another bug that occurs when not restricting to
non-negatives. In SimplexTableu::getSolution(),
...
if (basicRows.contains(basicRow))
// if multiple variables can take a given value
// then we choose the first and set the rest equal to 0
coefficients[i] = 0;
...
should be
...
if (basicRows.contains(basicRow)) {
// if multiple variables can take a given value
// then we choose the first and set the rest equal to 0
coefficients[i] = (restrictToNonNegative ? 0 : -mostNegative);
...
If necessary, I can give an example of where this bug causes a problem, but it
should be fairly obvious why this was wrong.
was:
The SimplexSolver is returning an unfeasible solution:
import java.util.ArrayList;
import java.text.DecimalFormat;
import org.apache.commons.math.linear.
