commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1367242 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.java test/java/org/apache/commons/math3/optimization/linear/SimplexSolverTest.java
Date Mon, 30 Jul 2012 19:37:48 GMT
Author: tn
Date: Mon Jul 30 19:37:48 2012
New Revision: 1367242

URL: http://svn.apache.org/viewvc?rev=1367242&view=rev
Log:
[MATH-828] Add additional heuristic for rare cases in pivotRow selection.

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexSolver.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=1367242&r1=1367241&r2=1367242&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
Mon Jul 30 19:37:48 2012
@@ -116,12 +116,14 @@ public class SimplexSolver extends Abstr
             // there's a degeneracy as indicated by a tie in the minimum ratio test
 
             // 1. check if there's an artificial variable that can be forced out of the basis
-            for (Integer row : minRatioPositions) {
-                for (int i = 0; i < tableau.getNumArtificialVariables(); i++) {
-                    int column = i + tableau.getArtificialVariableOffset();
-                    final double entry = tableau.getEntry(row, column);
-                    if (Precision.equals(entry, 1d, maxUlps) && row.equals(tableau.getBasicRow(column)))
{
-                        return row;
+            if (tableau.getNumArtificialVariables() > 0) {
+                for (Integer row : minRatioPositions) {
+                    for (int i = 0; i < tableau.getNumArtificialVariables(); i++) {
+                        int column = i + tableau.getArtificialVariableOffset();
+                        final double entry = tableau.getEntry(row, column);
+                        if (Precision.equals(entry, 1d, maxUlps) && row.equals(tableau.getBasicRow(column)))
{
+                            return row;
+                        }
                     }
                 }
             }
@@ -131,20 +133,26 @@ 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)
-            Integer minRow = null;
-            int minIndex = tableau.getWidth();
-            for (Integer row : minRatioPositions) {
-                for (int i = tableau.getNumObjectiveFunctions(); i < tableau.getWidth()
- 1 && minRow != row; i++) {
-                    if (row == tableau.getBasicRow(i)) {
-                        if (i < minIndex) {
-                            minIndex = i;
-                            minRow = row;
+            //
+            // 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();
+                for (Integer row : minRatioPositions) {
+                    int i = tableau.getNumObjectiveFunctions();
+                    for (; i < tableau.getWidth() - 1 && minRow != row; i++) {
+                        if (row == tableau.getBasicRow(i)) {
+                            if (i < minIndex) {
+                                minIndex = i;
+                                minRow = row;
+                            }
                         }
                     }
                 }
+                return minRow;
             }
-
-            return minRow;
         }
         return minRatioPositions.get(0);
     }

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=1367242&r1=1367241&r2=1367242&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
Mon Jul 30 19:37:48 2012
@@ -50,7 +50,28 @@ public class SimplexSolverTest {
         Assert.assertEquals(1.0d, solution.getValue(), epsilon);
         Assert.assertTrue(validSolution(solution, constraints, epsilon));
     }
-    
+
+    @Test
+    public void testMath828Cycle() {
+        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, 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);
+        
+        ArrayList <LinearConstraint>constraints = new ArrayList<LinearConstraint>();
+
+        constraints.add(new LinearConstraint(new double[] {0.0, 16.0, 14.0, 69.0, 1.0, 85.0,
52.0, 43.0, 64.0, 97.0, 14.0, 74.0, 89.0, 28.0, 94.0, 58.0, 13.0, 22.0, 21.0, 17.0, 30.0,
25.0, 1.0, 59.0, 91.0, 78.0, 12.0, 74.0, 56.0, 3.0, 88.0,}, Relationship.GEQ, 91.0));
+        constraints.add(new LinearConstraint(new double[] {0.0, 60.0, 40.0, 81.0, 71.0, 72.0,
46.0, 45.0, 38.0, 48.0, 40.0, 17.0, 33.0, 85.0, 64.0, 32.0, 84.0, 3.0, 54.0, 44.0, 71.0, 67.0,
90.0, 95.0, 54.0, 99.0, 99.0, 29.0, 52.0, 98.0, 9.0,}, Relationship.GEQ, 54.0));
+        constraints.add(new LinearConstraint(new double[] {0.0, 41.0, 12.0, 86.0, 90.0, 61.0,
31.0, 41.0, 23.0, 89.0, 17.0, 74.0, 44.0, 27.0, 16.0, 47.0, 80.0, 32.0, 11.0, 56.0, 68.0,
82.0, 11.0, 62.0, 62.0, 53.0, 39.0, 16.0, 48.0, 1.0, 63.0,}, Relationship.GEQ, 62.0));
+        constraints.add(new LinearConstraint(new double[] {83.0, -76.0, -94.0, -19.0, -15.0,
-70.0, -72.0, -57.0, -63.0, -65.0, -22.0, -94.0, -22.0, -88.0, -86.0, -89.0, -72.0, -16.0,
-80.0, -49.0, -70.0, -93.0, -95.0, -17.0, -83.0, -97.0, -31.0, -47.0, -31.0, -13.0, -23.0,},
Relationship.GEQ, 0.0));
+        constraints.add(new LinearConstraint(new double[] {41.0, -96.0, -41.0, -48.0, -70.0,
-43.0, -43.0, -43.0, -97.0, -37.0, -85.0, -70.0, -45.0, -67.0, -87.0, -69.0, -94.0, -54.0,
-54.0, -92.0, -79.0, -10.0, -35.0, -20.0, -41.0, -41.0, -65.0, -25.0, -12.0, -8.0, -46.0,},
Relationship.GEQ, 0.0));
+        constraints.add(new LinearConstraint(new double[] {27.0, -42.0, -65.0, -49.0, -53.0,
-42.0, -17.0, -2.0, -61.0, -31.0, -76.0, -47.0, -8.0, -93.0, -86.0, -62.0, -65.0, -63.0, -22.0,
-43.0, -27.0, -23.0, -32.0, -74.0, -27.0, -63.0, -47.0, -78.0, -29.0, -95.0, -73.0,}, Relationship.GEQ,
0.0));
+        constraints.add(new LinearConstraint(new double[] {15.0, -46.0, -41.0, -83.0, -98.0,
-99.0, -21.0, -35.0, -7.0, -14.0, -80.0, -63.0, -18.0, -42.0, -5.0, -34.0, -56.0, -70.0, -16.0,
-18.0, -74.0, -61.0, -47.0, -41.0, -15.0, -79.0, -18.0, -47.0, -88.0, -68.0, -55.0,}, Relationship.GEQ,
0.0));
+        
+        double epsilon = 1e-6;
+        PointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MINIMIZE,
true);
+        Assert.assertEquals(1.0d, solution.getValue(), epsilon);
+        Assert.assertTrue(validSolution(solution, constraints, epsilon));        
+    }
+
     @Test
     public void testMath781() {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 2, 6, 7 },
0);



Mime
View raw message