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