Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 0B510D7DB for ; Mon, 30 Jul 2012 19:38:34 +0000 (UTC) Received: (qmail 39458 invoked by uid 500); 30 Jul 2012 19:38:33 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 39397 invoked by uid 500); 30 Jul 2012 19:38:33 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 39390 invoked by uid 99); 30 Jul 2012 19:38:33 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 30 Jul 2012 19:38:33 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 30 Jul 2012 19:38:32 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id DA71723888EA for ; Mon, 30 Jul 2012 19:37:48 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@commons.apache.org From: tn@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120730193748.DA71723888EA@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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 constraints = new ArrayList(); + + 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);