You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/07/30 21:37:48 UTC
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
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);