commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1524213 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/optimization/linear/ test/java/org/apache/commons/math3/optimization/linear/
Date Tue, 17 Sep 2013 20:32:51 GMT
Author: tn
Date: Tue Sep 17 20:32:50 2013
New Revision: 1524213

URL: http://svn.apache.org/r1524213
Log:
[MATH-842] revert incomplete change and postpone.

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

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.java?rev=1524213&r1=1524212&r2=1524213&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.java
Tue Sep 17 20:32:50 2013
@@ -47,9 +47,6 @@ public class SimplexSolver extends Abstr
     /** Amount of error to accept in floating point comparisons (as ulps). */
     private final int maxUlps;
 
-    /** Prevent cycles via Bland's rule. */
-    private boolean cyclePrevention;
-
     /**
      * Build a simplex solver with default settings.
      */
@@ -65,33 +62,6 @@ public class SimplexSolver extends Abstr
     public SimplexSolver(final double epsilon, final int maxUlps) {
         this.epsilon = epsilon;
         this.maxUlps = maxUlps;
-        this.cyclePrevention = true;
-    }
-
-    /**
-     * Enables/disables cycle prevention using Bland's rule.
-     * <p>
-     * In case of a degeneracy the simplex algorithm might cycle. This can be prevented
-     * by using Bland's pivot selection rule. The drawback of this rule is that it may result
-     * in pivot choices that do not significantly improve the objective function value,
-     * thus increasing the number of required iterations.
-     * <p>
-     * By default, the cycle prevention is enabled.
-     *
-     * @param cyclePrevention if cycle prevention shall be used
-     *
-     * @see <a href="http://www.stanford.edu/class/msande310/blandrule.pdf">Bland's
rule</a>
-     */
-    public void setCyclePrevention(boolean cyclePrevention) {
-        this.cyclePrevention = cyclePrevention;
-    }
-
-    /**
-     * Returns whether cycle prevention (using Bland's rule) is enabled.
-     * @return {@code true} if cycle prevention is enable, {@code false} otherwise
-     */
-    public boolean getCyclePrevention() {
-        return cyclePrevention;
     }
 
     /**
@@ -109,42 +79,14 @@ public class SimplexSolver extends Abstr
             if (entry < minValue) {
                 minValue = entry;
                 minPos = i;
-
-                // Bland's rule: chose the entering column with the lowest index
-                if (cyclePrevention && isValidPivotColumn(tableau, i)) {
-                    break;
-                }
             }
         }
         return minPos;
     }
 
     /**
-     * Checks whether the given column is valid pivot column, i.e. will result
-     * in a valid pivot row.
-     * <p>
-     * When applying Bland's rule to select the pivot column, it may happen that
-     * there is no corresponding pivot row. This method will check if the selected
-     * pivot column will return a valid pivot row.
-     *
-     * @param tableau simplex tableau for the problem
-     * @param col the column to test
-     * @return {@code true} if the pivot column is valid, {@code false} otherwise
-     */
-    private boolean isValidPivotColumn(SimplexTableau tableau, int col) {
-        for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getHeight(); i++)
{
-            final double entry = tableau.getEntry(i, col);
-
-            if (Precision.compareTo(entry, 0d, maxUlps) > 0) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    /**
      * Returns the row with the minimum ratio as given by the minimum ratio test (MRT).
-     * @param tableau simplex tableau for the problem
+     * @param tableau simple tableau for the problem
      * @param col the column to test the ratio of.  See {@link #getPivotColumn(SimplexTableau)}
      * @return row with the minimum ratio
      */
@@ -194,7 +136,11 @@ public class SimplexSolver extends Abstr
             //
             // see http://www.stanford.edu/class/msande310/blandrule.pdf
             // see http://en.wikipedia.org/wiki/Bland%27s_rule (not equivalent to the above
paper)
-            if (cyclePrevention) {
+            //
+            // Additional heuristic: if we did not get a solution after half of maxIterations
+            //                       revert to the simple case of just returning the top-most
row
+            // This heuristic is based on empirical data gathered while investigating MATH-828.
+            if (getIterations() < getMaxIterations() / 2) {
                 Integer minRow = null;
                 int minIndex = tableau.getWidth();
                 final int varStart = tableau.getNumObjectiveFunctions();

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java?rev=1524213&r1=1524212&r2=1524213&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java
Tue Sep 17 20:32:50 2013
@@ -73,7 +73,7 @@ class SimplexTableau implements Serializ
     private static final int DEFAULT_ULPS = 10;
 
     /** The cut-off threshold to zero-out entries. */
-    private static final double CUTOFF_THRESHOLD = 1e-10;
+    private static final double CUTOFF_THRESHOLD = 1e-12;
 
     /** Serializable version identifier. */
     private static final long serialVersionUID = -1369660067587938365L;

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/linear/SimplexSolverTest.java?rev=1524213&r1=1524212&r2=1524213&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/linear/SimplexSolverTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/optimization/linear/SimplexSolverTest.java
Tue Sep 17 20:32:50 2013
@@ -31,31 +31,6 @@ import org.junit.Test;
 public class SimplexSolverTest {
 
     @Test
-    public void testMath842Cycle() {
-        // from http://www.math.toronto.edu/mpugh/Teaching/APM236_04/bland
-        //      maximize 10 x1 - 57 x2 - 9 x3 - 24 x4
-        //      subject to
-        //          1/2 x1 - 11/2 x2 - 5/2 x3 + 9 x4  <= 0
-        //          1/2 x1 -  3/2 x2 - 1/2 x3 +   x4  <= 0
-        //              x1                  <= 1
-        //      x1,x2,x3,x4 >= 0
-
-        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 10, -57, -9,
-24}, 0);
-        
-        ArrayList <LinearConstraint>constraints = new ArrayList<LinearConstraint>();
-
-        constraints.add(new LinearConstraint(new double[] {0.5, -5.5, -2.5, 9}, Relationship.LEQ,
0));
-        constraints.add(new LinearConstraint(new double[] {0.5, -1.5, -0.5, 1}, Relationship.LEQ,
0));
-        constraints.add(new LinearConstraint(new double[] {  1,    0,    0, 0}, Relationship.LEQ,
1));
-        
-        double epsilon = 1e-6;
-        SimplexSolver solver = new SimplexSolver();
-        PointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
-        Assert.assertEquals(1.0d, solution.getValue(), epsilon);
-        Assert.assertTrue(validSolution(solution, constraints, epsilon));
-    }
-
-    @Test
     public void testMath828() {
         LinearObjectiveFunction f = new LinearObjectiveFunction(
                 new double[] { 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
0.0, 0.0, 0.0, 0.0}, 0.0);



Mime
View raw message