commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1435810 - in /commons/proper/math/trunk/src: changes/ main/java/org/apache/commons/math3/optim/linear/ test/java/org/apache/commons/math3/optim/linear/
Date Sun, 20 Jan 2013 10:04:45 GMT
Author: tn
Date: Sun Jan 20 10:04:45 2013
New Revision: 1435810

URL: http://svn.apache.org/viewvc?rev=1435810&view=rev
Log:
[MATH-930] Add new constructors to override the hard-coded cut-off value, further improve
javadoc and update failing unit test.

Modified:
    commons/proper/math/trunk/src/changes/changes.xml
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java

Modified: commons/proper/math/trunk/src/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Sun Jan 20 10:04:45 2013
@@ -56,9 +56,9 @@ This is a minor release: It combines bug
   way such as to allow drop-in replacement of the v3.1[.1] JAR file.
 ">
       <action dev="tn" type="fix" issue="MATH-930">
-        Improved class javadoc wrt convergence criteria and added an 
-        additional constructor to override the default epsilon value in class
-        "SimplexSolver".
+        Improved class javadoc wrt convergence criteria and added 
+        additional constructors to override the default epsilon and cut-off
+        values in class "SimplexSolver".
       </action>
       <action dev="erans" type="fix" issue="MATH-929" due-to="Piotr Wydrych">
         Fixed truncated value in "MultivariateNormalDistribution".

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexSolver.java
Sun Jan 20 10:04:45 2013
@@ -34,8 +34,15 @@ import org.apache.commons.math3.util.Pre
  * <ul>
  *   <li>Algorithm convergence: 1e-6</li>
  *   <li>Floating-point comparisons: 10 ulp</li>
+ *   <li>Cut-Off value: 1e-12</li>
  * </ul>
  * <p>
+ * The cut-off value has been introduced to zero out very small numbers in the Simplex tableau,
+ * as these may lead to numerical instabilities due to the nature of the Simplex algorithm
+ * (the pivot element is used as a denominator). If the problem definition is very tight,
the
+ * default cut-off value may be too small, thus it is advised to increase it to a larger
value,
+ * in accordance with the chosen epsilon.
+ * <p>
  * It may also be counter-productive to provide a too large value for {@link MaxIter}
  * as parameter in the call of {@link #optimize(org.apache.commons.math3.optim.OptimizationData...)},
  * as the {@link SimplexSolver} will use different strategies depending on the current iteration
@@ -46,12 +53,15 @@ import org.apache.commons.math3.util.Pre
  * @since 2.0
  */
 public class SimplexSolver extends LinearOptimizer {
+    /** Default amount of error to accept in floating point comparisons (as ulps). */
+    static final int DEFAULT_ULPS = 10;
+
+    /** Default cut-off value. */
+    static final double DEFAULT_CUT_OFF = 1e-12;
+
     /** Default amount of error to accept for algorithm convergence. */
     private static final double DEFAULT_EPSILON = 1.0e-6;
 
-    /** Default amount of error to accept in floating point comparisons (as ulps). */
-    private static final int DEFAULT_ULPS = 10;
-
     /** Amount of error to accept for algorithm convergence. */
     private final double epsilon;
 
@@ -59,10 +69,16 @@ public class SimplexSolver extends Linea
     private final int maxUlps;
 
     /**
+     * Cut-off value for entries in the tableau: values smaller than the cut-off
+     * are treated as zero to improve numerical stability.
+     */
+    private final double cutOff;
+
+    /**
      * Builds a simplex solver with default settings.
      */
     public SimplexSolver() {
-        this(DEFAULT_EPSILON, DEFAULT_ULPS);
+        this(DEFAULT_EPSILON, DEFAULT_ULPS, DEFAULT_CUT_OFF);
     }
 
     /**
@@ -71,7 +87,17 @@ public class SimplexSolver extends Linea
      * @param epsilon Amount of error to accept for algorithm convergence.
      */
     public SimplexSolver(final double epsilon) {
-        this(epsilon, DEFAULT_ULPS);
+        this(epsilon, DEFAULT_ULPS, DEFAULT_CUT_OFF);
+    }
+
+    /**
+     * Builds a simplex solver with a specified accepted amount of error.
+     *
+     * @param epsilon Amount of error to accept for algorithm convergence.
+     * @param maxUlps Amount of error to accept in floating point comparisons.
+     */
+    public SimplexSolver(final double epsilon, final int maxUlps) {
+        this(epsilon, maxUlps, DEFAULT_CUT_OFF);
     }
 
     /**
@@ -79,11 +105,12 @@ public class SimplexSolver extends Linea
      *
      * @param epsilon Amount of error to accept for algorithm convergence.
      * @param maxUlps Amount of error to accept in floating point comparisons.
+     * @param cutOff Values smaller than the cutOff are treated as zero.
      */
-    public SimplexSolver(final double epsilon,
-                         final int maxUlps) {
+    public SimplexSolver(final double epsilon, final int maxUlps, final double cutOff) {
         this.epsilon = epsilon;
         this.maxUlps = maxUlps;
+        this.cutOff = cutOff;
     }
 
     /**
@@ -258,7 +285,8 @@ public class SimplexSolver extends Linea
                                getGoalType(),
                                isRestrictedToNonNegative(),
                                epsilon,
-                               maxUlps);
+                               maxUlps,
+                               cutOff);
 
         solvePhase1(tableau);
         tableau.dropPhase1Objective();

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optim/linear/SimplexTableau.java
Sun Jan 20 10:04:45 2013
@@ -66,12 +66,6 @@ class SimplexTableau implements Serializ
     /** Column label for negative vars. */
     private static final String NEGATIVE_VAR_COLUMN_LABEL = "x-";
 
-    /** Default amount of error to accept in floating point comparisons (as ulps). */
-    private static final int DEFAULT_ULPS = 10;
-
-    /** The cut-off threshold to zero-out entries. */
-    private static final double CUTOFF_THRESHOLD = 1e-12;
-
     /** Serializable version identifier. */
     private static final long serialVersionUID = -1369660067587938365L;
 
@@ -105,6 +99,9 @@ class SimplexTableau implements Serializ
     /** Amount of error to accept in floating point comparisons. */
     private final int maxUlps;
 
+    /** Cut-off value for entries in the tableau. */
+    private final double cutOff;
+
     /**
      * Builds a tableau for a linear problem.
      *
@@ -120,7 +117,8 @@ class SimplexTableau implements Serializ
                    final GoalType goalType,
                    final boolean restrictToNonNegative,
                    final double epsilon) {
-        this(f, constraints, goalType, restrictToNonNegative, epsilon, DEFAULT_ULPS);
+        this(f, constraints, goalType, restrictToNonNegative, epsilon,
+                SimplexSolver.DEFAULT_ULPS, SimplexSolver.DEFAULT_CUT_OFF);
     }
 
     /**
@@ -138,11 +136,32 @@ class SimplexTableau implements Serializ
                    final boolean restrictToNonNegative,
                    final double epsilon,
                    final int maxUlps) {
+        this(f, constraints, goalType, restrictToNonNegative, epsilon, maxUlps, SimplexSolver.DEFAULT_CUT_OFF);
+    }
+
+    /**
+     * Build a tableau for a linear problem.
+     * @param f linear objective function
+     * @param constraints linear constraints
+     * @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 when checking for optimality
+     * @param maxUlps amount of error to accept in floating point comparisons
+     * @param cutOff the cut-off value for tableau entries
+     */
+    SimplexTableau(final LinearObjectiveFunction f,
+                   final Collection<LinearConstraint> constraints,
+                   final GoalType goalType,
+                   final boolean restrictToNonNegative,
+                   final double epsilon,
+                   final int maxUlps,
+                   final double cutOff) {
         this.f                      = f;
         this.constraints            = normalizeConstraints(constraints);
         this.restrictToNonNegative  = restrictToNonNegative;
         this.epsilon                = epsilon;
         this.maxUlps                = maxUlps;
+        this.cutOff                 = cutOff;
         this.numDecisionVariables   = f.getCoefficients().getDimension() +
                                       (restrictToNonNegative ? 0 : 1);
         this.numSlackVariables      = getConstraintTypeCounts(Relationship.LEQ) +
@@ -462,8 +481,8 @@ class SimplexTableau implements Serializ
                                final double multiple) {
         for (int i = 0; i < getWidth(); i++) {
             double result = tableau.getEntry(minuendRow, i) - tableau.getEntry(subtrahendRow,
i) * multiple;
-            // cut-off values smaller than the CUTOFF_THRESHOLD, otherwise may lead to numerical
instabilities
-            if (FastMath.abs(result) < CUTOFF_THRESHOLD) {
+            // cut-off values smaller than the cut-off threshold, otherwise may lead to numerical
instabilities
+            if (FastMath.abs(result) < cutOff) {
                 result = 0.0;
             }
             tableau.setEntry(minuendRow, i, result);

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java?rev=1435810&r1=1435809&r2=1435810&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optim/linear/SimplexSolverTest.java
Sun Jan 20 10:04:45 2013
@@ -420,11 +420,11 @@ public class SimplexSolverTest {
         double[] objFunctionCoeff = new double[33];
         objFunctionCoeff[3] = 1;
         LinearObjectiveFunction f = new LinearObjectiveFunction(objFunctionCoeff, 0);
-        SimplexSolver solver = new SimplexSolver(1e-4, 10);
+        SimplexSolver solver = new SimplexSolver(1e-4, 10, 1e-6);
         
         PointValuePair solution = solver.optimize(new MaxIter(1000), f, new LinearConstraintSet(constraints),
                                                   GoalType.MINIMIZE, new NonNegativeConstraint(true));
-        Assert.assertEquals(0.3752298, solution.getValue(), 1e-6);
+        Assert.assertEquals(0.3752298, solution.getValue(), 1e-4);
     }
 
     @Test



Mime
View raw message