commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r763412 - in /commons/proper/math/trunk/src: java/org/apache/commons/math/optimization/linear/ test/org/apache/commons/math/optimization/linear/
Date Wed, 08 Apr 2009 21:41:48 GMT
Author: luc
Date: Wed Apr  8 21:41:47 2009
New Revision: 763412

URL: http://svn.apache.org/viewvc?rev=763412&view=rev
Log:
added a threshold for comparisons in Simplex solver
Jira: MATH-246

Modified:
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
    commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
    commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
    commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
(original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
Wed Apr  8 21:41:47 2009
@@ -33,7 +33,7 @@
     private static final long serialVersionUID = -4886937648715323786L;
 
     /** Default amount of error to accept in floating point comparisons. */ 
-    private static final double DEFAULT_EPSILON = 1.0e-10;
+    private static final double DEFAULT_EPSILON = 1.0e-6;
 
     /** Amount of error to accept in floating point comparisons. */ 
     protected final double epsilon;  
@@ -62,7 +62,7 @@
         double minValue = 0;
         Integer minPos = null;
         for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++)
{
-            if (tableau.getEntry(0, i) < minValue) {
+            if (MathUtils.compareTo(tableau.getEntry(0, i), minValue, epsilon) < 0) {
                 minValue = tableau.getEntry(0, i);
                 minPos = i;
             }
@@ -81,7 +81,7 @@
         Integer minRatioPos = null;
         for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++)
{
             double rhs = tableau.getEntry(i, tableau.getWidth() - 1);
-            if (tableau.getEntry(i, col) >= 0) {
+            if (MathUtils.compareTo(tableau.getEntry(i, col), 0, epsilon) >= 0) {
                 double ratio = rhs / tableau.getEntry(i, col);
                 if (ratio < minRatio) {
                     minRatio = ratio;
@@ -133,7 +133,7 @@
             return true;
         }
         for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++)
{
-            if (tableau.getEntry(0, i) < 0) {
+            if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
                 return false;
             }
         }
@@ -150,7 +150,7 @@
             return false;
         }
         for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth() - 1; i++)
{
-            if (tableau.getEntry(0, i) < 0) {
+            if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) < 0) {
                 return false;
             }
         }
@@ -186,7 +186,7 @@
     public RealPointValuePair doOptimize()
         throws OptimizationException {
         final SimplexTableau tableau =
-            new SimplexTableau(f, constraints, goalType, restrictToNonNegative);
+            new SimplexTableau(f, constraints, goalType, restrictToNonNegative, epsilon);
         solvePhase1(tableau);
         tableau.discardArtificialVariables();
         while (!isOptimal(tableau)) {

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
(original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
Wed Apr  8 21:41:47 2009
@@ -27,6 +27,7 @@
 import org.apache.commons.math.linear.RealVector;
 import org.apache.commons.math.optimization.GoalType;
 import org.apache.commons.math.optimization.RealPointValuePair;
+import org.apache.commons.math.util.MathUtils;
 
 /**
  * A tableau for use in the Simplex method.
@@ -79,6 +80,9 @@
     /** Number of artificial variables. */
     protected int numArtificialVariables;
 
+    /** Amount of error to accept in floating point comparisons. */ 
+    protected final double epsilon;
+    
     /**
      * Build a tableau for a linear problem.
      * @param f linear objective function
@@ -86,13 +90,16 @@
      * @param goalType type of optimization goal: either {@link GoalType#MAXIMIZE}
      * or {@link GoalType#MINIMIZE}
      * @param restrictToNonNegative whether to restrict the variables to non-negative values
+     * @param epsilon amount of error to accept in floating point comparisons
      */
     SimplexTableau(final LinearObjectiveFunction f,
                    final Collection<LinearConstraint> constraints,
-                   final GoalType goalType, final boolean restrictToNonNegative) {
+                   final GoalType goalType, final boolean restrictToNonNegative,
+                   final double epsilon) {
         this.f                      = f;
         this.constraints            = constraints;
         this.restrictToNonNegative  = restrictToNonNegative;
+        this.epsilon                = epsilon;
         this.numDecisionVariables   = getNumVariables() + (restrictToNonNegative ? 0 : 1);
         this.numSlackVariables      = getConstraintTypeCounts(Relationship.LEQ) +
                                       getConstraintTypeCounts(Relationship.GEQ);
@@ -259,7 +266,7 @@
     private Integer getBasicRow(final int col) {
         Integer row = null;
         for (int i = getNumObjectiveFunctions(); i < getHeight(); i++) {
-            if (getEntry(i, col) != 0.0) {
+            if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) {
                 if (row == null) {
                     row = i;
                 } else {

Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
(original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Wed Apr  8 21:41:47 2009
@@ -31,7 +31,6 @@
 public class SimplexSolverTest extends TestCase {
 
     public void testSimplexSolver() throws OptimizationException {
-
         LinearObjectiveFunction f =
             new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -143,6 +142,22 @@
         assertEquals(1438556.7491409, solution.getValue(), .0000001);
     }
 
+    public void testEpsilon() throws OptimizationException {
+      LinearObjectiveFunction f =
+          new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
+      Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+      constraints.add(new LinearConstraint(new double[] {  9, 8, 0 }, Relationship.EQ,  17));
+      constraints.add(new LinearConstraint(new double[] {  0, 7, 8 }, Relationship.LEQ, 
7));
+      constraints.add(new LinearConstraint(new double[] { 10, 0, 2 }, Relationship.LEQ, 10));
+
+      SimplexSolver solver = new SimplexSolver();
+      RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
+      assertEquals(1.0, solution.getPoint()[0]);
+      assertEquals(1.0, solution.getPoint()[1]);
+      assertEquals(0.0, solution.getPoint()[2]);
+      assertEquals(15.0, solution.getValue());
+  }
+    
     public void testTrivialModel() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();

Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java?rev=763412&r1=763411&r2=763412&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
(original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
Wed Apr  8 21:41:47 2009
@@ -30,7 +30,7 @@
         LinearObjectiveFunction f = createFunction();
         Collection<LinearConstraint> constraints = createConstraints();
         SimplexTableau tableau =
-            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
         double[][] expectedInitialTableau = {
                                              {-1, 0,  -1,  -1,  2, 0, 0, 0, -4},
                                              { 0, 1, -15, -10, 25, 0, 0, 0,  0},
@@ -45,7 +45,7 @@
         LinearObjectiveFunction f = createFunction();
         Collection<LinearConstraint> constraints = createConstraints();
         SimplexTableau tableau =
-            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
         double[][] expectedTableau = {
                                       { 1, -15, -10, 25, 0, 0, 0},
                                       { 0,   1,   0, -1, 1, 0, 2},
@@ -63,7 +63,7 @@
         constraints.add(new LinearConstraint(new double[] {0, 1}, Relationship.LEQ, 3));
         constraints.add(new LinearConstraint(new double[] {1, 1}, Relationship.LEQ, 4));
   
         SimplexTableau tableau =
-            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false);
+            new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
         double[][] initialTableau = {
                                      {1, -15, -10, 25, 0, 0, 0, 0},
                                      {0,   1,   0, -1, 1, 0, 0, 2},



Mime
View raw message