commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r812831 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/optimization/linear/ test/java/org/apache/commons/math/optimization/linear/
Date Wed, 09 Sep 2009 08:48:04 GMT
Author: luc
Date: Wed Sep  9 08:48:03 2009
New Revision: 812831

URL: http://svn.apache.org/viewvc?rev=812831&view=rev
Log:
applied Benjamin's patch from 2009-09-08
warning: I had to update the expected matrix in SimplexTableauTest.testdiscardArtificialVariables

JIRA: MATH-286

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

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexSolver.java
Wed Sep  9 08:48:03 2009
@@ -174,7 +174,7 @@
             new SimplexTableau(function, linearConstraints, goal, nonNegative, epsilon);
 
         solvePhase1(tableau);
-        tableau.discardArtificialVariables();
+        tableau.dropPhase1Objective();
 
         while (!tableau.isOptimal()) {
             doIteration(tableau);

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
(original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
Wed Sep  9 08:48:03 2009
@@ -112,8 +112,7 @@
                                       getConstraintTypeCounts(Relationship.GEQ);
         this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
                                       getConstraintTypeCounts(Relationship.GEQ);
-        this.tableau = new Array2DRowRealMatrix(createTableau(goalType == GoalType.MAXIMIZE));
-        initialize();
+        this.tableau = createTableau(goalType == GoalType.MAXIMIZE);
     }
 
     /**
@@ -121,29 +120,29 @@
      * @param maximize if true, goal is to maximize the objective function
      * @return created tableau
      */
-    protected double[][] createTableau(final boolean maximize) {
+    protected RealMatrix createTableau(final boolean maximize) {
 
         // create a matrix of the correct size
         int width = numDecisionVariables + numSlackVariables +
         numArtificialVariables + getNumObjectiveFunctions() + 1; // + 1 is for RHS
         int height = constraints.size() + getNumObjectiveFunctions();
-        double[][] matrix = new double[height][width];
+        Array2DRowRealMatrix matrix = new Array2DRowRealMatrix(height, width);
 
         // initialize the objective function rows
         if (getNumObjectiveFunctions() == 2) {
-            matrix[0][0] = -1;
+            matrix.setEntry(0, 0, -1);
         }
         int zIndex = (getNumObjectiveFunctions() == 1) ? 0 : 1;
-        matrix[zIndex][zIndex] = maximize ? 1 : -1;
+        matrix.setEntry(zIndex, zIndex, maximize ? 1 : -1);
         RealVector objectiveCoefficients =
             maximize ? f.getCoefficients().mapMultiply(-1) : f.getCoefficients();
-        copyArray(objectiveCoefficients.getData(), matrix[zIndex]);
-        matrix[zIndex][width - 1] =
-            maximize ? f.getConstantTerm() : -1 * f.getConstantTerm();
+        copyArray(objectiveCoefficients.getData(), matrix.getDataRef()[zIndex]);
+        matrix.setEntry(zIndex, width - 1,
+            maximize ? f.getConstantTerm() : -1 * f.getConstantTerm());
 
         if (!restrictToNonNegative) {
-            matrix[zIndex][getSlackVariableOffset() - 1] =
-                getInvertedCoeffiecientSum(objectiveCoefficients);
+            matrix.setEntry(zIndex, getSlackVariableOffset() - 1,
+                getInvertedCoeffiecientSum(objectiveCoefficients));
         }
 
         // initialize the constraint rows
@@ -154,34 +153,34 @@
             int row = getNumObjectiveFunctions() + i;
 
             // decision variable coefficients
-            copyArray(constraint.getCoefficients().getData(), matrix[row]);
+            copyArray(constraint.getCoefficients().getData(), matrix.getDataRef()[row]);
 
             // x-
             if (!restrictToNonNegative) {
-                matrix[row][getSlackVariableOffset() - 1] =
-                    getInvertedCoeffiecientSum(constraint.getCoefficients());
+                matrix.setEntry(row, getSlackVariableOffset() - 1,
+                    getInvertedCoeffiecientSum(constraint.getCoefficients()));
             }
 
             // RHS
-            matrix[row][width - 1] = constraint.getValue();
+            matrix.setEntry(row, width - 1, constraint.getValue());
 
             // slack variables
             if (constraint.getRelationship() == Relationship.LEQ) {
-                matrix[row][getSlackVariableOffset() + slackVar++] = 1;  // slack
+                matrix.setEntry(row, getSlackVariableOffset() + slackVar++, 1);  // slack
             } else if (constraint.getRelationship() == Relationship.GEQ) {
-                matrix[row][getSlackVariableOffset() + slackVar++] = -1; // excess
+                matrix.setEntry(row, getSlackVariableOffset() + slackVar++, -1); // excess
             }
 
             // artificial variables
             if ((constraint.getRelationship() == Relationship.EQ) ||
                     (constraint.getRelationship() == Relationship.GEQ)) {
-                matrix[0][getArtificialVariableOffset() + artificialVar] = 1;
-                matrix[row][getArtificialVariableOffset() + artificialVar++] = 1;
+                matrix.setEntry(0, getArtificialVariableOffset() + artificialVar, 1);
+                matrix.setEntry(row, getArtificialVariableOffset() + artificialVar++, 1);
+                matrix.setRowVector(0, matrix.getRowVector(0).subtract(matrix.getRowVector(row)));
             }
         }
 
         return matrix;
-
     }
 
     /**
@@ -236,17 +235,6 @@
     }
 
     /**
-     * Puts the tableau in proper form by zeroing out the artificial variables
-     * in the objective function via elementary row operations.
-     */
-    private void initialize() {
-        for (int artificialVar = 0; artificialVar < numArtificialVariables; artificialVar++)
{
-            int row = getBasicRow(getArtificialVariableOffset() + artificialVar);
-            subtractRow(0, row, 1.0);
-        }
-    }
-
-    /**
      * Get the -1 times the sum of all coefficients in the given array.
      * @param coefficients coefficients to sum
      * @return the -1 times the sum of all coefficients in the given array.
@@ -264,30 +252,9 @@
      * @param col index of the column to check
      * @return the row that the variable is basic in.  null if the column is not basic
      */
-    Integer getBasicRow(final int col) {
-        return getBasicRow(col, true);
-    }
-
-    /**
-     * Checks whether the given column is basic.
-     * @param col index of the column to check
-     * @return the row that the variable is basic in.  null if the column is not basic
-     */
-    private Integer getBasicRowForSolution(final int col) {
-        return getBasicRow(col, false);
-    }
-
-    /**
-     * Checks whether the given column is basic.
-     * @param col index of the column to check
-     * @param ignoreObjectiveRows if true ignore the first rows which correspond
-     * to objective functions
-     * @return the row that the variable is basic in.  null if the column is not basic
-     */
-    private Integer getBasicRow(final int col, boolean ignoreObjectiveRows) {
+    protected Integer getBasicRow(final int col) {
         Integer row = null;
-        int start = ignoreObjectiveRows ? getNumObjectiveFunctions() : 0;
-        for (int i = start; i < getHeight(); i++) {
+        for (int i = 0; i < getHeight(); i++) {
             if (MathUtils.equals(getEntry(i, col), 1.0, epsilon) && (row == null))
{
                 row = i;
             } else if (!MathUtils.equals(getEntry(i, col), 0.0, epsilon)) {
@@ -298,21 +265,42 @@
     }
 
     /**
-     * Removes the phase 1 objective function and artificial variables from this tableau.
+     * Removes the phase 1 objective function, positive cost non-artificial variables,
+     * and the non-basic artificial variables from this tableau.
      */
-    protected void discardArtificialVariables() {
-        if (numArtificialVariables == 0) {
+    protected void dropPhase1Objective() {
+        if (getNumObjectiveFunctions() == 1) {
             return;
         }
-        int width = getWidth() - numArtificialVariables - 1;
-        int height = getHeight() - 1;
-        double[][] matrix = new double[height][width];
-        for (int i = 0; i < height; i++) {
-            for (int j = 0; j < width - 1; j++) {
-                matrix[i][j] = getEntry(i + 1, j + 1);
+
+        List<Integer> columnsToDrop = new ArrayList<Integer>();
+        columnsToDrop.add(0);
+
+        // positive cost non-artificial variables
+        for (int i = getNumObjectiveFunctions(); i < getArtificialVariableOffset(); i++)
{
+          if (MathUtils.compareTo(tableau.getEntry(0, i), 0, epsilon) > 0) {
+            columnsToDrop.add(i);
+          }
+        }
+
+        // non-basic artificial variables
+        for (int i = 0; i < getNumArtificialVariables(); i++) {
+          int col = i + getArtificialVariableOffset();
+          if (getBasicRow(col) == null) {
+            columnsToDrop.add(col);
+          }
+        }
+
+        double[][] matrix = new double[getHeight() - 1][getWidth() - columnsToDrop.size()];
+        for (int i = 1; i < getHeight(); i++) {
+          int col = 0;
+          for (int j = 0; j < getWidth(); j++) {
+            if (!columnsToDrop.contains(j)) {
+              matrix[i - 1][col++] = tableau.getEntry(i, j);
             }
-            matrix[i][width - 1] = getEntry(i + 1, getRhsOffset());
+          }
         }
+
         this.tableau = new Array2DRowRealMatrix(matrix);
         this.numArtificialVariables = 0;
     }
@@ -345,11 +333,11 @@
      */
     protected RealPointValuePair getSolution() {
       double[] coefficients = new double[getOriginalNumDecisionVariables()];
-      Integer negativeVarBasicRow = getBasicRowForSolution(getNegativeDecisionVariableOffset());
+      Integer negativeVarBasicRow = getBasicRow(getNegativeDecisionVariableOffset());
       double mostNegative = negativeVarBasicRow == null ? 0 : getEntry(negativeVarBasicRow,
getRhsOffset());
       Set<Integer> basicRows = new HashSet<Integer>();
       for (int i = 0; i < coefficients.length; i++) {
-          Integer basicRow = getBasicRowForSolution(getNumObjectiveFunctions() + i);
+          Integer basicRow = getBasicRow(getNumObjectiveFunctions() + i);
           if (basicRows.contains(basicRow)) {
               // if multiple variables can take a given value
               // then we choose the first and set the rest equal to 0
@@ -391,10 +379,8 @@
      */
     protected void subtractRow(final int minuendRow, final int subtrahendRow,
                                final double multiple) {
-        for (int j = 0; j < getWidth(); j++) {
-            tableau.setEntry(minuendRow, j, tableau.getEntry(minuendRow, j) -
-                             multiple * tableau.getEntry(subtrahendRow, j));
-        }
+        tableau.setRowVector(minuendRow, tableau.getRowVector(minuendRow)
+            .subtract(tableau.getRowVector(subtrahendRow).mapMultiply(multiple)));
     }
 
     /**

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Wed Sep  9 08:48:03 2009
@@ -48,13 +48,17 @@
 
     @Test
     public void testMath286() throws OptimizationException {
-        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.2, 0.3 },
0 );
+        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2,
0.7, 0.3, 0.6, 0.4 }, 0 );
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
-        constraints.add(new LinearConstraint(new double[] { 1, 1 }, Relationship.EQ, 23.0));
+        constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ,
23.0));
+        constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ,
23.0));
+        constraints.add(new LinearConstraint(new double[] { 1, 0, 0, 0, 0, 0 }, Relationship.GEQ,
10.0));
+        constraints.add(new LinearConstraint(new double[] { 0, 0, 1, 0, 0, 0 }, Relationship.GEQ,
8.0));
+        constraints.add(new LinearConstraint(new double[] { 0, 0, 0, 0, 1, 0 }, Relationship.GEQ,
5.0));
 
         SimplexSolver solver = new SimplexSolver();
         RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE,
true);
-        Assert.assertEquals(6.9, solution.getValue(), .0000001);
+        Assert.assertEquals(25.8, solution.getValue(), .0000001);
     }
 
     @Test

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java?rev=812831&r1=812830&r2=812831&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
(original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexTableauTest.java
Wed Sep  9 08:48:03 2009
@@ -50,12 +50,12 @@
         SimplexTableau tableau =
             new SimplexTableau(f, constraints, GoalType.MAXIMIZE, false, 1.0e-6);
         double[][] expectedTableau = {
-                                      { 1, -15, -10, 25, 0, 0, 0},
-                                      { 0,   1,   0, -1, 1, 0, 2},
-                                      { 0,   0,   1, -1, 0, 1, 3},
-                                      { 0,   1,   1, -2, 0, 0, 4}
+                                      { 1, -15, -10, 0, 0, 0, 0},
+                                      { 0,   1,   0, 1, 0, 0, 2},
+                                      { 0,   0,   1, 0, 1, 0, 3},
+                                      { 0,   1,   1, 0, 0, 1, 4}
         };
-        tableau.discardArtificialVariables();
+        tableau.dropPhase1Objective();
         assertMatrixEquals(expectedTableau, tableau.getData());
     }
 



Mime
View raw message