commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From l..@apache.org
Subject svn commit: r813301 - in /commons/proper/math/trunk/src: main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java site/xdoc/changes.xml test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Date Thu, 10 Sep 2009 08:20:28 GMT
Author: luc
Date: Thu Sep 10 08:20:28 2009
New Revision: 813301

URL: http://svn.apache.org/viewvc?rev=813301&view=rev
Log:
Fixed a OutOfBoundException in simplex solver when some constraints are tight
JIRA: MATH-293

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
    commons/proper/math/trunk/src/site/xdoc/changes.xml
    commons/proper/math/trunk/src/test/java/org/apache/commons/math/optimization/linear/SimplexSolverTest.java

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=813301&r1=813300&r2=813301&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
Thu Sep 10 08:20:28 2009
@@ -74,6 +74,9 @@
     /** Whether to restrict the variables to non-negative values. */
     private final boolean restrictToNonNegative;
 
+    /** The variables each column represents */
+    private final List<String> columnLabels = new ArrayList<String>();
+
     /** Simple tableau. */
     private transient RealMatrix tableau;
 
@@ -113,6 +116,27 @@
         this.numArtificialVariables = getConstraintTypeCounts(Relationship.EQ) +
                                       getConstraintTypeCounts(Relationship.GEQ);
         this.tableau = createTableau(goalType == GoalType.MAXIMIZE);
+        initializeColumnLabels();
+    }
+
+    protected void initializeColumnLabels() {
+      if (getNumObjectiveFunctions() == 2) {
+        columnLabels.add("W");
+      }
+      columnLabels.add("Z");
+      for (int i = 0; i < getOriginalNumDecisionVariables(); i++) {
+        columnLabels.add("x" + i);
+      }
+      if (!restrictToNonNegative) {
+        columnLabels.add("x-");
+      }
+      for (int i = 0; i < getNumSlackVariables(); i++) {
+        columnLabels.add("s" + i);
+      }
+      for (int i = 0; i < getNumArtificialVariables(); i++) {
+        columnLabels.add("a" + i);
+      }
+      columnLabels.add("RHS");
     }
 
     /**
@@ -301,6 +325,10 @@
           }
         }
 
+        for (int i = columnsToDrop.size() - 1; i >= 0; i--) {
+          columnLabels.remove((int) columnsToDrop.get(i));
+        }
+
         this.tableau = new Array2DRowRealMatrix(matrix);
         this.numArtificialVariables = 0;
     }
@@ -332,12 +360,19 @@
      * @return current solution
      */
     protected RealPointValuePair getSolution() {
-      double[] coefficients = new double[getOriginalNumDecisionVariables()];
-      Integer negativeVarBasicRow = getBasicRow(getNegativeDecisionVariableOffset());
+      int negativeVarColumn = columnLabels.indexOf("x-");
+      Integer negativeVarBasicRow = negativeVarColumn > 0 ? getBasicRow(negativeVarColumn)
: null;
       double mostNegative = negativeVarBasicRow == null ? 0 : getEntry(negativeVarBasicRow,
getRhsOffset());
+
       Set<Integer> basicRows = new HashSet<Integer>();
+      double[] coefficients = new double[getOriginalNumDecisionVariables()];
       for (int i = 0; i < coefficients.length; i++) {
-          Integer basicRow = getBasicRow(getNumObjectiveFunctions() + i);
+          int colIndex = columnLabels.indexOf("x" + i);
+          if (colIndex < 0) {
+            coefficients[i] = 0;
+            continue;
+          }
+          Integer basicRow = getBasicRow(colIndex);
           if (basicRows.contains(basicRow)) {
               // if multiple variables can take a given value
               // then we choose the first and set the rest equal to 0
@@ -349,7 +384,7 @@
                   (restrictToNonNegative ? 0 : mostNegative);
           }
       }
-        return new RealPointValuePair(coefficients, f.getValue(coefficients));
+      return new RealPointValuePair(coefficients, f.getValue(coefficients));
     }
 
     /**
@@ -443,15 +478,6 @@
     }
 
     /**
-     * Returns the offset of the extra decision variable added when there is a
-     * negative decision variable in the original problem.
-     * @return the offset of x-
-     */
-    protected final int getNegativeDecisionVariableOffset() {
-      return getNumObjectiveFunctions() + getOriginalNumDecisionVariables();
-    }
-
-    /**
      * Get the number of decision variables.
      * <p>
      * If variables are not restricted to positive values, this will include 1
@@ -471,7 +497,7 @@
      * @see #getNumDecisionVariables()
      */
     protected final int getOriginalNumDecisionVariables() {
-        return restrictToNonNegative ? numDecisionVariables : numDecisionVariables - 1;
+        return f.getCoefficients().getDimension();
     }
 
     /**
@@ -562,4 +588,5 @@
         ois.defaultReadObject();
         MatrixUtils.deserializeRealMatrix(this, "tableau", ois);
     }
+
 }

Modified: commons/proper/math/trunk/src/site/xdoc/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/site/xdoc/changes.xml?rev=813301&r1=813300&r2=813301&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Thu Sep 10 08:20:28 2009
@@ -39,6 +39,9 @@
   </properties>
   <body>
     <release version="2.1" date="TBD" description="TBD">
+      <action dev="luc" type="fix" issue="MATH-293" due-to="Benjamin McCann">
+        Fixed a OutOfBoundException in simplex solver when some constraints are tight.
+      </action>
       <action dev="luc" type="fix" issue="MATH-291" due-to="Sebb">
         Fixed misleading number formats in error messages for adaptive
         stepsize integrators.

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=813301&r1=813300&r2=813301&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
Thu Sep 10 08:20:28 2009
@@ -117,6 +117,43 @@
     }
 
     @Test
+    public void testMath293() throws OptimizationException {
+      LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7,
0.3, 0.4, 0.6}, 0 );
+      Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ,
30.0));
+      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ,
30.0));
+      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 },
Relationship.GEQ, 10.0));
+      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 },
Relationship.GEQ, 10.0));
+      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 },
Relationship.GEQ, 10.0));
+
+      SimplexSolver solver = new SimplexSolver();
+      RealPointValuePair solution1 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
+
+      Assert.assertEquals(15.7143, solution1.getPoint()[0], .0001);
+      Assert.assertEquals(0.0, solution1.getPoint()[1], .0001);
+      Assert.assertEquals(14.2857, solution1.getPoint()[2], .0001);
+      Assert.assertEquals(0.0, solution1.getPoint()[3], .0001);
+      Assert.assertEquals(0.0, solution1.getPoint()[4], .0001);
+      Assert.assertEquals(30.0, solution1.getPoint()[5], .0001);
+      Assert.assertEquals(40.57143, solution1.getValue(), .0001);
+
+      double valA = 0.8 * solution1.getPoint()[0] + 0.2 * solution1.getPoint()[1];
+      double valB = 0.7 * solution1.getPoint()[2] + 0.3 * solution1.getPoint()[3];
+      double valC = 0.4 * solution1.getPoint()[4] + 0.6 * solution1.getPoint()[5];
+
+      f = new LinearObjectiveFunction(new double[] { 0.8, 0.2, 0.7, 0.3, 0.4, 0.6}, 0 );
+      constraints = new ArrayList<LinearConstraint>();
+      constraints.add(new LinearConstraint(new double[] { 1, 0, 1, 0, 1, 0 }, Relationship.EQ,
30.0));
+      constraints.add(new LinearConstraint(new double[] { 0, 1, 0, 1, 0, 1 }, Relationship.EQ,
30.0));
+      constraints.add(new LinearConstraint(new double[] { 0.8, 0.2, 0.0, 0.0, 0.0, 0.0 },
Relationship.GEQ, valA));
+      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.7, 0.3, 0.0, 0.0 },
Relationship.GEQ, valB));
+      constraints.add(new LinearConstraint(new double[] { 0.0, 0.0, 0.0, 0.0, 0.4, 0.6 },
Relationship.GEQ, valC));
+
+      RealPointValuePair solution2 = solver.optimize(f, constraints, GoalType.MAXIMIZE, true);
+      Assert.assertEquals(40.57143, solution2.getValue(), .0001);
+    }
+
+    @Test
     public void testSimplexSolver() throws OptimizationException {
         LinearObjectiveFunction f =
             new LinearObjectiveFunction(new double[] { 15, 10 }, 7);



Mime
View raw message