commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Wayne Witzel (JIRA)" <j...@apache.org>
Subject [jira] Created: (MATH-434) SimplexSolver returns unfeasible solution
Date Sun, 07 Nov 2010 03:57:06 GMT
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.


Mime
View raw message