You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Wayne Witzel (JIRA)" <ji...@apache.org> on 2010/11/07 04:57:06 UTC
[jira] Created: (MATH-434) SimplexSolver returns unfeasible
solution
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
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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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
...
final double ratio = rhs / entry;
if (MathUtils.equals(ratio, minRatio, epsilon)) {
minRatioPositions.add(i);
} else {
...
with
...
if (MathUtils.equals(rhs, minRatio*entry, epsilon)) {
minRatioPositions.add(i);
} else {
final double ratio = rhs / entry;
...
I believe this would be more appropriate (and at least resolves this particular problem).
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] [Resolved] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Luc Maisonobe resolved MATH-434.
--------------------------------
Resolution: Fixed
Fixed in subversion repository as of r1090656.
Path applied with a very small change: adding the maxUlps parameter to the detailed constructor.
Thanks for the report and thanks for the patch.
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13015875#comment-13015875 ]
Thomas Neidhart commented on MATH-434:
--------------------------------------
hmm, I feel a bit stupid now, as I have re-implemented MathUtils.equals(double, double, int) but in a mediocre way. So all calls to getEpsilon should be replaced with the equivalent MathUtils.equals.
for the isOptimal:
the idea was to have a user-defined threshold for the convergence criteria, which defaults to the original value of 1e-6. Using the same adjusted epsilon would possibly lead to more iterations as before. As the feasibility check in SimplexSolver.solvePhase1 has to use a static epsilon for convergence reasons, I thought to use the same epsilon in isOptimal makes sense for symmetry reasons (use the same epsilon to check for convergence /feasibility).
But it's good that you raise these points, because I was hesitating myself what is the best way to go forward, as I am also not considering myself a floating-point expert. I am mainly interested in the simplex algorithm, that's why I have chosen to provide a patch for this (very nice) implementation of it.
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Wayne Witzel (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] [Commented] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13018464#comment-13018464 ]
Luc Maisonobe commented on MATH-434:
------------------------------------
Cleanup patch applied.
thanks again
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13015626#comment-13015626 ]
Thomas Neidhart commented on MATH-434:
--------------------------------------
Hi Luc,
my initial idea was to use an epsilon that is adjusted to the magnitude of the respective value used for comparison. To be honest, I was not aware of [Math,FastMath].ulp, therefore I went with BigReal/BigDecimal to circumvent the problem in another way (by using an arbitrary precision datatype). After reading your comment, I investigated more into the problem, e.g. using http://www.cygnus-software.com/papers/comparingfloats/Comparing%20floating%20point%20numbers.htm, and addressed it (hopefully correct) in the way you proposed.
Though, I had to split up the epsilon test into two categories:
- general comparison of floating-point values: using ulp, as values can be arbitrarily small
- algorithm convergence check: using a standard epsilon, as the algorithm may not converge due to limited precision of
the double datatype otherwise
Please find attached my updated patch, any comments are welcome (e.g. I was unsure whether to expose the maxUlps parameter in the constructor, or to use a generic comparison epsilon, e.g. using FastMath.ulp(1d) instead of one adjusted to the current value in question).
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Luc Maisonobe (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13015549#comment-13015549 ]
Luc Maisonobe commented on MATH-434:
------------------------------------
Thanks Thomas.
I had a look at the patch. I'm not a big fan of using BigReal, mainly when we don't specify a scale and we don't link it to the choice for epsilon. Also reading back Ben comments, I wonder if we should not replace epsilon by an integer number of ulps with a default set to a very small value (say something like 10 ulps).
What problem did you see in the accuracy of the variables to use BigReal ?
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Wayne Witzel (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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
...
final double ratio = rhs / entry;
if (MathUtils.equals(ratio, minRatio, epsilon)) {
minRatioPositions.add(i);
} else {
...
with
...
if (MathUtils.equals(rhs, minRatio*entry, epsilon)) {
minRatioPositions.add(i);
} else {
final double ratio = rhs / entry;
...
I believe this would be more appropriate (and at least resolves this particular problem).
My original suggested fix had a potential for overflow errors (since minRatio is initialized to Double.MAX_VALUE). Also, I added another suggestion and pointed out another bug which leads to invalid solutions.
> 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
>
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] [Commented] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13015853#comment-13015853 ]
Gilles commented on MATH-434:
-----------------------------
[Pardon the possibly naïve questions.]
In "SimplexTableau":
* Why not use directly "equals(double, double, int)" from "MathUtils" instead of computing an epsilon with "getEpsilon"?
* Why is the "isOptimal" method not using the adjusted "epsilon" (at line 385)?
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Commented: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Gilles (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12929508#action_12929508 ]
Gilles commented on MATH-434:
-----------------------------
Could you attach unit tests that demonstrate each problem? Thank you.
> 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
>
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Wayne Witzel (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] [Updated] (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Thomas Neidhart (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Phil Steitz (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Wayne Witzel (JIRA)" <ji...@apache.org>.
[ 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Wayne Witzel (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12931688#action_12931688 ]
Wayne Witzel commented on MATH-434:
-----------------------------------
I'll try to send some examples soon. I'm noticing more problems with the right-hand-side going negative and want to cover all bases (as much as possible).
> 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
>
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (MATH-434) SimplexSolver returns unfeasible
solution
Posted by "Benjamin McCann (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MATH-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12980570#action_12980570 ]
Benjamin McCann commented on MATH-434:
--------------------------------------
Hey, sorry I took so long to look at this. I've had very little time and am not working on this stuff anymore. I'm honestly not going to be able to look at this stuff much moving forward, so hopefully there's a Commons Math contributor that can act as a reviewer.
When you say it's choosing a pivot with a negative RHS, I'm assuming that means it's not within the epsilon?
Why would it be more appropriate to divide by the entry? I'm not sure I see why you'd want to use a bigger epsilon when the entry is 0.1 and a smaller epsilon when the entry is 10. Maybe we should just make the default epsilon smaller? I'm no expert with floating point math so I'm not real sure how to set the epsilon and just made up a value.
...
if (MathUtils.equals(ratio, minRatio, epsilon)) {
...
with
...
if (MathUtils.equals(ratio, minRatio, Math.abs(epsilon/entry))) {
> 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<LinearConstraint> cnsts = new ArrayList<LinearConstraint>(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.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.