Return-Path: 
 <commits-return-6812-apmail-commons-commits-archive=commons.apache.org@commons.apache.org>
Delivered-To: apmail-commons-commits-archive@minotaur.apache.org
Received: (qmail 77227 invoked from network); 2 Jun 2009 19:37:42 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3)
  by minotaur.apache.org with SMTP; 2 Jun 2009 19:37:42 -0000
Received: (qmail 99269 invoked by uid 500); 2 Jun 2009 19:37:54 -0000
Delivered-To: apmail-commons-commits-archive@commons.apache.org
Received: (qmail 99174 invoked by uid 500); 2 Jun 2009 19:37:53 -0000
Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:commits-help@commons.apache.org>
List-Unsubscribe: <mailto:commits-unsubscribe@commons.apache.org>
List-Post: <mailto:commits@commons.apache.org>
List-Id: <commits.commons.apache.org>
Reply-To: dev@commons.apache.org
Delivered-To: mailing list commits@commons.apache.org
Received: (qmail 99165 invoked by uid 99); 2 Jun 2009 19:37:53 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 02 Jun 2009 19:37:53 +0000
X-ASF-Spam-Status: No, hits=-2000.0 required=10.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; Tue, 02 Jun 2009 19:37:51 +0000
Received: by eris.apache.org (Postfix, from userid 65534)
	id 6150B23888C8; Tue,  2 Jun 2009 19:37:31 +0000 (UTC)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r781135 - in /commons/proper/math/trunk/src:
 java/org/apache/commons/math/optimization/linear/SimplexTableau.java
 site/xdoc/changes.xml
 test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
Date: Tue, 02 Jun 2009 19:37:31 -0000
To: commits@commons.apache.org
From: luc@apache.org
X-Mailer: svnmailer-1.0.8
Message-Id: <20090602193731.6150B23888C8@eris.apache.org>
X-Virus-Checked: Checked by ClamAV on apache.org

Author: luc
Date: Tue Jun  2 19:37:30 2009
New Revision: 781135

URL: http://svn.apache.org/viewvc?rev=781135&view=rev
Log:
Fixed a problem when setting some variables (several variables were set instead of only one)
JIRA: MATH-272

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

Modified: commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java?rev=781135&r1=781134&r2=781135&view=diff
==============================================================================
--- commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java (original)
+++ commons/proper/math/trunk/src/java/org/apache/commons/math/optimization/linear/SimplexTableau.java Tue Jun  2 19:37:30 2009
@@ -23,7 +23,9 @@
 import java.io.Serializable;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Set;
 
 import org.apache.commons.math.linear.MatrixUtils;
 import org.apache.commons.math.linear.RealMatrix;
@@ -321,39 +323,27 @@
      */
     protected RealPointValuePair getSolution() {
         double[] coefficients = new double[getOriginalNumDecisionVariables()];
-        double mostNegative = getDecisionVariableValue(getOriginalNumDecisionVariables());
+        Integer basicRow =
+            getBasicRow(getNumObjectiveFunctions() + getOriginalNumDecisionVariables());
+        double mostNegative = basicRow == null ? 0 : getEntry(basicRow, getRhsOffset());
+        Set<Integer> basicRows = new HashSet<Integer>();
         for (int i = 0; i < coefficients.length; i++) {
-            coefficients[i] =
-                getDecisionVariableValue(i) - (restrictToNonNegative ? 0 : mostNegative); 
+            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
+                coefficients[i] = 0;
+            } else {
+                basicRows.add(basicRow);
+                coefficients[i] =
+                    (basicRow == null ? 0 : getEntry(basicRow, getRhsOffset())) -
+                    (restrictToNonNegative ? 0 : mostNegative);
+            }
         }
         return new RealPointValuePair(coefficients, f.getValue(coefficients));
     }
 
     /**
-     * Get the value of the given decision variable.  This is not the actual
-     * value as it is guaranteed to be >= 0 and thus must be corrected before
-     * being returned to the user.
-     * 
-     * @param decisionVariable The index of the decision variable
-     * @return The value of the given decision variable.
-     */
-    protected double getDecisionVariableValue(final int decisionVariable) {
-      int col = getNumObjectiveFunctions() + decisionVariable;  
-      Integer basicRow = getBasicRow(col);
-      if (basicRow == null) {
-          return 0;
-      }
-      // if there are multiple variables that can take the value on the RHS
-      // then we'll give the first variable that value
-      for (int i = getNumObjectiveFunctions(); i < col; i++) {
-          if (tableau.getEntry(basicRow, i) == 1) {
-              return 0;
-          }
-      }
-      return getEntry(basicRow, getRhsOffset()); 
-  }
-
-    /**
      * Subtracts a multiple of one row from another.
      * <p>
      * After application of this operation, the following will hold:

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=781135&r1=781134&r2=781135&view=diff
==============================================================================
--- commons/proper/math/trunk/src/site/xdoc/changes.xml (original)
+++ commons/proper/math/trunk/src/site/xdoc/changes.xml Tue Jun  2 19:37:30 2009
@@ -39,6 +39,10 @@
   </properties>
   <body>
     <release version="2.0" date="TBD" description="TBD">
+      <action dev="luc" type="fix" issue="MATH-272" due-to="Benjamin McCann">
+        Fixed a problem when setting some variables (several variables were set
+        instead of only one)
+      </action>
       <action dev="luc" type="add" due-to="Gilles Sadowski">
         Added a way to limit the number of functions evaluations in optimizers
         (the number of iterations could already be limited)

Modified: commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java?rev=781135&r1=781134&r2=781135&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java (original)
+++ commons/proper/math/trunk/src/test/org/apache/commons/math/optimization/linear/SimplexSolverTest.java Tue Jun  2 19:37:30 2009
@@ -17,19 +17,38 @@
 
 package org.apache.commons.math.optimization.linear;
 
+import static org.junit.Assert.assertEquals;
+
 import java.util.ArrayList;
 import java.util.Collection;
 
-import junit.framework.TestCase;
-
 import org.apache.commons.math.linear.RealVector;
 import org.apache.commons.math.linear.RealVectorImpl;
 import org.apache.commons.math.optimization.GoalType;
 import org.apache.commons.math.optimization.OptimizationException;
 import org.apache.commons.math.optimization.RealPointValuePair;
+import org.junit.Test;
 
-public class SimplexSolverTest extends TestCase {
+public class SimplexSolverTest {
 
+    @Test
+    public void testMath272() throws OptimizationException {
+        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 2, 2, 1 }, 0);
+        Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
+        constraints.add(new LinearConstraint(new double[] { 1, 1, 0 }, Relationship.GEQ,  1));
+        constraints.add(new LinearConstraint(new double[] { 1, 0, 1 }, Relationship.GEQ,  1));
+        constraints.add(new LinearConstraint(new double[] { 0, 1, 0 }, Relationship.GEQ,  1));
+
+        SimplexSolver solver = new SimplexSolver();
+        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, true);
+        
+        assertEquals(0.0, solution.getPoint()[0], .0000001);
+        assertEquals(1.0, solution.getPoint()[1], .0000001);
+        assertEquals(1.0, solution.getPoint()[2], .0000001);
+        assertEquals(3.0, solution.getValue(), .0000001);
+      }
+
+    @Test
     public void testSimplexSolver() throws OptimizationException {
         LinearObjectiveFunction f =
             new LinearObjectiveFunction(new double[] { 15, 10 }, 7);
@@ -40,15 +59,16 @@
 
         SimplexSolver solver = new SimplexSolver();
         RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-        assertEquals(2.0, solution.getPoint()[0]);
-        assertEquals(2.0, solution.getPoint()[1]);
-        assertEquals(57.0, solution.getValue());
+        assertEquals(2.0, solution.getPoint()[0], 0.0);
+        assertEquals(2.0, solution.getPoint()[1], 0.0);
+        assertEquals(57.0, solution.getValue(), 0.0);
     }
 
     /**
      * With no artificial variables needed (no equals and no greater than
      * constraints) we can go straight to Phase 2.
      */
+    @Test
     public void testModelWithNoArtificialVars() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -58,11 +78,12 @@
 
         SimplexSolver solver = new SimplexSolver();
         RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-        assertEquals(2.0, solution.getPoint()[0]);
-        assertEquals(2.0, solution.getPoint()[1]);
-        assertEquals(50.0, solution.getValue());
+        assertEquals(2.0, solution.getPoint()[0], 0.0);
+        assertEquals(2.0, solution.getPoint()[1], 0.0);
+        assertEquals(50.0, solution.getValue(), 0.0);
     }
 
+    @Test
     public void testMinimization() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -72,11 +93,12 @@
 
         SimplexSolver solver = new SimplexSolver();
         RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MINIMIZE, false);
-        assertEquals(4.0, solution.getPoint()[0]);
-        assertEquals(0.0, solution.getPoint()[1]);
-        assertEquals(-13.0, solution.getValue());
+        assertEquals(4.0, solution.getPoint()[0], 0.0);
+        assertEquals(0.0, solution.getPoint()[1], 0.0);
+        assertEquals(-13.0, solution.getValue(), 0.0);
     }
 
+    @Test
     public void testSolutionWithNegativeDecisionVariable() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -85,44 +107,33 @@
 
         SimplexSolver solver = new SimplexSolver();
         RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-        assertEquals(-2.0, solution.getPoint()[0]);
-        assertEquals(8.0, solution.getPoint()[1]);
-        assertEquals(12.0, solution.getValue());
+        assertEquals(-2.0, solution.getPoint()[0], 0.0);
+        assertEquals(8.0, solution.getPoint()[1], 0.0);
+        assertEquals(12.0, solution.getValue(), 0.0);
     }
 
-    public void testInfeasibleSolution() {
+    @Test(expected = NoFeasibleSolutionException.class)
+    public void testInfeasibleSolution() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
         constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.LEQ, 1));
         constraints.add(new LinearConstraint(new double[] { 1 }, Relationship.GEQ, 3));
 
         SimplexSolver solver = new SimplexSolver();
-        try {
-            solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-            fail("An exception should have been thrown.");
-        } catch (NoFeasibleSolutionException e) {
-            // expected;
-        } catch (OptimizationException e) {
-            fail("wrong exception caught");
-        }
+        solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
     }
 
-    public void testUnboundedSolution() {
+    @Test(expected = UnboundedSolutionException.class)
+    public void testUnboundedSolution() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 15, 10 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
         constraints.add(new LinearConstraint(new double[] { 1, 0 }, Relationship.EQ, 2));
 
         SimplexSolver solver = new SimplexSolver();
-        try {
-            solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-            fail("An exception should have been thrown.");
-        } catch (UnboundedSolutionException e) {
-            // expected;
-        } catch (OptimizationException e) {
-            fail("wrong exception caught");
-        }
+        solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
     }
 
+    @Test
     public void testRestrictVariablesToNonNegative() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 409, 523, 70, 204, 339 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -142,6 +153,7 @@
         assertEquals(1438556.7491409, solution.getValue(), .0000001);
     }
 
+    @Test
     public void testEpsilon() throws OptimizationException {
       LinearObjectiveFunction f =
           new LinearObjectiveFunction(new double[] { 10, 5, 1 }, 0);
@@ -152,12 +164,13 @@
 
       SimplexSolver solver = new SimplexSolver();
       RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, false);
-      assertEquals(1.0, solution.getPoint()[0]);
-      assertEquals(1.0, solution.getPoint()[1]);
-      assertEquals(0.0, solution.getPoint()[2]);
-      assertEquals(15.0, solution.getValue());
+      assertEquals(1.0, solution.getPoint()[0], 0.0);
+      assertEquals(1.0, solution.getPoint()[1], 0.0);
+      assertEquals(0.0, solution.getPoint()[2], 0.0);
+      assertEquals(15.0, solution.getValue(), 0.0);
   }
     
+    @Test
     public void testTrivialModel() throws OptimizationException {
         LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 1, 1 }, 0);
         Collection<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
@@ -168,6 +181,7 @@
         assertEquals(0, solution.getValue(), .0000001);
     }
 
+    @Test
     public void testLargeModel() throws OptimizationException {
         double[] objective = new double[] {
                                            1, 1, 1, 1, 1, 1, 1, 1, 1, 1,